{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T07:47:17Z","timestamp":1762069637327,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2022,10,4]],"date-time":"2022-10-04T00:00:00Z","timestamp":1664841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&amp;D Program of China","award":["2021YFB3100100","62002385","61972413","2021M703321"],"award-info":[{"award-number":["2021YFB3100100","62002385","61972413","2021M703321"]}]},{"name":"National Natural Science Foundation of China","award":["2021YFB3100100","62002385","61972413","2021M703321"],"award-info":[{"award-number":["2021YFB3100100","62002385","61972413","2021M703321"]}]},{"name":"China Postdoctoral Science Foundation","award":["2021YFB3100100","62002385","61972413","2021M703321"],"award-info":[{"award-number":["2021YFB3100100","62002385","61972413","2021M703321"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Research on the security of lattice-based public-key encryption schemes against misuse attacks is an important part of the cryptographic assessment of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process. In particular, many NIST-PQC cryptosystems follow the same meta-cryptosystem. At EUROCRYPT 2019, Ba\u02d8etu et al. mounted a classical key recovery under plaintext checking attacks (KR-PCA) and a quantum key recovery under chosen ciphertext attacks (KR-CCA). They analyzed the security of the weak version of nine submissions to NIST. In this paper, we focus on learning with error (LWE)-based FrodoPKE, whose IND-CPA security is tightly related to the hardness of plain LWE problems. We first review the meta-cryptosystem and quantum algorithm for solving quantum LWE problems. Then, we consider the case where the noise follows a discrete Gaussian distribution and recompute the success probability for quantum LWE by using Hoeffding bound. Finally, we give a quantum key recovery algorithm based on LWE under CCA attack and analyze the security of Frodo. Compared with the existing work of Ba\u02d8etu et al., our method reduces the number of queries from 22 to 1 with the same success probability.<\/jats:p>","DOI":"10.3390\/e24101418","type":"journal-article","created":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T04:04:56Z","timestamp":1665201896000},"page":"1418","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Quantum Misuse Attack on Frodo"],"prefix":"10.3390","volume":"24","author":[{"given":"Yaru","family":"Wang","sequence":"first","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}]},{"given":"Haodong","family":"Jiang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}]},{"given":"Zhi","family":"Ma","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,4]]},"reference":[{"key":"ref_1","first-page":"1277","article-title":"Quantum computing","volume":"10","author":"Wei","year":"2017","journal-title":"Sci. Sin."},{"key":"ref_2","unstructured":"Shor, P. (1994, January 20\u201322). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, NM, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Diffie","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_5","unstructured":"Nist: National Institute for Standards and Technology (2017, January 03). Post Quantum Crypto Project, Available online: https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/round-1-submissions."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Oded, R. (2009). Lattice-based cryptography. Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"ref_7","unstructured":"Eiichiro, F., and Tatsuaki, O. (1999). Secure integration of asymmetric and symmetric encryption schemes. Advances in Cryptology\u2014CRYPTO, Springer."},{"key":"ref_8","unstructured":"Aurelien, G., Simon, M., and Guenael, R. (2020). Attack on lac key exchange in misuse situation. Cryptology and Network Security, Springer."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Ding, J.T., Fluhrer, S., and Rv, S. (2018). Complete attack on rlwe key exchange with reused keys, without signal leakage. Information Security and Privacy, Springer.","DOI":"10.1007\/978-3-319-93638-3_27"},{"key":"ref_10","first-page":"1343","article-title":"An efficient key mismatch attack on the nist second round candidate kyber","volume":"2019","author":"Qin","year":"2019","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_11","unstructured":"Satoshi, O., Yuntao, W., and Tsuyoshi, T. (2018). Improving key mismatch attack on newhope with fewer queries. Information Security and Privacy, Springer."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Qin, Y., Cheng, C., and Ding, J.T. (2019). A complete and optimized key mismatch attack on nist candidate newhope. Computer Security\u2013ESORICS, Springer.","DOI":"10.1007\/978-3-030-29962-0_24"},{"key":"ref_13","first-page":"283","article-title":"Small leaks sink a great ship: An evaluation of key reuse resilience of pqc third round finalist ntru-hrss","volume":"2021","author":"Zhang","year":"2021","journal-title":"Inf. Commun. Secur."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Daniel, B. (1998). Chosen ciphertext attacks against protocols based on the rsa encryption standard pkcs #1. Advances in Cryptology\u2013CRYPTO, Springer.","DOI":"10.1007\/BFb0055716"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1504\/IJACT.2010.038308","article-title":"On reusing ephemeral keys in diffie-hellman key agreement protocols","volume":"2","author":"Menezes","year":"2010","journal-title":"Int. Appl. Cryptogr."},{"key":"ref_16","first-page":"85","article-title":"Cryptanalysis of ring-lwe based key exchange with key share reuse","volume":"2016","author":"Fluhrer","year":"2016","journal-title":"Cryptol. ePrint Arch."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ding, J., Alsayigh, S., Saraswathy, R.V., Fluhrer, S., and Lin, X. (2017, January 21\u201325). Leakage of signal function with reused keys in rlwe key exchange. Proceedings of the ICC 2017\u20142017 IEEE International Conference on Communications, Paris, France.","DOI":"10.1109\/ICC.2017.7996806"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bauer, A., Gilbert, H., Renault, G., and Rossi, M. (2019, January 4\u20138). Assessment of the key-reuse resilience of newhope. Proceedings of the Cryptographers Track at the Rsa Conference, San Francisco, CA, USA.","DOI":"10.1007\/978-3-030-12612-4_14"},{"key":"ref_19","first-page":"327","article-title":"Post-quantum key exchange\u2014A new hope","volume":"1092","author":"Alkim","year":"2015","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_20","first-page":"92","article-title":"A systematic approach andanalysis ofkey mismatch attacks onlattice-based nist candidate kems","volume":"Volume 13093","author":"Qin","year":"2021","journal-title":"Advances in Cryptology\u2013ASIACRYPT"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"10","DOI":"10.3390\/cryptography4010010","article-title":"On quantum chosen-ciphertext attacks and learning with errors","volume":"4","author":"Gorjan","year":"2020","journal-title":"Cryptography"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"B\u0103etu, C., Durak, F.B., Huguenin-Dumittan, L., Talayhan, A., and Vaudenay, S. (2019, January 19\u201323). Misuse attacks on post-quantum cryptosystems. Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Darmstadt, Germany.","DOI":"10.1007\/978-3-030-17656-3_26"},{"key":"ref_23","unstructured":"Bundesamt f\u00fcr Sicherheit in der Informationstechnik (2022, January 01). BSI TR-021021: Cryptographic Mechanisms: Recommendations and Key Lengths, Version 2022-1. Available online: https:\/\/www.bsi.bund.de\/SharedDocs\/Downloads\/EN\/BSI\/Publications\/TechGuidelines\/TG02102\/BSI-TR-02102-1.pdf."},{"key":"ref_24","first-page":"319","article-title":"Better key sizes (and attacks) for lwe-based encryption","volume":"Volume 6558","author":"Lindner","year":"2011","journal-title":"Topics in Cryptology"},{"key":"ref_25","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":"Oded","year":"2009","journal-title":"J. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"032314","DOI":"10.1103\/PhysRevA.99.032314","article-title":"Learning with errors problem is easy with quantum samples","volume":"99","author":"Grilo","year":"2019","journal-title":"Phys. Rev. A"},{"key":"ref_27","unstructured":"Michael, J.K., Yishay, M., Dana, R., Ronitt, R., Schapire, R.E., and Linda, S. (1994, January 23\u201325). On the learnability of discrete distributions. Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montreal, QC, Canada."},{"key":"ref_28","first-page":"1","article-title":"An improved quantum algorithm for the quantum learning with errors problem","volume":"21","author":"Wang","year":"2022","journal-title":"Quantum Inf. Process."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1418\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:46:19Z","timestamp":1760143579000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,4]]},"references-count":28,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["e24101418"],"URL":"https:\/\/doi.org\/10.3390\/e24101418","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,10,4]]}}}