An official website of the United States government
We propose a quantum algorithm for computing an isogeny between two elliptic curves E1,E2 defined over a finite field such that there is an imaginary quadratic order O satisfying O~End(Ei )for i=1,2. This concerns ordinary curves and supersingular curves defined over Fp (the latter used in the recent CSIDH proposal). Our algorithm has heuristic asymptotic run time exp(O(√log(|Δ|))) and requires polynomial quantum memory and exp(O(√log(|Δ|))) quantumly accessible classical memory, where Δ is the discriminant of O. This asymptotic complexity outperforms all other available methods for computing isogenies.We also show that a variant of our method has asymptotic run time e exp(Õ(√log(|Δ|))) while requesting only polynomial memory (both quantum and classical).
more »
« less
A trade-off between classical and quantum circuit size for an attack against CSIDH
Abstract We propose a heuristic algorithm to solve the underlying hard problem of the CSIDH cryptosystem (and other isogeny-based cryptosystems using elliptic curves with endomorphism ring isomorphic to an imaginary quadratic order 𝒪). Let Δ = Disc(𝒪) (in CSIDH, Δ = −4 p for p the security parameter). Let 0 < α < 1/2, our algorithm requires: A classical circuit of size 2 O ˜ log ( | Δ | ) 1 − α . $$2^{\tilde{O}\left(\log(|\Delta|)^{1-\alpha}\right)}.$$ A quantum circuit of size 2 O ˜ log ( | Δ | ) α . $$2^{\tilde{O}\left(\log(|\Delta|)^{\alpha}\right)}.$$ Polynomial classical and quantum memory. Essentially, we propose to reduce the size of the quantum circuit below the state-of-the-art complexity 2 O ˜ log ( | Δ | ) 1 / 2 $$2^{\tilde{O}\left(\log(|\Delta|)^{1/2}\right)}$$ at the cost of increasing the classical circuit-size required. The required classical circuit remains subexponential, which is a superpolynomial improvement over the classical state-of-the-art exponential solutions to these problems. Our method requires polynomial memory, both classical and quantum.
more »
« less
- Award ID(s):
- 1839805
- PAR ID:
- 10295503
- Date Published:
- Journal Name:
- Journal of Mathematical Cryptology
- Volume:
- 15
- Issue:
- 1
- ISSN:
- 1862-2984
- Page Range / eLocation ID:
- 4 to 17
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let { s j } j = 1 n \left \{ s_{j}\right \} _{j=1}^{n} be positive integers. We show that for any 1 ≤ L ≤ n , 1\leq L\leq n, ‖ ∏ j = 1 n ( 1 − z s j ) ‖ L ∞ ( | z | = 1 ) ≥ exp ( 1 2 e L ( s 1 s 2 … s L ) 1 / L ) . \begin{equation*} \left \Vert \prod _{j=1}^{n}\left ( 1-z^{s_{j}}\right ) \right \Vert _{L_{\infty }\left ( \left \vert z\right \vert =1\right ) }\geq \exp \left ( \frac {1}{2e}\frac {L}{\left ( s_{1}s_{2}\ldots s_{L}\right ) ^{1/L}}\right ) . \end{equation*} In particular, this gives geometric growth if a positive proportion of the { s j } \left \{ s_{j}\right \} are bounded. We also show that when the { s j } \left \{ s_{j}\right \} grow regularly and faster than j ( log j ) 2 + ε j\left ( \log j\right ) ^{2+\varepsilon } , some ε > 0 \varepsilon >0 , then the norms grow faster than exp ( ( log n ) 1 + δ ) \exp \left ( \left ( \log n\right ) ^{1+\delta }\right ) for some δ > 0 \delta >0 .more » « less
-
Mulzer, Wolfgang; Phillips, Jeff M (Ed.)Let X be a set of points in ℝ² and 𝒪 be a set of geometric objects in ℝ², where |X| + |𝒪| = n. We study the problem of computing a minimum subset 𝒪^* ⊆ 𝒪 that encloses all points in X. Here a point x ∈ X is enclosed by 𝒪^* if it lies in a bounded connected component of ℝ²∖(⋃_{O ∈ 𝒪^*} O). We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in O(1)-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an O(α(n)log n)-approximation algorithm for segments, where α(n) is the inverse Ackermann function, and an O(log n)-approximation algorithm for disks.more » « less
-
null (Ed.)Abstract In this paper we provide a framework for applying classical search and preprocessing to quantum oracles for use with Grover’s quantum search algorithm in order to lower the quantum circuit-complexity of Grover’s algorithm for single-target search problems. This has the effect (for certain problems) of reducing a portion of the polynomial overhead contributed by the implementation cost of quantum oracles and can be used to provide either strict improvements or advantageous trade-offs in circuit-complexity. Our results indicate that it is possible for quantum oracles for certain single-target preimage search problems to reduce the quantum circuit-size from O 2 n / 2 ⋅ m C $$O\left(2^{n/2}\cdot mC\right)$$ (where C originates from the cost of implementing the quantum oracle) to O ( 2 n / 2 ⋅ m C ) $$O(2^{n/2} \cdot m\sqrt{C})$$ without the use of quantum ram, whilst also slightly reducing the number of required qubits. This framework captures a previous optimisation of Grover’s algorithm using preprocessing [21] applied to cryptanalysis, providing new asymptotic analysis. We additionally provide insights and asymptotic improvements on recent cryptanalysis [16] of SIKE [14] via Grover’s algorithm, demonstrating that the speedup applies to this attack and impacting upon quantum security estimates [16] incorporated into the SIKE specification [14].more » « less
-
We show that any memory-constrained, first-order algorithm which minimizes d-dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly(d) accuracy using at most $$d^{1.25-\delta}$$ bits of memory must make at least $$\tilde{Omega}(d^{1+(4/3)\delta})$$ first-order queries (for any constant $$\delta in [0,1/4]$$). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal $$\tilde{O}(d)$$ query bound for this problem obtained by cutting plane methods that use $$\tilde{O}(d^2)$$ memory. This resolves a COLT 2019 open problem of Woodworth and Srebro.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1515/jmc-2020-0070
