SIDH proof of knowledge. (English) Zbl 1519.94100
Agrawal, Shweta (ed.) et al., Advances in cryptology – ASIACRYPT 2022. 28th international conference on the theory and application of cryptology and information security, Taipei, Taiwan, December 5–9, 2022. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13792, 310-339 (2023).
Summary: We show that the soundness proof for the De Feo-Jao-Plût identification scheme (the basis for supersingular isogeny Diffie-Hellman (SIDH) signatures) contains an invalid assumption, and we provide a counterexample for this assumption – thus showing the proof of soundness is invalid. As this proof was repeated in a number of works by various authors, multiple pieces of literature are affected by this result. Due to the importance of being able to prove knowledge of an SIDH key (for example, to prevent adaptive attacks), soundness is a vital property.
Surprisingly, the problem of proving knowledge of a specific isogeny turns out to be considerably more difficult than was perhaps anticipated. The main results of this paper are a sigma protocol to prove knowledge of a walk of specified length in a supersingular isogeny graph, and a second one to additionally prove that the isogeny maps some torsion points to some other torsion points (as seen in SIDH public keys). Our scheme also avoids the SIDH identification scheme soundness issue raised by W. Ghantous et al. [“Collisions in supersingular isogeny graphs and the SIDH-based identification protocol”, Preprint, https://eprint.iacr.org/2021/1051]. In particular, our protocol provides a non-interactive way of verifying correctness of SIDH public keys, and related statements, as protection against adaptive attacks.
Post-scriptum: Some months after this work was completed and made public, the SIDH assumption was broken in a series of papers by several authors. Hence, in the standard SIDH setting, some of the statements studied here now have trivial polynomial time non-interactive proofs. Nevertheless our first sigma protocol is unaffected by the attacks, and our second protocol may still be useful in present and future variants of SIDH that escape the attacks.
For the entire collection see [Zbl 1517.94001].
Surprisingly, the problem of proving knowledge of a specific isogeny turns out to be considerably more difficult than was perhaps anticipated. The main results of this paper are a sigma protocol to prove knowledge of a walk of specified length in a supersingular isogeny graph, and a second one to additionally prove that the isogeny maps some torsion points to some other torsion points (as seen in SIDH public keys). Our scheme also avoids the SIDH identification scheme soundness issue raised by W. Ghantous et al. [“Collisions in supersingular isogeny graphs and the SIDH-based identification protocol”, Preprint, https://eprint.iacr.org/2021/1051]. In particular, our protocol provides a non-interactive way of verifying correctness of SIDH public keys, and related statements, as protection against adaptive attacks.
Post-scriptum: Some months after this work was completed and made public, the SIDH assumption was broken in a series of papers by several authors. Hence, in the standard SIDH setting, some of the statements studied here now have trivial polynomial time non-interactive proofs. Nevertheless our first sigma protocol is unaffected by the attacks, and our second protocol may still be useful in present and future variants of SIDH that escape the attacks.
For the entire collection see [Zbl 1517.94001].
References:
| [1] | Azarderakhsh, R., et al.: Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Standardization project (2017) |
| [2] | Azarderakhsh, R.; Jao, D.; Leonardi, C.; Adams, C.; Camenisch, J., Post-quantum static-static key agreement using multiple protocol instances, Selected Areas in Cryptography - SAC 2017, 45-63 (2018), Cham: Springer, Cham · Zbl 1384.94028 · doi:10.1007/978-3-319-72565-9_3 |
| [3] | Basso, A.; Kutas, P.; Merz, S-P; Petit, C.; Weitkämper, C.; Nitaj, A.; Youssef, A., On adaptive attacks against Jao-Urbanik’s isogeny-based protocol, Progress in Cryptology - AFRICACRYPT 2020, 195-213 (2020), Cham: Springer, Cham · Zbl 1501.94026 · doi:10.1007/978-3-030-51938-4_10 |
| [4] | Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) ACM CCS 1993, pp. 62-73. ACM Press (1993). doi:10.1145/168588.168596 |
| [5] | Boneh, D.; Kogan, D.; Woo, K.; Moriai, S.; Wang, H., Oblivious pseudorandom functions from isogenies, Advances in Cryptology - ASIACRYPT 2020, 520-550 (2020), Cham: Springer, Cham · Zbl 1511.94060 · doi:10.1007/978-3-030-64834-3_18 |
| [6] | Castryck, W., Decru, T.: An efficient key recovery attack on SIDH (preliminary version). Cryptology ePrint Archive, Paper 2022/975 (2022). https://eprint.iacr.org/2022/975 · Zbl 1501.94035 |
| [7] | Damgård, I.; Preneel, B., Efficient concurrent zero-knowledge in the auxiliary string model, Advances in Cryptology — EUROCRYPT 2000, 418-430 (2000), Heidelberg: Springer, Heidelberg · Zbl 1082.94539 · doi:10.1007/3-540-45539-6_30 |
| [8] | Damgård, I.; Goldreich, O.; Okamoto, T.; Wigderson, A.; Coppersmith, D., Honest verifier vs dishonest verifier in public coin zero-knowledge proofs, Advances in Cryptology — CRYPT0’ 95, 325-338 (1995), Heidelberg: Springer, Heidelberg · Zbl 1114.94305 · doi:10.1007/3-540-44750-4_26 |
| [9] | De Feo, L., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol. 8(3), 209-247 (2014). doi:10.1515/jmc-2012-0015. https://www.degruyter.com/view/j/jmc.2014.8.issue-3/jmc-2012-0015/jmc-2012-0015.xml · Zbl 1372.94419 |
| [10] | Dobson, S.; Galbraith, SD; LeGrow, J.; Ti, YB; Zobernig, L., An adaptive attack on 2-SIDH, Int. J. Comput. Math. Comput. Syst. Theory, 5, 4, 282-299 (2020) · doi:10.1080/23799927.2020.1822446 |
| [11] | Fouotsa, T.B.: SIDH with masked torsion point images. Cryptology ePrint Archive, Paper 2022/1054 (2022). https://eprint.iacr.org/2022/1054 |
| [12] | Fouotsa, TB; Petit, C.; Galbraith, SD, A new adaptive attack on SIDH, Topics in Cryptology - CT-RSA 2022, 322-344 (2022), Cham: Springer, Cham · Zbl 1492.94107 · doi:10.1007/978-3-030-95312-6_14 |
| [13] | Galbraith, SD; Petit, C.; Shani, B.; Ti, YB; Cheon, JH; Takagi, T., On the security of supersingular isogeny cryptosystems, Advances in Cryptology - ASIACRYPT 2016, 63-91 (2016), Heidelberg: Springer, Heidelberg · Zbl 1404.94073 · doi:10.1007/978-3-662-53887-6_3 |
| [14] | Galbraith, SD; Petit, C.; Silva, J., Identification protocols and signature schemes based on supersingular isogeny problems, J. Cryptol., 33, 1, 130-175 (2020) · Zbl 1455.94155 · doi:10.1007/s00145-019-09316-0 |
| [15] | Galbraith, SD; Vercauteren, F., Computational problems in supersingular elliptic curve isogenies, Quantum Inf. Process., 17, 10, 1-22 (2018) · Zbl 1400.81083 · doi:10.1007/s11128-018-2023-6 |
| [16] | Garay, JA; MacKenzie, P.; Yang, K., Strengthening zero-knowledge protocols using signatures, J. Cryptol., 19, 2, 169-209 (2005) · Zbl 1101.68550 · doi:10.1007/s00145-005-0307-3 |
| [17] | Ghantous, W., Pintore, F., Veroni, M.: Collisions in supersingular isogeny graphs and the SIDH-based identification protocol. Cryptology ePrint Archive, Report 2021/1051 (2021). https://eprint.iacr.org/2021/1051 |
| [18] | Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, J. ACM (JACM), 38, 3, 690-728 (1991) · Zbl 0799.68101 · doi:10.1145/116825.116852 |
| [19] | Hofheinz, D.; Hövelmanns, K.; Kiltz, E.; Kalai, Y.; Reyzin, L., A modular analysis of the Fujisaki-Okamoto transformation, Theory of Cryptography, 341-371 (2017), Cham: Springer, Cham · Zbl 1410.94082 · doi:10.1007/978-3-319-70500-2_12 |
| [20] | Jao, D.; De Feo, L.; Yang, B-Y, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Post-Quantum Cryptography, 19-34 (2011), Heidelberg: Springer, Heidelberg · Zbl 1290.94094 · doi:10.1007/978-3-642-25405-5_2 |
| [21] | Jao, D.; Soukharev, V.; Mosca, M., Isogeny-based quantum-resistant undeniable signatures, Post-Quantum Cryptography, 160-179 (2014), Cham: Springer, Cham · Zbl 1380.94101 · doi:10.1007/978-3-319-11659-4_10 |
| [22] | Leonardi, C.: A note on the ending elliptic curve in SIDH. Cryptology ePrint Archive, Report 2020/262 (2020). https://ia.cr/2020/262 |
| [23] | Maino, L., Martindale, C.: An attack on SIDH with arbitrary starting curve. Cryptology ePrint Archive, Paper 2022/1026 (2022). https://eprint.iacr.org/2022/1026 |
| [24] | Martindale, C., Panny, L.: How to not break SIDH. CFAIL (2019). https://ia.cr/2019/558 |
| [25] | Moriya, T.: Masked-degree SIDH. Cryptology ePrint Archive, Paper 2022/1019 (2022). https://eprint.iacr.org/2022/1019 |
| [26] | Robert, D.: Breaking SIDH in polynomial time. Cryptology ePrint Archive, Paper 2022/1038 (2022). https://eprint.iacr.org/2022/1038 |
| [27] | Silverman, JH, The Arithmetic of Elliptic Curves (2009), New York: Springer, New York · Zbl 1194.11005 · doi:10.1007/978-0-387-09494-6 |
| [28] | Thormarker, E.: Post-quantum cryptography: supersingular isogeny Diffie-Hellman key exchange. Thesis, Stockholm University (2017) |
| [29] | Ueno, R., Xagawa, K., Tanaka, Y., Ito, A., Takahashi, J., Homma, N.: Curse of re-encryption: a generic power/EM analysis on post-quantum KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 296-322 (2022) |
| [30] | Urbanik, D., Jao, D.: SoK: the problem landscape of SIDH. In: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop, pp. 53-60 (2018) |
| [31] | Urbanik, D.; Jao, D., New techniques for SIDH-based NIKE, J. Math. Cryptol., 14, 1, 120-128 (2020) · Zbl 1448.94233 · doi:10.1515/jmc-2015-0056 |
| [32] | Vélu, J.: Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. A-B 273, A238-A241 (1971) · Zbl 0225.14014 |
| [33] | Yoo, Y.; Azarderakhsh, R.; Jalali, A.; Jao, D.; Soukharev, V.; Kiayias, A., A post-quantum digital signature scheme based on supersingular isogenies, Financial Cryptography and Data Security, 163-181 (2017), Cham: Springer, Cham · Zbl 1457.94230 · doi:10.1007/978-3-319-70972-7_9 |
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.
