×

Quantum security analysis of Rocca. (English) Zbl 1542.81335

Summary: The recent developments in the creation of large-scale, commercially feasible quantum computers puts both symmetric and asymmetric encryption at risk. As they assess the security of 5G and beyond, the telecommunication standards groups are now inviting recommendations that take the threat posed by quantum adversaries into account. Rocca is the first cipher designed that complies with 6G specifications. In this paper we analyze the security of Rocca against quantum adversaries. We first construct the quantum circuit of Rocca and estimate the cost of implementing Grover’s algorithm for key recovery. We also compute the cost under the NISTs MAXDEPTH restriction. We then find a differential distinguisher for 5 and 6 rounds in secret key settings and related key settings respectively. In the nonce-respecting settings, we discover that Rocca is susceptible to a quantum forging attack with a complexity of \(\mathcal{O}(2^{75})\) in the \(Q2\) settings, i.e., if the adversary is given access to quantum superposition queries to the cryptographic oracle. This complexity is considerably less than the complexity of \(\mathcal{O}(2^{128})\) claimed by the authors. Thus we propose that the number of initialization rounds in Rocca can be reduced without compromising its security and the tag length should be increased to 256-bits.

MSC:

81P94 Quantum cryptography (quantum-theoretic aspects)
94A60 Cryptography

Software:

SNOW; AEGIS
Full Text: DOI

References:

[1] Almazrooie, M.; Samsudin, A.; Abdullah, R.; Mutter, KN, Quantum reversible circuit of AES-128, Quantum Inf. Process., 17, 5, 1-30 (2018) · Zbl 1395.81098 · doi:10.1007/s11128-018-1864-3
[2] Amy, M.; Maslov, D.; Mosca, M.; Roetteler, M., A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Trans. CAD Integr. Circuits Syst., 32, 6, 818-830 (2013) · doi:10.1109/TCAD.2013.2244643
[3] Anand, R.; Maitra, A.; Mukhopadhyay, S., Grover on SIMON, Quantum Inf. Process., 19, 9, 1-17 (2020) · Zbl 1509.81348 · doi:10.1007/s11128-020-02844-w
[4] Anand, R., Maitra, A., Mukhopadhyay, S.: Evaluation of quantum cryptanalysis on speck. In: International Conference on Cryptology in India, pp. 395-413. Springer, Cham (2020) · Zbl 1500.81021
[5] Anand, R., Maitra, A., Maitra, S., Mukherjee, C.S., Mukhopadhyay, S.: Quantum resource estimation for FSR based symmetric ciphers and related Grover’s attacks. In: International Conference on Cryptology in India, pp. 179-198. Springer, Cham (2021) · Zbl 1522.81068
[6] Baksi, A.; Jang, K.; Song, G.; Seo, H.; Xiang, Z., Quantum implementation and resource estimates for rectangle and knot, Quantum Inf. Process., 20, 12, 1-24 (2021) · Zbl 1508.81646 · doi:10.1007/s11128-021-03307-6
[7] Bathe, B.; Anand, R.; Dutta, S., Evaluation of Grover’s algorithm toward quantum cryptanalysis on ChaCha, Quantum Inf. Process., 20, 12, 1-19 (2021) · Zbl 1508.81416 · doi:10.1007/s11128-021-03322-7
[8] Bonnetain, X., Hosoyamada, A., Naya-Plasencia, M., Sasaki, Y., Schrottenloher, A.: Quantum attacks without superposition queries: the offline Simon’s algorithm. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 552-583. Springer, Cham (2019) · Zbl 1456.94052
[9] Bonnetain, X.; Naya-Plasencia, M.; Schrottenloher, A., Quantum security analysis of AES, IACR Trans. Symmetric Cryptol., 2019, 2, 55-93 (2019) · doi:10.46586/tosc.v2019.i2.55-93
[10] Boyer, M.; Brassard, G.; Høyer, P.; Tapp, A., Tight bounds on quantum searching, Fortschr. Phys. Progress Phys., 46, 4-5, 493-505 (1998) · doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
[11] Dworkin, M.: Recommendation for block cipher modes of operation: Galois/Counter Mode (GCM) and GMAC. In: NIST SP 800-38D (2007). doi:10.6028/NIST.SP.800-38D, https://csrc.nist.gov/publications/detail/sp/800-38d/final
[12] Ekdahl, P., Johansson, T., Maximov, A., Yang, J.: A new SNOW stream cipher called SNOW-V. Cryptology ePrint Archive (2018)
[13] Fettweis, GP; Boche, H., On 6G and trustworthiness, Commun. ACM, 65, 4, 48-49 (2022) · doi:10.1145/3512996
[14] Fowler, A.G.: Time-optimal quantum computation (2012). arXiv preprint arXiv:1210.4626
[15] Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: Post-quantum Cryptography, pp. 29-43. Springer, Cham (2016) · Zbl 1405.81026
[16] Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212-219 (1996) · Zbl 0922.68044
[17] Hosoyamada, A., Sasaki, Y.: Quantum Demiric-Selcuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions. In: International Conference on Security and Cryptography for Networks, pp. 386-403. Springer, Cham (2018) · Zbl 1514.81107
[18] Hosoyamada, A., Sasaki, Y.: Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In: Cryptographer’s Track at the RSA Conference, pp. 198-218. Springer, Cham (2018) · Zbl 1507.94040
[19] Huang, Z., Sun, S.: Synthesizing quantum circuits of AES with lower T-depth and less qubits. Cryptology ePrint Archive (2022)
[20] Ishizu, K.: Beyond 5G/6G architecture and key technologies to realize future life in 2035—overview of NICT beyond 5G/6G white paper and its background. In: IEICE Technical Report; IEICE Tech. Rep
[21] Jang, K., Baksi, A., Song, G., Kim, H., Seo, H., Chattopadhyay, A.: Quantum analysis of AES. Cryptology ePrint Archive (2022)
[22] Jang, K., Choi, S., Kwon, H., Seo, H.: Grover on SPECK: quantum resource estimates. Cryptology ePrint Archive (2020)
[23] Jang, K., Kim, H., Eum, S., Seo, H.: Grover on GIFT. Cryptology ePrint Archive (2020)
[24] Jang, K., Baksi, A., Breier, J., Seo, H., Chattopadhyay, A.: Quantum implementation and analysis of DEFAULT. Cryptology ePrint Archive (2022)
[25] Jang, K.; Song, G.; Kim, H.; Kwon, H.; Kim, H.; Seo, H., Efficient implementation of present and gift on quantum computers, Appl. Sci., 11, 11, 4776 (2021) · doi:10.3390/app11114776
[26] Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing Grover oracles for quantum key search on AES and LowMC. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 280-310. Springer, Cham (2020) · Zbl 1492.81042
[27] Jean, J., Nikolić, I.: Efficient design strategies based on the AES round function. In: International Conference on Fast Software Encryption, pp. 334-353. Springer, Berlin, Heidelberg (2016) · Zbl 1387.94085
[28] Kaplan, M.: Quantum attacks against iterated block ciphers. arXiv preprint arXiv:1410.1434 (2014)
[29] Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Annual International Cryptology Conference, pp. 207-237. Springer, Berlin, Heidelberg (2016) · Zbl 1391.94766
[30] Kaplan, M.; Leurent, G.; Leverrier, A.; Naya-Plasencia, M., Quantum differential and linear cryptanalysis, IACR Trans. Symmetric Cryptol., 2016, 71-94 (2015) · Zbl 1391.94766
[31] Kuwakado, H., Morii, M.: Security on the quantum-type Even-Mansour cipher. In 2012 International Symposium on Information Theory and its Applications, pp. 312-316. IEEE (2012)
[32] Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: 2010 IEEE International Symposium on Information Theory, pp. 2682-2685. IEEE (2010)
[33] Langenberg, B.; Pham, H.; Steinwandt, R., Reducing the cost of implementing the advanced encryption standard as a quantum circuit, IEEE Trans. Quantum Eng., 1, 1-12 (2020) · doi:10.1109/TQE.2020.2965697
[34] Latva-aho, M., Leppänen, K., Clazzer, F., Munari, A.: Key drivers and research challenges for 6G ubiquitous wireless intelligence (2020)
[35] Leander, G., May, A.: Grover meets Simon-quantumly attacking the FX-construction. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 161-178. Springer, Cham (2017) · Zbl 1380.94109
[36] Mitchell, CJ, The impact of quantum computing on real-world security: a 5G case study, Comput. Secur., 93, 101825 (2020) · doi:10.1016/j.cose.2020.101825
[37] Nathan, W.; Roetteler, M., Quantum arithmetic and numerical analysis using repeat-until-success circuits, Quantum Inf. Comput., 16, 1-2, 134-178 (2016)
[38] Nikolic, I.: Tiaoxin-346 (version 2.1). CAESAR competition. https://competitions.cr.yp.to/round3/tiaoxinv21.pdf
[39] Sakamoto, K.; Liu, F.; Nakano, Y.; Kiyomoto, S.; Isobe, T., Rocca: an efficient AES-based encryption scheme for beyond 5G, IACR Trans. Symmetric Cryptol., 2021, 1-30 (2021)
[40] Sakamoto, K., Liu, F., Nakano, Y., Kiyomoto, S., Isobe, T.: Rocca: an efficient AES-based encryption scheme for beyond 5G (Full version). Cryptology ePrint Archive (2022)
[41] Simon, DR, On the power of quantum computation, SIAM J. Comput., 26, 5, 1474-1483 (1997) · Zbl 0883.03024 · doi:10.1137/S0097539796298637
[42] Ulitzsch, V., Seifert, J.P.: Breaking the quadratic barrier: quantum cryptanalysis of Milenage, telecommunications’ cryptographic backbone. Cryptology ePrint Archive (2022)
[43] Wu, H., Preneel, B.: AEGIS: a fast authenticated encryption algorithm (v1.1) CAESAR competition. https://competitions.cr.yp.to/round3/aegisv11.pdf · Zbl 1339.94083
[44] Xiang, Z.; Zeng, X.; Lin, D.; Bao, Z.; Zhang, S., Optimizing implementations of linear layers, IACR Trans. Symmetric Cryptol., 2020, 120-145 (2020) · doi:10.46586/tosc.v2020.i2.120-145
[45] Xu, Y.; Liu, W.; Yu, W., Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms, Quantum Inf. Process., 20, 4, 1-21 (2021) · Zbl 1509.81434 · doi:10.1007/s11128-021-03036-w
[46] Yang, J.; Johansson, T., An overview of cryptographic primitives for possible use in 5G and beyond, Sci. China Inf. Sci., 63, 12, 1-22 (2020) · doi:10.1007/s11432-019-2907-4
[47] Zou, J., Wei, Z., Sun, S., Liu, X., Wu, W.: Quantum circuit implementations of AES with fewer qubits. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 697-726. Springer, Cham (2020) · Zbl 1521.81059
[48] The ZUC-256 Stream Cipher. http://www.is.cas.cn/ztzl2016/zouchongzhi/201801/W020180126529970733243.pdf
[49] https://csrc.nist.gov/csrc/media/projects/post-quantum-cryptography/documents/call-for-proposals-final-dec-2016.pdf
[50] https://qiskit.org/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.