{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T14:17:34Z","timestamp":1772893054059,"version":"3.50.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,10,18]],"date-time":"2021-10-18T00:00:00Z","timestamp":1634515200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["#1453806, #1314709, #1527888, #1441484, #1850373, and CCF-1901446"],"award-info":[{"award-number":["#1453806, #1314709, #1527888, #1441484, #1850373, and CCF-1901446"]}]},{"DOI":"10.13039\/100000028","name":"Semiconductor Research Corporation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000028","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2021,11,30]]},"abstract":"<jats:p>Key exchange protocols and key encapsulation mechanisms establish secret keys to communicate digital information confidentially over public channels. Lattice-based cryptography variants of these protocols are promising alternatives given their quantum-cryptanalysis resistance and implementation efficiency. Although lattice cryptosystems can be mathematically secure, their implementations have shown side-channel vulnerabilities. But such attacks largely presume collecting multiple measurements under a fixed key, leaving the more dangerous single-trace attacks unexplored.<\/jats:p>\n          <jats:p>\n            This article demonstrates successful single-trace power side-channel attacks on lattice-based key exchange and encapsulation protocols. Our attack targets both hardware and software implementations of matrix multiplications used in lattice cryptosystems. The crux of our idea is to apply a horizontal attack that makes hypotheses on several intermediate values within a single execution all relating to the same secret, and to combine their correlations for accurately estimating the secret key. We illustrate that the design of protocols combined with the nature of lattice arithmetic enables our attack. Since a straightforward attack suffers from false positives, we demonstrate a novel\n            <jats:italic>extend-and-prune<\/jats:italic>\n            procedure to recover the key by following the sequence of intermediate updates during multiplication.\n          <\/jats:p>\n          <jats:p>\n            We analyzed two protocols,\n            <jats:monospace>Frodo<\/jats:monospace>\n            and\n            <jats:monospace>FrodoKEM<\/jats:monospace>\n            , and reveal that they are vulnerable to our attack. We implement both stand-alone hardware and RISC-V based software realizations and test the effectiveness of the proposed attack by using concrete parameters of these protocols on physical platforms with real measurements. We show that the proposed attack can estimate secret keys from a single power measurement with over 99% success rate.\n          <\/jats:p>","DOI":"10.1145\/3476799","type":"journal-article","created":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T01:02:15Z","timestamp":1634605335000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Horizontal Side-Channel Vulnerabilities of Post-Quantum Key Exchange and Encapsulation Protocols"],"prefix":"10.1145","volume":"20","author":[{"given":"Furkan","family":"Aydin","sequence":"first","affiliation":[{"name":"North Carolina State University, Raleigh, NC, USA"}]},{"given":"Aydin","family":"Aysu","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC, USA"}]},{"given":"Mohit","family":"Tiwari","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}]},{"given":"Andreas","family":"Gerstlauer","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}]},{"given":"Michael","family":"Orshansky","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,10,18]]},"reference":[{"issue":"1","key":"e_1_3_2_2_2","first-page":"243","article-title":"Polynomial multiplication in NTRU prime: Comparison of optimization strategies on cortex-M4","volume":"2021","author":"Alkim Erdem","year":"2020","unstructured":"Erdem Alkim, Dean Yun-Li Cheng, Chi-Ming Marvin Chung, H\u00fclya Evkan, Leo Wei-Lun Huang, Vincent Hwang, Ching-Lin Trista Li, Ruben Niederhagen, Cheng-Jhih Shih, Julian W\u00e4lde, and Bo-Yin Yang. 2020. Polynomial multiplication in NTRU prime: Comparison of optimization strategies on cortex-M4. IACR Transactions on Cryptographic Hardware and Embedded Systems 2021, 1 (2020), 243\u2013268. DOI:https:\/\/doi.org\/10.46586\/tches.v2021.i1.217-238","journal-title":"IACR Transactions on Cryptographic Hardware and Embedded Systems"},{"key":"e_1_3_2_3_2","article-title":"FrodoKEM Learning With Errors Key Encapsulation Algorithm Specifications And Supporting Documentation","author":"Alkim Erdem","year":"2020","unstructured":"Erdem Alkim, Joppe W. Bos L\u00e9o Ducas, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila. 2020. FrodoKEM Learning With Errors Key Encapsulation Algorithm Specifications And Supporting Documentation. https:\/\/frodokem.org\/files\/FrodoKEM-specification-20200930.pdf.","journal-title":"https:\/\/frodokem.org\/files\/FrodoKEM-specification-20200930.pdf"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44223-1_11"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.3390\/app8112014"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_2_7_2","unstructured":"Ali Can Atici Lejla Batina Benedikt Gierlichs and Ingrid Verbauwhede. 2008. Power analysis on NTRU implementations for RFIDs: First results. In Proceedings of the Workshop on RFID Security . 128\u2013139."},{"key":"e_1_3_2_8_2","unstructured":"Roberto Avanzi L\u00e9o Ducas Joppe Bos 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. Retrieved June 9 2021 from https:\/\/pq-crystals.org\/kyber\/data\/kyber-specification-round3-20210131.pdf."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60939-9_18"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/HST.2018.8383894"},{"key":"e_1_3_2_11_2","first-page":"599","volume-title":"DPA, Bitslicing and Masking at 1 GHz","author":"Balasch Josep","year":"2015","unstructured":"Josep Balasch, Benedikt Gierlichs, Oscar Reparaz, and Ingrid Verbauwhede. 2015. DPA, Bitslicing and Masking at 1 GHz. Springer Berlin Heidelberg, Berlin, 599\u2013619. DOI:https:\/\/doi.org\/10.1007\/978-3-662-48324-4_30"},{"key":"e_1_3_2_12_2","article-title":"SABER: Mod-LWR based KEM","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. Technical report. Retrieved from https:\/\/www.esat.kuleuven.be\/cosic\/pqcrypto\/saber\/files\/saberspecround3.pdf.","journal-title":"Technical report"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43414-7_28"},{"key":"e_1_3_2_14_2","unstructured":"STMicroelectronics 8 bit MCUs. 2020. Retrieved June 9 2021 from https:\/\/www.st.com\/en\/microcontrollers-microprocessors\/stm8-8-bit-mcus.html."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03326-2_17"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978425"},{"key":"e_1_3_2_17_2","first-page":"216","volume-title":"Proceedings of the Selected Areas in Cryptography","author":"Bos Joppe W.","year":"2018","unstructured":"Joppe W. Bos, Simon Friedberger, Marco Martinoli, Elisabeth Oswald, and Martijn Stam. 2018. Assessing the feasibility of single trace power analysis of frodo. In Proceedings of the Selected Areas in Cryptography. Springer, 216\u2013234."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28632-5_2"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2899007.2899011"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/648255.752740"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/1948352.1948359"},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","unstructured":"Thomas Espitau Pierre-Alain Fouque Benoit Gerard and Mehdi Tibouchi. 2017. Side-Channel Attacks on BLISS Lattice-Based Signatures \u2013 Exploiting Branch Tracing Against strongSwan and Electromagnetic Emanations in Microcontrollers . Cryptology ePrint Archive Report 2017\/505. Retrieved June 9 2021 from http:\/\/eprint.iacr.org\/2017\/505.","DOI":"10.1145\/3133956.3134028"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27998-5_11"},{"key":"e_1_3_2_24_2","article-title":"BSI TR-02102-1: \u201cCryptographic Mechanisms: Recommendations and Key Lengths\u201c Version: 2020-1","author":"Security Federal Office for Information","year":"2020","unstructured":"Federal Office for Information Security. 2020. BSI TR-02102-1: \u201cCryptographic Mechanisms: Recommendations and Key Lengths\u201c Version: 2020-1. Retrieved from https:\/\/www.bsi.bund.de\/SharedDocs\/Downloads\/EN\/BSI\/Publications\/TechGuidelines\/TG02102\/BSI-TR-02102-1.html.","journal-title":"https:\/\/www.bsi.bund.de\/SharedDocs\/Downloads\/EN\/BSI\/Publications\/TechGuidelines\/TG02102\/BSI-TR-02102-1.html"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45238-6_22"},{"issue":"1","key":"e_1_3_2_26_2","first-page":"123","article-title":"Power analysis on NTRU prime","volume":"2020","author":"Huang Wei-Lun","year":"2020","unstructured":"Wei-Lun Huang, Jiun-Peng Chen, and Bo-Yin Yang. 2020. Power analysis on NTRU prime. IACR Transactions on Cryptographic Hardware and Embedded Systems 2020, 1 (2020), 123\u2013151. DOI:https:\/\/doi.org\/10.13154\/tches.v2020.i1.123-151","journal-title":"IACR Transactions on Cryptographic Hardware and Embedded Systems"},{"key":"e_1_3_2_27_2","first-page":"368","volume-title":"Cache Attacks Enable Bulk Key Recovery on the Cloud","author":"\u0130nci Mehmet Sinan","year":"2016","unstructured":"Mehmet Sinan \u0130nci, Berk Gulmezoglu, Gorka Irazoqui, Thomas Eisenbarth, and Berk Sunar. 2016. Cache Attacks Enable Bulk Key Recovery on the Cloud. Springer Berlin Heidelberg, Berlin, 368\u2013388. DOI:https:\/\/doi.org\/10.1007\/978-3-662-53140-2_18"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2020.i3.243-268"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FPL50879.2020.00016"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"Emre Karabulut and Aydin Aysu. 2021. Falcon Down: Breaking Falcon Post-Quantum Signature Scheme through Side-Channel Attacks . Cryptology ePrint Archive Report 2021\/772. Retrieved June 9 2021 from https:\/\/eprint.iacr.org\/2021\/772.","DOI":"10.1109\/DAC18074.2021.9586131"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3038701"},{"key":"e_1_3_2_32_2","unstructured":"Il-Ju Kim Tae-Ho Lee Jaeseung Han Bo-Yeon Sim and Dong-Guk Han. 2019. On Security of Fiat-Shamir Signatures over Lattice in the Presence of Randomness Leakage . Cryptology ePrint Archive Report 2019\/715. Retrieved June 9 2021 from http:\/\/eprint.iacr.org\/2019\/715."},{"key":"e_1_3_2_33_2","unstructured":"Il-Ju Kim Tae-Ho Lee Jaeseung Han Bo-Yeon Sim and Dong-Guk Han. 2020. Novel Single-Trace ML Profiling Attacks on NIST 3 Round candidate Dilithium . Cryptology ePrint Archive Report 2020\/1383. Retrieved June 9 2021 from http:\/\/eprint.iacr.org\/2020\/1383."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.3390\/app8101809"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/646764.703989"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2019.i3.180-201"},{"key":"e_1_3_2_37_2","first-page":"61","volume-title":"Statistical Characteristics of Power Traces","author":"Mangard Stefan","year":"2007","unstructured":"Stefan Mangard, Elisabeth Oswald, and Thomas Popp. 2007. Statistical Characteristics of Power Traces. Springer US, Boston, MA, 61\u201399. DOI:https:\/\/doi.org\/10.1007\/978-0-387-38162-6_4"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1873548.1873552"},{"key":"e_1_3_2_39_2","unstructured":"MaximIntegrated Secure MCUs. 2020. Retrieved from https:\/\/para.maximintegrated.com\/en\/search.mvp?fam=micros&1233=Secure."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3017930"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/3408352.3408433"},{"key":"e_1_3_2_42_2","article-title":"Workshop on Cybersecurity in a Post-Quantum World","author":"Technology National Institute of Standards and","year":"2015","unstructured":"National Institute of Standards and Technology. 2015. Workshop on Cybersecurity in a Post-Quantum World. Retrieved from https:\/\/www.nist.gov\/news-events\/events\/2015\/04\/workshop-cybersecurity-post-quantum-world.","journal-title":"https:\/\/www.nist.gov\/news-events\/events\/2015\/04\/workshop-cybersecurity-post-quantum-world"},{"key":"e_1_3_2_43_2","article-title":"A side-channel attack on a masked IND-CCA secure saber KEM","author":"Ngo Kalle","year":"2021","unstructured":"Kalle Ngo, E. Dubrova, Q. Guo, and T. Johansson. 2021. A side-channel attack on a masked IND-CCA secure saber KEM. IACR Cryptology ePrint Archive 2021, 4 (2021), 676\u2013707. DOI:https:\/\/doi.org\/10.46586\/tches.v2021.i4.676-707","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2018.i1.142-174"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/LES.2019.2960457"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60939-9_19"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/AsianHOST.2016.7835555"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49890-4_9"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30530-7_7"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33481-8_8"},{"key":"e_1_3_2_51_2","doi-asserted-by":"crossref","unstructured":"Thomas P\u00f6ppelmann and Tim G\u00fcneysu. 2014. Area optimization of lightweight lattice-based encryption on reconfigurable hardware. In Proceedings of the IEEE International Symposium on Circuits and Systems . 2796-2799.DOI:https:\/\/doi.org\/10.1109\/ISCAS.2014.6865754","DOI":"10.1109\/ISCAS.2014.6865754"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66787-4_25"},{"key":"e_1_3_2_53_2","unstructured":"Prasanna Ravi Shivam Bhasin Sujoy Sinha Roy and Anupam Chattopadhyay. 2020. Drop by Drop you break the rock - Exploiting generic vulnerabilities in Lattice-based PKE\/KEMs using EM-based Physical Attacks . Cryptology ePrint Archive Report 2020\/549. Retrieved June 9 2021 from http:\/\/eprint.iacr.org\/2020\/549."},{"key":"e_1_3_2_54_2","unstructured":"Prasanna Ravi Mahabir Prasad Jhanwar James Howe Anupam Chattopadhyay and Shivam Bhasin. 2018. Side-channel Assisted Existential Forgery Attack on Dilithium-A NIST PQC candidate . Cryptology ePrint Archive Report 2018\/821. Retrieved June 9 2021 from https:\/\/eprint.iacr.org\/2018\/821.pdf."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2020.i3.307-335"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29360-8_15"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-016-0126-5"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48324-4_34"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_2_61_2","unstructured":"Bo-Yeon Sim Jihoon Kwon Joohee Lee Il-Ju Kim Taeho Lee Jaeseung Han Hyojin Yoon Jihoon Cho and Dong-Guk Han. 2020. Single-Trace Attacks on the Message Encoding of Lattice-Based KEMs . Cryptology ePrint Archive Report 2020\/992. Retrieved June 9 2021 from https:\/\/eprint.iacr.org\/2020\/992."},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.3837\/tiis.2013.05.009"},{"key":"e_1_3_2_63_2","unstructured":"Zhuang Xu Owen Pemberton Sujoy Sinha Roy and David Oswald. 2020. Magnifying Side-Channel Leakage of Lattice- Based Cryptosystems with Chosen Ciphertexts: The Case Study of Kyber . Cryptology ePrint Archive Report 2020\/912. Retrieved June 9 2021 from https:\/\/eprint.iacr.org\/2020\/912."},{"key":"e_1_3_2_64_2","first-page":"1","volume-title":"Proceedings of the International Conference on Smart Card Research and Advanced Applications","author":"Yang Guang","year":"2018","unstructured":"Guang Yang, Huizhong Li, Jingdian Ming, and Yongbin Zhou. 2018. Convolutional neural network based sidechannel attacks in time-frequency representations. In Proceedings of the International Conference on Smart Card Research and Advanced Applications. Springer, 1\u201317."},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2020.2981133"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382230"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2013.04.008"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476799","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476799","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:20Z","timestamp":1750268960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,18]]},"references-count":66,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11,30]]}},"alternative-id":["10.1145\/3476799"],"URL":"https:\/\/doi.org\/10.1145\/3476799","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,18]]},"assertion":[{"value":"2021-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}