{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T15:27:29Z","timestamp":1778081249298,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T00:00:00Z","timestamp":1711497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CyberSecurity Research Flanders","award":["VR20192203"],"award-info":[{"award-number":["VR20192203"]}]},{"name":"Research Council KU Leuven","award":["C16\/15\/058"],"award-info":[{"award-number":["C16\/15\/058"]}]},{"name":"Horizon 2020 ERC Advanced Grant","award":["101020005 Belfort"],"award-info":[{"award-number":["101020005 Belfort"]}]},{"name":"SRC grant","award":["2909.001"],"award-info":[{"award-number":["2909.001"]}]},{"name":"Research Council KU Leuven grant","award":["C14\/18\/067"],"award-info":[{"award-number":["C14\/18\/067"]}]},{"name":"FWO","award":["203056\/1241722N LV"],"award-info":[{"award-number":["203056\/1241722N LV"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>\n            Polynomial multiplication algorithms such as Toom-Cook and the Number Theoretic Transform are fundamental building blocks for lattice-based post-quantum cryptography. In this work we present correlation power-analysis-based side-channel analysis methodologies targeting\n            <jats:italic>every<\/jats:italic>\n            polynomial multiplication strategy for\n            <jats:italic>all<\/jats:italic>\n            lattice-based post-quantum key encapsulation mechanisms in the final round of the NIST post-quantum standardization procedure. We perform practical experiments on real side-channel measurements, demonstrating that our method allows to extract the secret key from all lattice-based post-quantum key encapsulation mechanisms. Our analysis shows that the used polynomial multiplication strategy can significantly impact the time complexity of the attack.\n          <\/jats:p>","DOI":"10.1145\/3569420","type":"journal-article","created":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T12:33:20Z","timestamp":1667565200000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["Side-channel Analysis of Lattice-based Post-quantum Cryptography: Exploiting Polynomial Multiplication"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9210-5798","authenticated-orcid":false,"given":"Catinca","family":"Mujdei","sequence":"first","affiliation":[{"name":"imec-COSIC KU Leuven, Leuven, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5740-5066","authenticated-orcid":false,"given":"Lennert","family":"Wouters","sequence":"additional","affiliation":[{"name":"imec-COSIC KU Leuven, Leuven, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2594-588X","authenticated-orcid":false,"given":"Angshuman","family":"Karmakar","sequence":"additional","affiliation":[{"name":"imec-COSIC KU Leuven, Leuven, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6883-4074","authenticated-orcid":false,"given":"Arthur","family":"Beckers","sequence":"additional","affiliation":[{"name":"imec-COSIC KU Leuven, Leuven, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0457-5728","authenticated-orcid":false,"given":"Jose Maria","family":"Bermudo Mera","sequence":"additional","affiliation":[{"name":"imec-COSIC KU Leuven, Leuven, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0879-076X","authenticated-orcid":false,"given":"Ingrid","family":"Verbauwhede","sequence":"additional","affiliation":[{"name":"imec-COSIC KU Leuven, Leuven, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2024,3,27]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"99","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing","author":"Ajtai M.","year":"1996","unstructured":"M. Ajtai. 1996. Generating hard instances of lattice problems (extended abstract). In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. ACM, 99\u2013108."},{"key":"e_1_3_1_3_2","article-title":"Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process","author":"Alagic Gorjan","year":"2017","unstructured":"Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, John Kelsey, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, and Daniel Smith-Tone. 2017. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process. Retrieved March 20, 2022, from https:\/\/ nvlpubs.nist.gov\/nistpubs\/ir\/2020\/NIST.IR.8309.pdf. https:\/\/nvlpubs.nist.gov\/nistpubs\/ir\/2020\/NIST.IR.8309.pdf. https:\/\/nvlpubs.nist.gov\/nistpubs\/ir\/2020\/NIST.IR.8309.pdf.","journal-title":"https:\/\/ nvlpubs.nist.gov\/nistpubs\/ir\/2020\/NIST.IR.8309.pdf"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53018-4_6"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1515\/jmc-2015-0016"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2021.i1.217-238"},{"key":"e_1_3_1_7_2","first-page":"327","volume-title":"25th USENIX Security Symposium (USENIX Security\u201916)","author":"Alkim Erdem","year":"2016","unstructured":"Erdem Alkim, L\u00e9o Ducas, Thomas P\u00f6ppelmann, and Peter Schwabe. 2016. Post-quantum key exchange - A new hope. In 25th USENIX Security Symposium (USENIX Security\u201916), Thorsten Holz and Stefan Savage (Eds.). USENIX Association, 327\u2013343. https:\/\/www.usenix.org\/conference\/usenixsecurity16\/technical-sessions\/presentation\/alkim."},{"key":"e_1_3_1_8_2","article-title":"CRYSTALS-Kyber. Algorithm Specifications and Supporting Documentation. (Round 3 Submission)","author":"Avanzi Roberto","year":"2021","unstructured":"Roberto Avanzi, Joppe Bos, L\u00e9o Ducas, Eike Kiltz, Tancr\u00e9de Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehl\u00e9. 2021. CRYSTALS-Kyber. Algorithm Specifications and Supporting Documentation. (Round 3 Submission). Retrieved March 20, 2022, from https:\/\/pq-crystals.org\/kyber\/data\/kyber-specification-round3-20210131.pdf.","journal-title":"https:\/\/pq-crystals.org\/kyber\/data\/kyber-specification-round3-20210131.pdf"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/HST.2018.8383894"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_42"},{"key":"e_1_3_1_11_2","article-title":"SABER: Mod-LWR based KEM (Round 3 Submission)","author":"Basso Andrea","year":"2020","unstructured":"Andrea Basso, Jose Maria Bermudo Mera, Jan-Pieter D\u2019Anvers, Angshuman Karmakar, Sujoy Sinha Roy, Michiel Van Beirendonck, and Frederik Vercauteren. 2020. SABER: Mod-LWR based KEM (Round 3 Submission). Retrieved March 20, 2022, from https:\/\/www.esat.kuleuven.be\/cosic\/pqcrypto\/saber\/files\/saberspecround3.pdf.","journal-title":"https:\/\/www.esat.kuleuven.be\/cosic\/pqcrypto\/saber\/files\/saberspecround3.pdf"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3429983"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2021.i3.334-359"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2021.i4.173-214"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28632-5_2"},{"key":"e_1_3_1_16_2","article-title":"NTRU Algorithm Specifications and Supporting Documentation","author":"Chen Cong","year":"2020","unstructured":"Cong Chen, Oussama Danba, Jeffrey Hoffstein, Andreas H\u00fclsing, Joost Rijneveld, John M. Schanck, Tsunekazu Saito, Peter Schwabe, William Whyte, Keita Xagawa, Takashi Yamakawa, and Zhenfei Zhang. 2020. NTRU Algorithm Specifications and Supporting Documentation, 2nd PQC Standardization Conference, 2019, University of California, Santa Barbara, CA. Retrieved September 30, 2021, from https:\/\/ntru.org\/f\/ntru-20190330.pdf.","journal-title":"2nd PQC Standardization Conference, 2019, University of California, Santa Barbara, CA"},{"key":"e_1_3_1_17_2","article-title":"NTRU Algorithm Specifications and Supporting Documentation","author":"Chen Cong","year":"2019","unstructured":"Cong Chen, Oussama Danba, Jeffrey Hoffstein, Andreas H\u00fclsing, Joost Rijneveld, John M. Schanck, Peter Schwabe, William Whyte, and Zhenfei Zhang. 2019. NTRU Algorithm Specifications and Supporting Documentation, 2nd PQC Standardization Conference, 2019, University of California, Santa Barbara, CA. https:\/\/ntru.org\/f\/ntru-20190330.pdf.","journal-title":"2nd PQC Standardization Conference, 2019, University of California, Santa Barbara, CA"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2021.i2.159-188"},{"key":"e_1_3_1_19_2","volume-title":"On the Minimum Computation Time of Functions","author":"Cook S. A.","year":"1966","unstructured":"S. A. Cook. 1966. On the Minimum Computation Time of Functions. Ph.D. Dissertation. Harvard University, 51\u201377."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56880-1_12"},{"key":"e_1_3_1_22_2","article-title":"SABER: Mod-LWR based KEM","author":"D\u2019Anvers Jan Pieter","year":"2019","unstructured":"Jan Pieter D\u2019Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Vercauteren. 2019. SABER: Mod-LWR based KEM, 2nd PQC Standardization Conference, 2019, University of California, Santa Barbara, CA. https:\/\/www.esat.kuleuven.be\/cosic\/pqcrypto\/saber\/files\/SABER_KEM_Round_2.zip.","journal-title":"2nd PQC Standardization Conference, 2019, University of California, Santa Barbara, CA"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/3-540-48405-1_34","volume-title":"Advances in Cryptology (CRYPTO\u201999)","author":"Fujisaki Eiichiro","year":"1999","unstructured":"Eiichiro Fujisaki and Tatsuaki Okamoto. 1999. Secure integration of asymmetric and symmetric encryption schemes. In Advances in Cryptology (CRYPTO\u201999), Michael Wiener (Ed.). Springer, Berlin, 537\u2013554."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-011-9114-1"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1464291.1464352"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054868"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70500-2_12"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.13154\/tches.v2020.i1.123-151"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66787-4_12"},{"key":"e_1_3_1_30_2","article-title":"Faster multiplication in  \\(\\mathbb {Z}_{2^m}[x]\\)  on Cortex-M4 to speed up NIST PQC candidates","author":"Kannwischer Matthias J.","year":"2018","unstructured":"Matthias J. Kannwischer, Joost Rijneveld, and Peter Schwabe. 2018. Faster multiplication in \\(\\mathbb {Z}_{2^m}[x]\\) on Cortex-M4 to speed up NIST PQC candidates. Cryptology ePrint Archive, Report 2018\/1018. (2018). https:\/\/eprint.iacr.org\/2018\/1018.","journal-title":"Cryptology ePrint Archive, Report 2018\/1018"},{"key":"e_1_3_1_31_2","unstructured":"Matthias J. Kannwischer Joost Rijneveld Peter Schwabe and Ko Stoffelen. 2018. PQM4: Post-quantum crypto library for the ARM Cortex-M4. Retrieved March 20 2022 from https:\/\/github.com\/mupq\/pqm4."},{"issue":"7","key":"e_1_3_1_32_2","first-page":"293","article-title":"Multiplication of many-digital numbers by automatic computers","volume":"145","author":"Karatsuba A.","year":"1962","unstructured":"A. Karatsuba and Yu. Ofman. 1962. Multiplication of many-digital numbers by automatic computers. Proceedings of USSR Academy of Sciences 145, 7 (1962), 293\u2013294.","journal-title":"Proceedings of USSR Academy of Sciences"},{"key":"e_1_3_1_33_2","article-title":"Power analysis attack on Kyber","author":"Karlov Alexandre","year":"2021","unstructured":"Alexandre Karlov and Natacha Linard de Guertechin. 2021. Power analysis attack on Kyber. Cryptology ePrint Archive, Paper 2021\/1311. (2021). https:\/\/eprint.iacr.org\/2021\/1311.","journal-title":"Cryptology ePrint Archive, Paper 2021\/1311"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.13154\/tches.v2018.i3.243-266"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1090\/s0025-5718-1987-0866109-5"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48405-1_25"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-014-9938-4"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1587\/transfun.E93.A.153"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.13154\/tches.v2019.i3.180-201"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.13154\/tches.v2020.i2.222-244"},{"key":"e_1_3_1_42_2","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/3-540-39799-X_31","volume-title":"Advances in Cryptology (CRYPTO\u201985), Proceedings","author":"Miller Victor S.","year":"1986","unstructured":"Victor S. Miller. 1986. Use of elliptic curves in cryptography. In Advances in Cryptology (CRYPTO\u201985), Proceedings, Hugh C. Williams (Ed.). Springer, Berlin, 417\u2013426."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1985-0777282-X"},{"key":"e_1_3_1_44_2","article-title":"Post-Quantum Cryptography Standardization","year":"2017","unstructured":"NIST. 2017. Post-Quantum Cryptography Standardization. Retrieved October 10, 2021, from https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography\/Post-Quantum-Cryptography-Standardization.","journal-title":"https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography\/Post-Quantum-Cryptography-Standardization"},{"key":"e_1_3_1_45_2","first-page":"130","volume-title":"LATINCRYPT (Lecture Notes in Computer Science)","author":"Pessl Peter","year":"2019","unstructured":"Peter Pessl and Robert Primas. 2019. More practical single-trace attacks on the number theoretic transform. In LATINCRYPT (Lecture Notes in Computer Science), Vol. 11774. Springer, 130\u2013149."},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1971-0301966-0"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66787-4_25"},{"key":"e_1_3_1_48_2","first-page":"718","article-title":"Generic side-channel assisted chosen-ciphertext attacks on streamlined NTRU prime","author":"Ravi Prasanna","year":"2021","unstructured":"Prasanna Ravi, Martianus Frederic Ezerman, Shivam Bhasin, Anupam Chattopadhyay, and Sujoy Sinha Roy. 2021. Generic side-channel assisted chosen-ciphertext attacks on streamlined NTRU prime. IACR Cryptol. ePrint Arch. (2021), 718. https:\/\/eprint.iacr.org\/2021\/718.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.13154\/tches.v2020.i3.307-335"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039490"},{"key":"e_1_3_1_51_2","first-page":"84","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC\u201905)","author":"Regev Oded","year":"2005","unstructured":"Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC\u201905). ACM, 84\u201393."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78372-7_17"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/11967668_14"},{"key":"e_1_3_1_55_2","first-page":"714","volume-title":"Soviet Mathematics-Doklady","author":"Toom A. L.","year":"1963","unstructured":"A. L. Toom. 1963. The complexity of a scheme of functional elements realizing the multiplication of integers. In Soviet Mathematics-Doklady, Vol. 7. 714\u2013716. http:\/\/toomandre.com\/my-articles\/engmat\/MULT-E.PDF."},{"key":"e_1_3_1_56_2","first-page":"912","article-title":"Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: The case study of Kyber","author":"Xu Zhuang","year":"2020","unstructured":"Zhuang Xu, Owen Pemberton, Sujoy Sinha Roy, and David F. Oswald. 2020. Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: The case study of Kyber. IACR Cryptol. ePrint Arch. (2020), 912. https:\/\/eprint.iacr.org\/2020\/912.","journal-title":"IACR Cryptol. ePrint Arch."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569420","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569420","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:56Z","timestamp":1750182536000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,27]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3569420"],"URL":"https:\/\/doi.org\/10.1145\/3569420","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,27]]},"assertion":[{"value":"2022-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}