{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T07:58:15Z","timestamp":1768463895391,"version":"3.49.0"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T00:00:00Z","timestamp":1671148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,1,17]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The National Institute of Standards and Technology (NIST) has been working on standardization of post-quantum cryptography and is approaching the end of round-3 evaluation of algorithms. Key reuse security evaluation is an important part of algorithm evaluation. In order to evaluate the key reuse security of candidate IND-CPA PKEs, at Eurocrypt\u201919, B$\\breve{\\text{a}}$etu et al. proposed a classical key recovery under plaintext checking attack (KR-PCA) which can recover the reused secret keys by querying an oracle thousands of times. However, the method does not work for cryptosystems which shorten ciphertexts by rounding off the low bits, such as round-3 finalists Kyber and Saber. Subsequently, Dumittan and Vaudenay (ACNS\u201920) and Qin et al. (ASIACRYPT\u201921) came up with new effective methods, which require carefully constructed queries. In this paper, we propose an automatic method to recover the reused secret keys of IND-CPA PKEs in Kyber and Saber. Instead of constructing queries carefully, our method uses automated search combined with an optimized bruteforce. The effect and cost of the method depend on the specific parameters. In particular, we can recover the secret keys after thousands of queries in all parameter sets, which is comparable with the current best result.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac176","type":"journal-article","created":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T14:00:50Z","timestamp":1671285650000},"page":"323-337","source":"Crossref","is-referenced-by-count":1,"title":["Key Reuse Attacks on Post-quantum Cryptosystems, Revisited"],"prefix":"10.1093","volume":"67","author":[{"given":"Ke","family":"Wang","sequence":"first","affiliation":[{"name":"Department of Cryptography and Technology, Beijing Electronic Science and Technology Institute , Beijing, China"},{"name":"Key Laboratory of Cryptography of Zhejiang Province, Hangzhou Normal University , Hangzhou 311121 , China"}]},{"given":"Zhenfeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences , Beijing, China"}]},{"given":"Haodong","family":"Jiang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing , Zhengzhou, Henan , China"}]},{"given":"Huiqin","family":"Xie","sequence":"additional","affiliation":[{"name":"Department of Cryptography and Technology, Beijing Electronic Science and Technology Institute , Beijing, China"}]},{"given":"Yanjun","family":"Li","sequence":"additional","affiliation":[{"name":"North China Institute of Computing Technology , Beijing, China"}]},{"given":"Ying","family":"Sun","sequence":"additional","affiliation":[{"name":"Department of Cryptography and Technology, Beijing Electronic Science and Technology Institute , Beijing, China"}]},{"given":"Lidong","family":"Han","sequence":"additional","affiliation":[{"name":"Key Laboratory of Cryptography of Zhejiang Province, Hangzhou Normal University , Hangzhou 311121 , China"}]}],"member":"286","published-online":{"date-parts":[[2022,12,16]]},"reference":[{"key":"2024012011485597900_ref1","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","volume-title":"Proceedings 35th annual symposium on foundations of computer science, Santa Fe, New Mexico, USA, 20\u201322 November","author":"Shor","year":"1994"},{"key":"2024012011485597900_ref2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-88702-7","volume-title":"Post-quantum cryptography","author":"Bernstein","year":"2009"},{"issue":"7671","key":"2024012011485597900_ref3","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1038\/nature23461","article-title":"Post-quantum cryptography","volume":"549","author":"Bernstein","year":"2017","journal-title":"Nature"},{"key":"2024012011485597900_ref4","volume-title":"Announcing request for nominations for public-key post-quantum cryptographic algorithms","author":"National Institute of Standards and Technology","year":"2016"},{"key":"2024012011485597900_ref5","volume-title":"Post-quantum cryptography round 3 submissions","author":"National Institute of Standards and Technology","year":"2020"},{"key":"2024012011485597900_ref6","first-page":"1","volume-title":"Annual international conference on the theory and applications of cryptographic techniques, Monaco\/French Riviera, 30 May-3 June","author":"Lyubashevsky","year":"2010"},{"issue":"6","key":"2024012011485597900_ref7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and cryptography","volume":"56","author":"Regev","year":"2009","journal-title":"Journal of the ACM (JACM)"},{"key":"2024012011485597900_ref8","first-page":"272","volume-title":"Cryptographers\u2019 track at the RSA conference, San Francisco, CA, USA, 4-8 March","author":"Bauer","year":"2019"},{"key":"2024012011485597900_ref9","first-page":"747","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"B\u01ceetu","year":"2019"},{"key":"2024012011485597900_ref10","volume-title":"Post-quantum cryptography round 1 submissions","author":"National Institute of Standards and Technology","year":"2018"},{"key":"2024012011485597900_ref11","article-title":"Cryptanalysis of ring-LWE based key exchange with key share reuse","author":"Fluhrer","year":"2016","journal-title":"Cryptology ePrint Archive."},{"key":"2024012011485597900_ref12","first-page":"2","volume-title":"International Conference on Information and Communications Security, Sydney, Australia, 9-11 November","author":"Hall","year":"1999"},{"key":"2024012011485597900_ref13","volume-title":"Information, coding and mathematics","author":"McEliece","year":"2002"},{"key":"2024012011485597900_ref14","first-page":"565","volume-title":"IACR International Workshop on Public Key Cryptography, Beijing, China, 14-17 April","author":"D\u2019Anvers","year":"2019"},{"key":"2024012011485597900_ref15","first-page":"82","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 8-12 December","author":"Guo","year":"2019"},{"key":"2024012011485597900_ref16","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-030-57808-4_11","volume-title":"International Conference on Applied Cryptography and Network Security, Rome, Italy, 19-22 October","author":"Huguenin-Dumittan","year":"2020"},{"key":"2024012011485597900_ref17","first-page":"92","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 6-10 December","author":"Qin","year":"2021"},{"key":"2024012011485597900_ref18","first-page":"21","volume-title":"Workshop on Cybersecurity in a Post-Quantum World, Gaithersburg, Maryalnd, 2-3 April","author":"Kirkwood","year":"2015"},{"key":"2024012011485597900_ref19","first-page":"467","volume-title":"Australasian conference on information security and privacy, Wollongong, NSW, Australia, 11-13 July","author":"Ding","year":"2018"},{"key":"2024012011485597900_ref20","first-page":"203","volume-title":"International conference on cryptology in Africa, Marrakesh, Morocco, 7-9 May","author":"Bernstein","year":"2018"},{"key":"2024012011485597900_ref21","first-page":"192","volume-title":"International conference on selected areas in cryptography, Ottawa, ON, Canada, 16\u201318 August","author":"Saarinen","year":"2017"},{"key":"2024012011485597900_ref22","first-page":"1","volume-title":"2017 IEEE international conference on communications, Paris, France, 21\u201325 May","author":"Ding","year":"2017"},{"key":"2024012011485597900_ref23","volume-title":"A simple provably secure key exchange scheme based on the learning with errors problem","author":"Ding","year":"2012"},{"key":"2024012011485597900_ref24","first-page":"163","volume-title":"International conference on information security and cryptology, Seoul, South Korea, 28-30 November","author":"Liu","year":"2018"},{"key":"2024012011485597900_ref25","first-page":"327","volume-title":"25th USENIX Security Symposium","author":"Erdem","year":"2016"},{"issue":"11","key":"2024012011485597900_ref26","doi-asserted-by":"crossref","first-page":"1584","DOI":"10.1109\/TC.2018.2808527","article-title":"Practical randomized RLWE-based key exchange against signal leakage attack","volume":"67","author":"Gao","year":"2018","journal-title":"IEEE Trans. Comput."},{"key":"2024012011485597900_ref27","first-page":"370","volume-title":"International Conference on Cryptology in Africa, Rabat, Morocco, 9-11 July","author":"Wang","year":"2019"},{"key":"2024012011485597900_ref28","volume-title":"Newhope: Algorithm specifcations and supporting documentation","author":"Avanzi","year":"2017"},{"key":"2024012011485597900_ref29","first-page":"504","volume-title":"European symposium on research in computer security, Luxembourg, 23-27 September","author":"Qin","year":"2019"},{"key":"2024012011485597900_ref30","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/978-3-030-55304-3_26","volume-title":"Australasian Conference on Information Security and Privacy, Perth, WA, Australia, 30 November - 2 December","author":"Okada","year":"2020"},{"key":"2024012011485597900_ref31","doi-asserted-by":"crossref","first-page":"2209","DOI":"10.1093\/comjnl\/bxab058","article-title":"A Refinement of Key Mismatch Attack on NewHope","volume":"65","author":"Zhang","year":"2021","journal-title":"The Computer Journal"},{"key":"2024012011485597900_ref32","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/978-3-030-65411-5_27","volume-title":"International Conference on Cryptology and Network Security, Vienna, Austria, 14-16 December","author":"Greuet","year":"2020"},{"key":"2024012011485597900_ref33","first-page":"381","volume-title":"International Conference on Provable Security, Singapore, 29 November-1 December","author":"Wang","year":"2020"},{"key":"2024012011485597900_ref34","first-page":"182","volume-title":"International Conference on Information Security and Cryptology, Seoul, South Korea, 2-4 December","author":"Vacek","year":"2020"},{"key":"2024012011485597900_ref35","first-page":"402","volume-title":"International Conference on Provable Security, Singapore, 29 November-1 December","author":"Wang","year":"2020"},{"key":"2024012011485597900_ref36","first-page":"155","volume-title":"International Conference on Provable Security, Guangzhou, China, 5-8 November","author":"Okada","year":"2021"},{"key":"2024012011485597900_ref37","first-page":"283","volume-title":"International Conference on Information and Communications Security, Chongqing, China, 19-21 November","author":"Zhang","year":"2021"},{"key":"2024012011485597900_ref38","first-page":"33","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 6-10 December","author":"Xagawa","year":"2021"},{"issue":"3","key":"2024012011485597900_ref39","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","article-title":"Worst-case to average-case reductions for module lattices","volume":"75","author":"Langlois","year":"2015","journal-title":"Designs, Codes and Cryptography"},{"key":"2024012011485597900_ref40","first-page":"719","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 15-19 April","author":"Banerjee","year":"2012"},{"key":"2024012011485597900_ref41","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1109\/EuroSP.2018.00032","volume-title":"2018 IEEE European Symposium on Security and Privacy, London, United Kingdom, 24-26 April","author":"Bos","year":"2018"},{"key":"2024012011485597900_ref42","first-page":"68","volume-title":"International Conference on Selected Areas in Cryptography, Burnaby, BC, Canada, 14-16 August","author":"P\u00f6ppelmann","year":"2013"},{"key":"2024012011485597900_ref43","first-page":"333","volume-title":"Proceedings of the forty-first annual ACM symposium on Theory of computing, Bethesda, MD, USA, 31 May - 2 June","author":"Peikert","year":"2009"},{"key":"2024012011485597900_ref44","first-page":"282","volume-title":"International Conference on Cryptology in Africa, Marrakesh, Morocco, 7-9 May","author":"D\u2019Anvers","year":"2018"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/323\/56167768\/bxac176.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/323\/56167768\/bxac176.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T21:43:18Z","timestamp":1728250998000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/1\/323\/6918741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,16]]},"references-count":44,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12,16]]},"published-print":{"date-parts":[[2024,1,17]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac176","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,1]]},"published":{"date-parts":[[2022,12,16]]}}}