Low memory attacks on small key CSIDH. (English) Zbl 1542.94115
Tibouchi, Mehdi (ed.) et al., Applied cryptography and network security. 21st international conference, ACNS 2023, Kyoto, Japan, June 19–22, 2023. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13906, 276-304 (2023).
Summary: Despite recent breakthrough results in attacking SIDH, the CSIDH protocol remains a secure post-quantum key exchange protocol with appealing properties. However, for obtaining efficient CSIDH instantiations one has to resort to small secret keys. In this work, we provide novel methods to analyze small key CSIDH, thereby introducing the representation method – that has been successfully applied for attacking small secret keys in code- and lattice-based schemes – also to the isogeny-based world.
We use the recently introduced Restricted Effective Group Actions \((\mathsf{REGA})\) to illustrate the analogy between CSIDH and Diffie-Hellman key exchange. This framework allows us to introduce a \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) problem as a level of abstraction to computing isogenies between elliptic curves, analogous to the classic discrete logarithm problem. This in turn allows us to study \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with ternary key spaces such as \(\{-1, 0, 1\}^n\), \(\{0,1,2\}^n\) and \(\{-2,0,2\}^n\), which lead to especially efficient, recently proposed CSIDH instantiations. The best classic attack on these key spaces is a Meet-in-the-Middle algorithm that runs in time \(3^{0.5 n}\), using also \(3^{0.5 n}\) memory.
We first show that \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with ternary key spaces \(\{0,1,2\}^n\) or \(\{-2,0,2\}^n\) can be reduced to the ternary key space \(\{-1,0,1\}^n\). We further provide a heuristic time-memory tradeoff for \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with keyspace \(\{-1,0,1\}^n\) based on Parallel Collision Search with memory requirement \(M\) that under standard heuristics runs in time \(3^{0.75 n}/M^{0.5}\) for all \(M \le 3^{n/2}\). We then use the representation technique to heuristically improve to \(3^{0.675n}/M^{0.5}\) for all \(M \le 3^{0.22 n}\), and further provide more efficient time-memory tradeoffs for all \(M \le 3^{n/2}\).
Although we focus in this work on \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with ternary key spaces for showing its efficacy in providing attractive time-memory tradeoffs, we also show how to use our framework to analyze larger key spaces \(\{-m, \ldots , m\}^n\) with \(m = 2,3\).
For the entire collection see [Zbl 1523.94004].
We use the recently introduced Restricted Effective Group Actions \((\mathsf{REGA})\) to illustrate the analogy between CSIDH and Diffie-Hellman key exchange. This framework allows us to introduce a \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) problem as a level of abstraction to computing isogenies between elliptic curves, analogous to the classic discrete logarithm problem. This in turn allows us to study \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with ternary key spaces such as \(\{-1, 0, 1\}^n\), \(\{0,1,2\}^n\) and \(\{-2,0,2\}^n\), which lead to especially efficient, recently proposed CSIDH instantiations. The best classic attack on these key spaces is a Meet-in-the-Middle algorithm that runs in time \(3^{0.5 n}\), using also \(3^{0.5 n}\) memory.
We first show that \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with ternary key spaces \(\{0,1,2\}^n\) or \(\{-2,0,2\}^n\) can be reduced to the ternary key space \(\{-1,0,1\}^n\). We further provide a heuristic time-memory tradeoff for \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with keyspace \(\{-1,0,1\}^n\) based on Parallel Collision Search with memory requirement \(M\) that under standard heuristics runs in time \(3^{0.75 n}/M^{0.5}\) for all \(M \le 3^{n/2}\). We then use the representation technique to heuristically improve to \(3^{0.675n}/M^{0.5}\) for all \(M \le 3^{0.22 n}\), and further provide more efficient time-memory tradeoffs for all \(M \le 3^{n/2}\).
Although we focus in this work on \(\mathsf{REGA}\text{-}\mathsf{DLOG}\) with ternary key spaces for showing its efficacy in providing attractive time-memory tradeoffs, we also show how to use our framework to analyze larger key spaces \(\{-m, \ldots , m\}^n\) with \(m = 2,3\).
For the entire collection see [Zbl 1523.94004].
MSC:
| 94A60 | Cryptography |
| 11G05 | Elliptic curves over global fields |
| 14H52 | Elliptic curves |
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
References:
| [1] | Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.J., Menezes, A., Rodríguez-Henríquez, F.: On the cost of computing isogenies between supersingular elliptic curves. In: Cid, C., Jacobson Jr., M.J. (eds.) SAC 2018. LNCS, vol. 11349, pp. 322-343. Springer, Heidelberg (2019). doi:10.1007/978-3-030-10970-7_15 · Zbl 1447.94016 |
| [2] | Alamati, N.; De Feo, L.; Montgomery, H.; Patranabis, S.; Moriai, S.; Wang, H., Cryptographic group actions and applications, Advances in Cryptology - ASIACRYPT 2020, 411-439 (2020), Cham: Springer, Cham · Zbl 1508.94055 · doi:10.1007/978-3-030-64834-3_14 |
| [3] | Albrecht, M.R., et al.: Classic McEliece: conservative code-based cryptography (2020) |
| [4] | Banegas, G., et al.: CTIDH: faster constant-time CSIDH. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2021(4), 351-387 (2021). doi:10.46586/tches.v2021.i4.351-387 |
| [5] | Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 27th SODA, pp. 10-24. ACM-SIAM (Jan 2016). doi:10.1137/1.9781611974331.ch2 · Zbl 1410.68093 |
| [6] | Becker, A.; Joux, A.; May, A.; Meurer, A.; Pointcheval, D.; Johansson, T., Decoding random binary linear codes in \(2^\frac{n}{20}\) improves information set decoding, Advances in Cryptology - EUROCRYPT 2012, 520-536 (2012), Heidelberg: Springer, Heidelberg · Zbl 1291.94206 · doi:10.1007/978-3-642-29011-4_31 |
| [7] | Bellini, E., et al.: Parallel isogeny path finding with limited memory. In: INDOCRYPT 2022. LNCS, vol. 13774, pp. 294-316. Springer, Cham (2023). doi:10.1007/978-3-031-22912-1_13 · Zbl 1519.94047 |
| [8] | Bonnetain, X.; Bricout, R.; Schrottenloher, A.; Shen, Y.; Moriai, S.; Wang, H., Improved classical and quantum algorithms for subset-sum, Advances in Cryptology - ASIACRYPT 2020, 633-666 (2020), Cham: Springer, Cham · Zbl 1521.81056 · doi:10.1007/978-3-030-64834-3_22 |
| [9] | Bonnetain, X.; Schrottenloher, A.; Canteaut, A.; Ishai, Y., Quantum security analysis of CSIDH, Advances in Cryptology - EUROCRYPT 2020, 493-522 (2020), Cham: Springer, Cham · Zbl 1492.81039 · doi:10.1007/978-3-030-45724-2_17 |
| [10] | Bos, J., et al.: Crystals-kyber: a cca-secure module-lattice-based kem. In: 2018 IEEE European Symposium on Security and Privacy (EuroS &P), pp. 353-367. IEEE (2018) |
| [11] | Both, L.; May, A.; Lange, T.; Steinwandt, R., Decoding linear codes with high error rate and its impact for LPN security, Post-Quantum Cryptography, 25-46 (2018), Cham: Springer, Cham · Zbl 1425.94077 · doi:10.1007/978-3-319-79063-3_2 |
| [12] | Bricout, R.; Chailloux, A.; Debris-Alazard, T.; Lequesne, M.; Paterson, KG; Stebila, D., Ternary syndrome decoding with large weight, Selected Areas in Cryptography - SAC 2019, 437-466 (2020), Cham: Springer, Cham · Zbl 1453.94064 · doi:10.1007/978-3-030-38471-5_18 |
| [13] | Castryck, W., Decru, T.: An efficient key recovery attack on SIDH (preliminary version). IACR Cryptol. ePrint Arch, p. 975 (2022). https://eprint.iacr.org/2022/975 |
| [14] | Castryck, W.; Lange, T.; Martindale, C.; Panny, L.; Renes, J.; Peyrin, T.; Galbraith, S., CSIDH: an efficient post-quantum commutative group action, Advances in Cryptology - ASIACRYPT 2018, 395-427 (2018), Cham: Springer, Cham · Zbl 1407.81084 · doi:10.1007/978-3-030-03332-3_15 |
| [15] | Cervantes-Vázquez, D.; Chenu, M.; Chi-Domínguez, J-J; De Feo, L.; Rodríguez-Henríquez, F.; Smith, B.; Schwabe, P.; Thériault, N., Stronger and faster side-channel protections for CSIDH, Progress in Cryptology - LATINCRYPT 2019, 173-193 (2019), Cham: Springer, Cham · Zbl 1453.94067 · doi:10.1007/978-3-030-30530-7_9 |
| [16] | Chávez-Saab, J., Chi-Domínguez, J., Jaques, S., Rodríguez-Henríquez, F.: The SQALE of CSIDH: sublinear vélu quantum-resistant isogeny action with low exponents. J. Cryptogr. Eng. 12(3), 349-368 (2022). doi:10.1007/s13389-021-00271-w |
| [17] | Chi-Domínguez, J., Rodríguez-Henríquez, F.: Optimal strategies for CSIDH. Adv. Math. Commun. 16(2), 383-411 (2022). doi:10.3934/amc.2020116 · Zbl 1500.94022 |
| [18] | Costello, C., Longa, P., Naehrig, M., Renes, J., Virdia, F.: Improved classical cryptanalysis of the computational supersingular isogeny problem. Cryptology ePrint Archive, Report 2019/298 (2019). https://eprint.iacr.org/2019/298 · Zbl 1481.94093 |
| [19] | Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291 |
| [20] | Esser, A.: Revisiting nearest-neighbor-based information set decoding. Cryptology ePrint Archive, Report 2022/1328 (2022). https://eprint.iacr.org/2022/1328 |
| [21] | Esser, A., Girme, R., Mukherjee, A., Sarkar, S.: Memory-efficient attacks on small lwe keys. Cryptology ePrint Archive (2023) · Zbl 07913126 |
| [22] | Esser, A.; May, A.; Canteaut, A.; Ishai, Y., Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory, Advances in Cryptology - EUROCRYPT 2020, 94-122 (2020), Cham: Springer, Cham · Zbl 1479.94165 · doi:10.1007/978-3-030-45727-3_4 |
| [23] | Esser, A., May, A., Zweydinger, F.: McEliece needs a break - solving McEliece-1284 and quasi-cyclic-2918 with modern ISD. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. LNCS, vol. 13277, pp. 433-457. Springer, Heidelberg (2022). doi:10.1007/978-3-031-07082-2_16 · Zbl 1497.94086 |
| [24] | Galbraith, SD; Hess, F.; Smart, NP; Knudsen, LR, Extending the GHS weil descent attack, Advances in Cryptology — EUROCRYPT 2002, 29-44 (2002), Heidelberg: Springer, Heidelberg · Zbl 1055.94013 · doi:10.1007/3-540-46035-7_3 |
| [25] | Glaser, T., May, A.: How to enumerate LWE keys as narrow as in kyber/dilithium. Cryptology ePrint Archive, Report 2022/1337 (2022). https://eprint.iacr.org/2022/1337 |
| [26] | Hutchinson, A.; LeGrow, J.; Koziel, B.; Azarderakhsh, R.; Conti, M.; Zhou, J.; Casalicchio, E.; Spognardi, A., Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors, Applied Cryptography and Network Security, 481-501 (2020), Cham: Springer, Cham · Zbl 07314297 · doi:10.1007/978-3-030-57808-4_24 |
| [27] | 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 |
| [28] | Kuperberg, G., A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM J. Comput., 35, 1, 170-188 (2005) · Zbl 1084.81019 · doi:10.1137/S0097539703436345 |
| [29] | Maino, L., Martindale, C.: An attack on SIDH with arbitrary starting curve. IACR Cryptol. ePrint Arch., p. 1026 (2022). https://eprint.iacr.org/2022/1026 |
| [30] | May, A.; Malkin, T.; Peikert, C., How to meet ternary LWE keys, Advances in Cryptology - CRYPTO 2021, 701-731 (2021), Cham: Springer, Cham · Zbl 1486.94131 · doi:10.1007/978-3-030-84245-1_24 |
| [31] | May, A.; Meurer, A.; Thomae, E.; Lee, DH; Wang, X., Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\), Advances in Cryptology - ASIACRYPT 2011, 107-124 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94055 · doi:10.1007/978-3-642-25385-0_6 |
| [32] | May, A.; Ozerov, I.; Joux, A.; Youssef, A., A generic algorithm for small weight discrete logarithms in composite groups, Selected Areas in Cryptography - SAC 2014, 278-289 (2014), Cham: Springer, Cham · Zbl 1382.94139 · doi:10.1007/978-3-319-13051-4_17 |
| [33] | May, A.; Ozerov, I.; Oswald, E.; Fischlin, M., On computing nearest neighbors with applications to decoding of binary linear codes, Advances in Cryptology - EUROCRYPT 2015, 203-228 (2015), Heidelberg: Springer, Heidelberg · Zbl 1365.94597 · doi:10.1007/978-3-662-46800-5_9 |
| [34] | McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. The deep space network progress report 42-44, Jet Propulsion Laboratory, California Institute of Technology (Jan/Feb 1978). https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF |
| [35] | Meyer, M.; Campos, F.; Reith, S.; Ding, J.; Steinwandt, R., On lions and elligators: an efficient constant-time implementation of CSIDH, Post-Quantum Cryptography, 307-325 (2019), Cham: Springer, Cham · Zbl 1509.94123 · doi:10.1007/978-3-030-25510-7_17 |
| [36] | Onuki, H.; Aikawa, Y.; Yamazaki, T.; Takagi, T.; Attrapadung, N.; Yagi, T., (Short Paper) a faster constant-time algorithm of CSIDH keeping two points, Advances in Information and Computer Security, 23-33 (2019), Cham: Springer, Cham · doi:10.1007/978-3-030-26834-3_2 |
| [37] | Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T.: A constant-time algorithm of CSIDH keeping two points. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 103-A(10), 1174-1182 (2020). doi:10.1587/transfun.2019DMP0008 |
| [38] | Peikert, C.; Canteaut, A.; Ishai, Y., He gives C-sieves on the CSIDH, Advances in Cryptology - EUROCRYPT 2020, 463-492 (2020), Cham: Springer, Cham · Zbl 1492.81043 · doi:10.1007/978-3-030-45724-2_16 |
| [39] | Prange, E., The use of information sets in decoding cyclic codes, IRE Trans. Inf. Theory, 8, 5, 5-9 (1962) · doi:10.1109/TIT.1962.1057777 |
| [40] | Robert, D.: Breaking SIDH in polynomial time. IACR Cryptol. ePrint Arch. p. 1038 (2022). https://eprint.iacr.org/2022/1038 |
| [41] | Rostovtsev, A., Stolbunov, A.: Public-Key Cryptosystem Based On Isogenies. Cryptology ePrint Archive, Report 2006/145 (2006). https://eprint.iacr.org/2006/145 |
| [42] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th FOCS, pp. 124-134. IEEE Computer Society Press (Nov 1994). doi:10.1109/SFCS.1994.365700 |
| [43] | Tani, S., Claw finding algorithms using quantum walk, Theoret. Comput. Sci., 410, 50, 5285-5297 (2009) · Zbl 1191.68327 · doi:10.1016/j.tcs.2009.08.030 |
| [44] | van Hoof, I.; Kirshanova, E.; May, A.; Cheon, JH; Tillich, J-P, Quantum key search for ternary LWE, Post-Quantum Cryptography, 117-132 (2021), Cham: Springer, Cham · Zbl 1489.81023 · doi:10.1007/978-3-030-81293-5_7 |
| [45] | van Oorschot, PC; Wiener, MJ, Parallel collision search with cryptanalytic applications, J. Cryptol., 12, 1, 1-28 (1999) · Zbl 0992.94028 · doi:10.1007/PL00003816 |
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.
