Security comparisons and performance analyses of post-quantum signature algorithms. (English) Zbl 1492.81045
Sako, Kazue (ed.) et al., Applied cryptography and network security. 19th international conference, ACNS 2021, Kamakura, Japan, June 21–24, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12727, 424-447 (2021).
Summary: Quantum computing challenges the computational hardness assumptions anchoring the security of public-key ciphers, such as the prime factorization and the discrete logarithm problem. To prepare for the quantum era and withstand the attacks equipped with quantum computing, the security and cryptography communities are designing new quantum-resistant public-key ciphers. National Institute of Standards and Technology (NIST) is collecting and standardizing the post-quantum ciphers, similarly to its past involvements in establishing DES and AES as symmetric cipher standards. The NIST finalist algorithms for public-key signatures are Dilithium, Falcon, and Rainbow. Finding common ground to compare these algorithms can be difficult because of their design, the underlying computational hardness assumptions (lattice based vs. multivariate based), and the different metrics used for security strength analyses in the previous research (qubits vs. quantum gates). We overcome such challenges and compare the security and the performances of the finalist post-quantum ciphers of Dilithium, Falcon, and Rainbow. For security comparison analyses, we advance the prior literature by using the depth-width cost for quantum circuits (DW cost) to measure the security strengths and by analyzing the security in Universal Quantum Gate Model and with Quantum Annealing. For performance analyses, we compare the algorithms’ computational loads in the execution time as well as the communication costs and implementation overheads when integrated with Transport Layer Security (TLS) and Transmission Control Protocol (TCP)/Internet Protocol (IP). Our work presents a security comparison and performance analysis as well as the trade-off analysis to inform the post-quantum cipher design and standardization to protect computing and networking in the post-quantum era.
For the entire collection see [Zbl 1482.94011].
For the entire collection see [Zbl 1482.94011].
MSC:
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
| 81P68 | Quantum computation |
| 94A62 | Authentication, digital signatures and secret sharing |
| 94A60 | Cryptography |
| 81P70 | Quantum coding (general) |
| 81P73 | Computational stability and error-correcting codes for quantum computation and communication processing |
Keywords:
quantum-resistant cryptography; post-quantum cryptography; quantum computing; public-key cipher; digital signature algorithms; security analysis; performance analysisReferences:
| [1] | ETSI-Standards. https://www.etsi.org. Accessed 1 Sept 2020 |
| [2] | Wireshark tool. https://www.wireshark.org. Accessed 1 Sept 2020 |
| [3] | Workshops and timeline. https://csrc.nist.gov/projects/post-quantum-cryptography/workshops-and-timeline. Accessed 1 Sept 2020 |
| [4] | Alagic, G., et al.: Status report on the first round of the NIST post-quantum cryptography standardization process. US Department of Commerce, National Institute of Standards and Technology (2019) |
| [5] | Alagic, G., et al.: Status report on the second round of the NIST post-quantum cryptography standardization process, NIST, Technical report, July 2020 |
| [6] | Alicki, R.; Fannes, M.; Horodecki, M., On thermalization in Kitaev’s 2D model, J. Phys. A: Math. Theoret., 42, 6, 065303 (2009) · Zbl 1159.81011 · doi:10.1088/1751-8113/42/6/065303 |
| [7] | Alicki, R.; Horodecki, M.; Horodecki, P.; Horodecki, R., On thermal stability of topological qubit in Kitaev’s 4D model, Open Syst. Inf. Dyn., 17, 1, 1-20 (2010) · Zbl 1190.81027 · doi:10.1142/S1230161210000023 |
| [8] | Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange-a new hope. In: 25th USENIX Security Symposium (USENIX Security 16), pp. 327-343 (2016) |
| [9] | Alsina, D.; Latorre, JI, Experimental test of Mermin inequalities on a five-qubit quantum computer, Phys. Rev. A, 94, 1, 012314 (2016) · doi:10.1103/PhysRevA.94.012314 |
| [10] | Amin, MH, Consistency of the adiabatic theorem, Phys. Rev. Lett., 102, 22, 220401 (2009) · doi:10.1103/PhysRevLett.102.220401 |
| [11] | Basu, K., Soni, D., Nabeel, M., Karri, R.: NIST post-quantum cryptography-A hardware evaluation study. IACR Cryptology ePrint Archives, p. 47 (2019) |
| [12] | Bernstein, D.J.: Visualizing size-security tradeoffs for lattice-based encryption. IACR Cryptology ePrint Archives, p. 655 (2019) |
| [13] | Brassard, G.; Høyer, P.; Tapp, A., Quantum cryptanalysis of hash and claw-free functions, ACM SIGACT News, 28, 2, 14-19 (1997) · doi:10.1145/261342.261346 |
| [14] | Caelli, WJ; Dawson, EP; Rea, SA, PKI, elliptic curve cryptography, and digital signatures, Comput. Secur., 18, 1, 47-66 (1999) · doi:10.1016/S0167-4048(99)80008-X |
| [15] | Casanova, A., Faugere, J.C., Macario-Rat, G., Patarin, J., Perret, L., Ryckeghem, J.: GeMSS: a great multivariate short signature. Submission to NIST (2017) |
| [16] | Castelvecchi, D., IBM’s quantum cloud computer goes commercial, Nat. News, 543, 7644, 159 (2017) · doi:10.1038/nature.2017.21585 |
| [17] | Chen, L., et al.: Report on post-quantum cryptography, vol. 12. US Department of Commerce, National Institute of Standards and Technology (2016) |
| [18] | Cheung, D.; Høyer, P.; Wiebe, N., Improved error bounds for the adiabatic approximation, J. Phys. A: Math. Theoret., 44, 41, 415302 (2011) · Zbl 1251.81027 · doi:10.1088/1751-8113/44/41/415302 |
| [19] | Chuang, IL; Gershenfeld, N.; Kubinec, M., Experimental implementation of fast quantum searching, Phys. Rev. Lett., 80, 15, 3408 (1998) · doi:10.1103/PhysRevLett.80.3408 |
| [20] | Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. IACR Cryptology ePrint Archives 2020, 292 (2020) |
| [21] | Deutsch, DE, Quantum computational networks, Proc. R. Soc. Lond. A Math. Phys. Sci., 425, 1868, 73-90 (1989) · Zbl 0691.68054 |
| [22] | Ding, J.; Schmidt, D.; Ioannidis, J.; Keromytis, A.; Yung, M., Rainbow, a new multivariable polynomial signature scheme, Applied Cryptography and Network Security, 164-175 (2005), Heidelberg: Springer, Heidelberg · Zbl 1126.68393 · doi:10.1007/11496137_12 |
| [23] | Ducas, L., Crystals-dilithium: a lattice-based digital signature scheme, IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018, 238-268 (2018) · doi:10.46586/tches.v2018.i1.238-268 |
| [24] | Duong, DH; Tran, HTN, Choosing subfields for LUOV and lifting fields for rainbow, IET Inf. Secur., 14, 2, 196-201 (2020) · doi:10.1049/iet-ifs.2018.5288 |
| [25] | Durr, C., Hoyer, P.: A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014 (1996) |
| [26] | Finnila, AB; Gomez, M.; Sebenik, C.; Stenson, C.; Doll, JD, Quantum annealing: a new method for minimizing multidimensional functions, Chem. Phys. Lett., 219, 5-6, 343-348 (1994) · doi:10.1016/0009-2614(94)00117-0 |
| [27] | FIPS, P.: 186-4: Federal information processing standards publication. Digital Signature Standard (DSS). Information Technology Laboratory, National Institute of Standards and Technology (NIST), Gaithersburg, MD, pp. 20899-8900 (2013) |
| [28] | Fouque, P.A., et al.: Falcon: fast-Fourier lattice-based compact signatures over NTRU. Submission to the NIST’s post-quantum cryptography standardization process (2018) |
| [29] | Gao, YL; Chen, XB; Chen, YL; Sun, Y.; Niu, XX; Yang, YX, A secure cryptocurrency scheme based on post-quantum blockchain, IEEE Access, 6, 27205-27213 (2018) · doi:10.1109/ACCESS.2018.2827203 |
| [30] | Gottesman, D., Theory of fault-tolerant quantum computation, Phys. Rev. A, 57, 1, 127 (1998) · doi:10.1103/PhysRevA.57.127 |
| [31] | 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 |
| [32] | Hauke, P.; Katzgraber, HG; Lechner, W.; Nishimori, H.; Oliver, WD, Perspectives of quantum annealing: methods and implementations, Rep. Prog. Phys., 83, 5, 054401 (2020) · doi:10.1088/1361-6633/ab85b8 |
| [33] | Jacobson, V., Leres, C., McCanne, S.: TCPDUMP public repository (2003). http://www.tcpdump.org |
| [34] | Jaques, S.; Schanck, JM; Boldyreva, A.; Micciancio, D., Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE, Advances in Cryptology - CRYPTO 2019, 32-61 (2019), Cham: Springer, Cham · Zbl 1456.94090 · doi:10.1007/978-3-030-26948-7_2 |
| [35] | Kelly, J.: A preview of Bristlecone, Google’s new quantum processor. Google Research Blog 5 (2018) |
| [36] | Kipnis, A.; Patarin, J.; Goubin, L.; Stern, J., Unbalanced oil and vinegar signature schemes, Advances in Cryptology — EUROCRYPT ’99, 206-222 (1999), Heidelberg: Springer, Heidelberg · Zbl 0933.94031 · doi:10.1007/3-540-48910-X_15 |
| [37] | Kitaev, AY, Fault-tolerant quantum computation by anyons, Ann. Phys., 303, 1, 2-30 (2003) · Zbl 1012.81006 · doi:10.1016/S0003-4916(02)00018-0 |
| [38] | Messiah, A.: Quantum Mechanics: Translated [from the French] by J. Potter. North-Holland (1962) |
| [39] | Moses, T.: Quantum computing and cryptography. Entrust Inc., January 2009 |
| [40] | Nejatollahi, H.; Dutt, N.; Ray, S.; Regazzoni, F.; Banerjee, I.; Cammarota, R., Post-quantum lattice-based cryptography implementations: A survey, ACM Comput. Surv. (CSUR), 51, 6, 1-41 (2019) · doi:10.1145/3292548 |
| [41] | Ravi, P., Jhanwar, M.P., Howe, J., Chattopadhyay, A., Bhasin, S.: Exploiting determinism in lattice-based signatures: practical fault attacks on pqm4 implementations of NIST candidates. In: Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security, pp. 427-440 (2019) |
| [42] | Regev, O.; Dwork, C., Lattice-based cryptography, Advances in Cryptology - CRYPTO 2006, 131-141 (2006), Heidelberg: Springer, Heidelberg · Zbl 1161.94425 · doi:10.1007/11818175_8 |
| [43] | Rezakhani, A.; Kuo, WJ; Hamma, A.; Lidar, D.; Zanardi, P., Quantum adiabatic brachistochrone, Phys. Rev. Lett., 103, 8, 080502 (2009) · doi:10.1103/PhysRevLett.103.080502 |
| [44] | Rivest, RL; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 2, 120-126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342 |
| [45] | Shor, PW, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev., 41, 2, 303-332 (1999) · Zbl 1005.11507 · doi:10.1137/S0036144598347011 |
| [46] | Sikeridis, D., Kampanakis, P., Devetsikiotis, M.: Post-quantum authentication in TLS 1.3: a performance study. IACR Cryptology ePrint Archives, p. 71 (2020) |
| [47] | Stebila, D.; Mosca, M.; Avanzi, R.; Heys, H., Post-quantum key exchange for the internet and the open quantum safe project, Selected Areas in Cryptography - SAC 2016, 14-37 (2017), Cham: Springer, Cham · Zbl 1412.94213 · doi:10.1007/978-3-319-69453-5_2 |
| [48] | Vandersypen, LM; Steffen, M.; Breyta, G.; Yannoni, CS; Sherwood, MH; Chuang, IL, Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature, 414, 6866, 883-887 (2001) · doi:10.1038/414883a |
| [49] | Wheatley, M.: D-Wave debuts new 5,000-qubit quantum computer, September 2019. https://siliconangle.com/2019/09/24/d-wave-debuts-new-5000-qubit-quantum-computer |
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.
