Skip to main content

2020 | OriginalPaper | Buchkapitel

He Gives C-Sieves on the CSIDH

verfasst von : Chris Peikert

Erschienen in: Advances in Cryptology – EUROCRYPT 2020

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Recently, Castryck, Lange, Martindale, Panny, and Renes proposed CSIDH (pronounced “sea-side”) as a candidate post-quantum “commutative group action.” It has attracted much attention and interest, in part because it enables noninteractive Diffie–Hellman-like key exchange with quite small communication. Subsequently, CSIDH has also been used as a foundation for digital signatures.
In 2003–04, Kuperberg and then Regev gave asymptotically subexponential quantum algorithms for “hidden shift” problems, which can be used to recover the CSIDH secret key from a public key. In late 2011, Kuperberg gave a follow-up quantum algorithm called the collimation sieve (“c-sieve” for short), which improves the prior ones, in particular by using exponentially less quantum memory and offering more parameter tradeoffs. While recent works have analyzed the concrete cost of the original algorithms (and variants) against CSIDH, nothing of this nature was previously available for the c-sieve.
This work fills that gap. Specifically, we generalize Kuperberg’s collimation sieve to work for arbitrary finite cyclic groups, provide some practical efficiency improvements, give a classical (i.e., non-quantum) simulator, run experiments for a wide range of parameters up to the actual CSIDH-512 group order, and concretely quantify the complexity of the c-sieve against CSIDH.
Our main conclusion is that the proposed CSIDH parameters provide relatively little quantum security beyond what is given by the cost of quantumly evaluating the CSIDH group action itself (on a uniform superposition). For example, the cost of CSIDH-512 key recovery is only about \(2^{16}\) quantum evaluations using \(2^{40}\) bits of quantumly accessible classical memory (plus relatively small other resources). This improves upon a prior estimate of \(2^{32.5}\) evaluations and \(2^{31}\) qubits of quantum memory, for a variant of Kuperberg’s original sieve.
Under the plausible assumption that quantum evaluation does not cost much more than what is given by a recent “best case” analysis, CSIDH-512 can therefore be broken using significantly less than \(2^{64}\) quantum T-gates. This strongly invalidates its claimed NIST level 1 quantum security, especially when accounting for the MAXDEPTH restriction. Moreover, under analogous assumptions for CSIDH-1024 and -1792, which target higher NIST security levels, except near the high end of the MAXDEPTH range even these instantiations fall short of level 1.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
More recently, Kuperberg has given talks highlighting the virtues of the algorithm and its relevance to isogenies.
 
2
Shortly after the announcement of this work, Bonnetain and Schrottenloher posted an updated version of [BS18], which had been under private review and which does contain such an analysis. See below for a comparison.
 
3
Our work has no implications for SIDH [JD11] or the NIST submission SIKE, which do not use commutative group actions.
 
4
The main security claim in [CLM+18] for CSIDH-512 (which appears in the abstract, introduction, and security evaluation) is NIST level 1. However, in one location the paper also mentions, in a passing reference to CSIDH-512, a “conjectured post-quantum security level of 64 bits.” This would constitute a different, significantly weaker security claim than NIST level 1, in part because the latter accounts for the cost of quantumly evaluating AES, and has a MAXDEPTH restriction. No definition for ‘bits of post-quantum security’ is given in [CLM+18], but the security analysis in Section 7.3 and Table 1 quantifies “costs for the complete attack” in terms of number of logical qubit operations, and targets \(2^{64}\) or more for CSIDH-512. Under this implied interpretation of ‘64 bits of post-quantum security,’ and our assumption on the cost of the oracle, our work even falsifies this security claim as well. We point out that other metrics like “depth times width” can be used to quantify security (see, e.g., [JS19]), and at present the complexity of our attack in this metric is unclear, in part because the precise depth and width of the oracle are unknown. However, under any reasonable metric the oracle calls are presently the bottleneck for sieve parameters of interest.
 
5
We again emphasize that the c-sieve offers a flexible tradeoff among queries, QRACM, and classical time, so all these example query counts can be reduced somewhat by increasing these other resources.
 
6
This is roughly analogous to what is done in Kuperberg’s original sieve [Kup03], where combining two qubits has a 50% chance of producing a “useless” output that is then discarded.
 
7
Note that the multipliers \(b'(\varvec{\jmath }) \in [rS']\) are not quite uniformly distributed, because they are biased toward their expectation \(rS'/2\), and extreme values are less likely. For \(r=2\), an easy calculation shows that due to this bias, \(\mathbb {E}[L]\) is very close to \(\tfrac{2}{3} L' \cdot S/S'\). This means that the output of the collimation step is slightly better than the above analysis indicates.
 
8
The code for the simulator and instructions for running it are at https://​github.​com/​cpeikert/​CollimationSieve​. The code is written in the author’s favorite functional language Haskell, and has not been especially optimized for performance, but it suffices for the present purposes.
 
Literatur
[Bab85]
Zurück zum Zitat Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986). Preliminary version in STACS 1985MathSciNetCrossRef Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986). Preliminary version in STACS 1985MathSciNetCrossRef
[DH76]
Zurück zum Zitat Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory IT–22(6), 644–654 (1976)MathSciNetCrossRef Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory IT–22(6), 644–654 (1976)MathSciNetCrossRef
[KKP20]
Zurück zum Zitat Kaafarani, A.E., Katsumata, S., Pintore, F.: Lossy CSI-FiSh: efficient signature scheme with tight reduction to decisional CSIDH-512. In: PKC (2020) Kaafarani, A.E., Katsumata, S., Pintore, F.: Lossy CSI-FiSh: efficient signature scheme with tight reduction to decisional CSIDH-512. In: PKC (2020)
[Kup11]
Zurück zum Zitat Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC, pp. 20–34 (2013). Preliminary version in https://arxiv.org/abs/1112.3333 Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC, pp. 20–34 (2013). Preliminary version in https://​arxiv.​org/​abs/​1112.​3333
[Reg04]
Zurück zum Zitat Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. CoRR, quant-ph/0406151 (2004) Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. CoRR, quant-ph/0406151 (2004)
[Sch19]
Zurück zum Zitat Schanck, J.: Personal communication, June 2019 Schanck, J.: Personal communication, June 2019
[Sho94]
Zurück zum Zitat Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). Preliminary version in FOCS 2004MathSciNetCrossRef Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). Preliminary version in FOCS 2004MathSciNetCrossRef
[SS79]
Zurück zum Zitat Schroeppel, R., Shamir, A.: A t=o(2\({}^{\text{ n/2 }}\)), s=o(2\({}^{\text{ n/4 }}\)) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456–464 (1981). Preliminary version in FOCS 1979MathSciNetCrossRef Schroeppel, R., Shamir, A.: A t=o(2\({}^{\text{ n/2 }}\)), s=o(2\({}^{\text{ n/4 }}\)) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456–464 (1981). Preliminary version in FOCS 1979MathSciNetCrossRef
[Sto04]
Zurück zum Zitat Stolbunov, A.: Public-key encryption based on cycles of isogenous elliptic curves. Master’s thesis, Saint-Petersburg State Polytechnical University (2004). (in Russian) Stolbunov, A.: Public-key encryption based on cycles of isogenous elliptic curves. Master’s thesis, Saint-Petersburg State Polytechnical University (2004). (in Russian)
[Sto11]
Zurück zum Zitat Stolbunov, A.: Cryptographic schemes based on isogenies. Ph.D. thesis, Norwegian University of Science and Technology (2011) Stolbunov, A.: Cryptographic schemes based on isogenies. Ph.D. thesis, Norwegian University of Science and Technology (2011)
Metadaten
Titel
He Gives C-Sieves on the CSIDH
verfasst von
Chris Peikert
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-45724-2_16