{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:14Z","timestamp":1740142754664,"version":"3.37.3"},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:00:00Z","timestamp":1622592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2018YFA0704701","2020YFA0309705"],"award-info":[{"award-number":["2018YFA0704701","2020YFA0309705"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Major Program of Guangdong Basic and Applied Research","award":["2019B030302008"],"award-info":[{"award-number":["2019B030302008"]}]},{"DOI":"10.13039\/501100018532","name":"Major Scientific and Technological Innovation Project of Shandong Province","doi-asserted-by":"publisher","award":["2019JZZY010133"],"award-info":[{"award-number":["2019JZZY010133"]}],"id":[{"id":"10.13039\/501100018532","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,8,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>NewHope cryptosystem is one of the second-round submissions of the National Institute of Standards and Technology post-quantum cryptography standardization process, which is a suite of two key encapsulation mechanisms based on the ring-learning with errors (LWE) problem. It has received much attention from the research community due to its small key size and high efficiency. Recently, three key mismatch attacks are proposed against NewHope under the condition of key reuse. They do not solve the ring-LWE instance directly but exploit the leakage of secret information. As far as we know, the best result is given by Okada et al. ((2020) Improving Key Mismatch Attack on NewHope with Fewer Queries. In Proc. of the 25th Australasian Conf. on Information Security and Privacy, Perth, WA, Australia, November 30\u2013December 2, pp. 505\u2013524. Springer Cham, Switzerland), which recovers the whole secret with a success probability of $97\\%$ and $233,803$ average queries. In this paper, we further improve the key mismatch attack of NewHope by reducing the average queries to $106,577$ and raising the success probability to $100\\%$. Moreover, we analyze the key mismatch attack without key reuse for the first time and we propose a combinatorial attack against NewHope1024. The total complexity of the combinatorial attack is $2^{253}$, which is lower than the complexity of primal attack and the claimed security strength of NewHope1024.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab058","type":"journal-article","created":{"date-parts":[[2021,5,27]],"date-time":"2021-05-27T11:20:23Z","timestamp":1622114423000},"page":"2209-2220","source":"Crossref","is-referenced-by-count":1,"title":["A Refinement of Key Mismatch Attack on NewHope"],"prefix":"10.1093","volume":"65","author":[{"given":"Xue","family":"Zhang","sequence":"first","affiliation":[{"name":"Institute for Advanced Study , Tsinghua University, Beijing 100084, China"}]},{"given":"Zhongxiang","family":"Zheng","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study , Tsinghua University, Beijing 100084, China"}]},{"given":"Anyu","family":"Wang","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study , Tsinghua University, Beijing 100084, China"}]}],"member":"286","published-online":{"date-parts":[[2021,6,2]]},"reference":[{"key":"2022081612471371100_ref1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0036144598347011","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"41","author":"Shor","year":"1999","journal-title":"SIAM Rev."},{"key":"2022081612471371100_ref2","first-page":"84","article-title":"On Lattices, Learning with Errors, Random Linear Codes, and Cryptography","volume-title":"Proc. of the 37th Annual ACM Symposium on Theory of Computing","author":"Regev","year":"2005"},{"key":"2022081612471371100_ref3","first-page":"1","article-title":"On Ideal Lattices and Learning with Errors over Rings","volume-title":"Proc. of EUROCRYPT 2010","author":"Lyubashevsky","year":"2010"},{"key":"2022081612471371100_ref4","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":"Des. Codes Cryptogr."},{"volume-title":"NIST PQC Submission: NewHope - algorithm specifications and supporting documentation","year":"2019","author":"Alkim","key":"2022081612471371100_ref5"},{"key":"2022081612471371100_ref6","first-page":"327","article-title":"Post-quantum Key Exchange: A New Hope","volume-title":"Proc. of the 25th USENIX Conf. on Security Symposium","author":"Alkim","year":"2016"},{"key":"2022081612471371100_ref7","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/978-3-540-24676-3_31","article-title":"Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data","volume-title":"Proc. of EUROCRYPT 2004","author":"Dodis","year":"2004"},{"key":"2022081612471371100_ref8","first-page":"1157","article-title":"NewHope without reconciliation","volume":"2016","author":"Alkim","year":"2016","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2022081612471371100_ref9","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-319-70500-2_12","article-title":"A Modular Analysis of the Fujisaki-Okamoto Transformation","volume-title":"Proc. of the 15th Theory of Cryptography Conf.","author":"Hofheinz","year":"2017"},{"key":"2022081612471371100_ref10","first-page":"1","article-title":"Leakage of Signal Function with Reused Keys in RLWE Key Exchange","volume-title":"Proc. of the 2017 IEEE Int. Conf. on Communications","author":"Ding","year":"2017"},{"key":"2022081612471371100_ref11","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/978-3-319-93638-3_27","article-title":"Complete Attack on RLWE Key Exchange with Reused Keys, Without Signal Leakage","volume-title":"Proc. of the 23rd Australasian Conf. on Information Security and Privacy","author":"Ding","year":"2018"},{"key":"2022081612471371100_ref12","first-page":"163","article-title":"Key Reuse Attack on NewHope Key Exchange Protocol","volume-title":"Proc. of the 21st Int. Conf. on Information Security and Cryptology","author":"Liu","year":"2018"},{"key":"2022081612471371100_ref13","first-page":"272","article-title":"Assessment of the Key-Reuse Resilience of NewHope","volume-title":"Proc. of CT-RSA 2019","author":"Bauer","year":"2019"},{"key":"2022081612471371100_ref14","first-page":"504","article-title":"A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope","volume-title":"Proc. of the 24th European Symposium on Research in Computer Security","author":"Qin","year":"2019"},{"key":"2022081612471371100_ref15","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/978-3-030-55304-3_26","article-title":"Improving Key Mismatch Attack on NewHope with Fewer Queries","volume-title":"Proc. of the 25th Australasian Conf. on Information Security and Privacy","author":"Okada","year":"2020"},{"key":"2022081612471371100_ref16","first-page":"297","article-title":"Revisiting the Expected Cost of Solving uSVP and Applications to LWE","volume-title":"Proc. of ASIACRYPT 2017","author":"Albrecht","year":"2017"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/8\/2209\/45329756\/bxab058.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/8\/2209\/45329756\/bxab058.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T12:48:43Z","timestamp":1660654123000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/65\/8\/2209\/6291064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,2]]},"references-count":16,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,6,2]]},"published-print":{"date-parts":[[2022,8,11]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab058","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2022,8]]},"published":{"date-parts":[[2021,6,2]]}}}