On the cost of computing isogenies between supersingular elliptic curves, 25th Conference on Selected Areas in Cryptography (SAC 2018), 2018. ,
, , 2017.
A quantum algorithm for computing isogenies between supersingular elliptic curves, Progress in Cryptology -INDOCRYPT 2014 -15th International Conference on Cryptology in India, vol.8885, pp.428-442, 2014. ,
AVIsogenies -a library for computing isogenies between abelian varieties, 2012. ,
Tight bounds on quantum searching, Fortschritte der Physik: Progress of Physics, vol.46, issue.4-5, pp.493-505, 1998. ,
Prolegomena to a middlebrow arithmetic of curves of genus 2, vol.230, 1996. ,
Hash functions from superspecial genus-2 curves using Richelot isogenies, Cryptology ePrint Archive, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02067885
CSIDH: An efficient post-quantum commutative group action, Advances in Cryptology -ASIACRYPT 2018, Part III, pp.395-427, 2018. ,
Families of Ramanujan graphs and quaternion algebras, Groups and symmetries, from neolithic scots to John McKay, pp.53-80, 2009. ,
Cryptographic hash functions from expander graphs, Journal of Cryptology, vol.22, issue.1, pp.93-113, 2009. ,
Computing supersingular isogenies on Kummer surfaces, International Conference on the Theory and Application of Cryptology and Information Security, pp.428-456, 2018. ,
SeaSign: Compact isogeny signatures from class group actions, Advances in Cryptology -EUROCRYPT 2019, 2019. ,
Verifiable delay functions from supersingular isogenies and pairings, Cryptology ePrint Archive, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02388349
Computing isogenies between supersingular elliptic curves over Fp, Des. Codes Cryptography, vol.78, issue.2, pp.425-440, 2016. ,
An index calculus algorithm for plane curves of small degree, Algorithmic Number Theory, 7th International Symposium, ANTS-VII, vol.4076, pp.543-557, 2006. ,
Cyclic Isogenies for Abelian Varieties with Real Multiplication, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01629829
Supersingular isogeny graphs and endomorphism rings: reductions and solutions, Advances in cryptology-EUROCRYPT 2018. Part III, pp.329-368, 2018. ,
On supersingular curves and abelian varieties, Mathematica Scandinavica, vol.60, pp.151-178, 1987. ,
Genus two isogeny cryptography, Post-Quantum Cryptography -10th International Conference, vol.11505, pp.286-306, 2019. ,
On the security of supersingular isogeny cryptosystems, Advances in Cryptology -ASIACRYPT 2016 -22nd International Conference on the Theory and Application of Cryptology and Information Security, vol.10031, pp.63-91, 2016. ,
Identification protocols and signature schemes based on supersingular isogeny problems, Advances in Cryptology -ASIACRYPT 2017 -23rd International Conference on the Theory and Applications of Cryptology and Information Security, vol.10624, pp.3-33, 2017. ,
Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symb. Comput, vol.44, issue.12, pp.1690-1702, 2009. ,
URL : https://hal.archives-ouvertes.fr/inria-00337631
A double large prime variation for small genus hyperelliptic index calculus, Math. Comput, vol.76, issue.257, pp.475-492, 2007. ,
URL : https://hal.archives-ouvertes.fr/inria-00077334
A fast quantum mechanical algorithm for database search, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp.212-219, 1996. ,
Expander graphs and their applications, Bulletin (New Series) of the American Mathematical Society, vol.43, issue.4, pp.439-561, 2006. ,
Superspecial abelian varieties, theta series and the Jacquet-Langlands correspondence, 2005. ,
Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, International Workshop on Post-Quantum Cryptography, pp.19-34, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00652846
Quantum cryptanalysis in the RAM model: Clawfinding attacks on SIKE, Advances in Cryptology -CRYPTO 2019 -39th Annual International Cryptology Conference, vol.11692, pp.32-61, 2019. ,
On the quaternion ?-isogeny path problem, LMS J. Comput. Math, vol.17, pp.418-432, 2014. ,
URL : https://hal.archives-ouvertes.fr/hal-01257092
, Arithmetic on abelian and Kummer varieties. Finite Fields and Their Applications, vol.39, pp.130-158, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01057467
Faster algorithms for isogeny problems using torsion point images, Advances in Cryptology -ASIACRYPT 2017 -23rd International Conference on the Theory and Applications of Cryptology and Information Security, vol.10625, pp.330-353, 2017. ,
Ramanujan graphs and hecke operators, Bull. Am. Math. Soc, vol.23, issue.1, 1990. ,
Explicit endomorphisms and correspondences, 2005. ,
Isogenies and the discrete logarithm problem in jacobians of genus 3 hyperelliptic curves, J. Cryptology, vol.22, issue.4, pp.505-529, 2009. ,
URL : https://hal.archives-ouvertes.fr/inria-00537860
Identifying supersingular elliptic curves, LMS Journal of Computation and Mathematics, vol.15, pp.317-325, 2012. ,
Mathematical Modelling for Next-Generation Cryptography: CREST Crypto-Math Project, chapter Efficient Algorithms for Isogeny Sequences and Their Cryptographic Applications, pp.97-114, 2018. ,
Claw finding algorithms using quantum walk, Theor. Comput. Sci, vol.410, issue.50, pp.5285-5297, 2009. ,
C : y 2 = x 5 + x over a given F p 2 to a random abelian surface in ? 2 (2; p), which becomes the target A. Then it starts computing random walks of length slightly larger than log 2 (p), whose steps correspond to (2, 2)-isogenies. As each step is taken, it checks whether we have landed on a product of two elliptic curves (at which point it will terminate) before continuing. Magma's built-in functionality for (2, 2)-isogenies makes this rather straightforward. At a given node, the function RichelotIsogenousSurfaces computes all 15 of its neighbours, so our random walks are simply a matter of generating enough entropy to choose one of these neighbours at each of the O(log(p)) steps. For the sake of replicability, we have used Magma's inbuilt implementation of SHA-1 to produce pseudo-random walks that are deterministically generated by an input seed. SHA-1 produces 160-bit strings, J. Cryptology, vol.12, issue.1, pp.1-28, 1999. ,
, Fp:=GF(p)
, Fp2<i>:=ExtensionField<Fp,x|x^2+1>; _<x>:=PolynomialRing(Fp2)
, H:=SHA1(str); bytes:=StringToBytes(H)
, Walk_To_Starting_Jacobian:=function(str) steps,H:= Next_Walk(str)
, C0:=HyperellipticCurve(x^5+x)
, J0:=Jacobian(C0)
, =1 to #steps do neighbours:=RichelotIsogenousSurfaces(J0)
, Walk_Until_Found:=function(seed, J0
, H:=seed; found:=false; walks_done:=0; steps_done:=0
, walks and
, =1 to #steps do steps_done+, p.1
, J:=RichelotIsogenousSurfaces(J)
, if Type(J) eq SetCart then found:=true
,
, J0:=Walk_To_Starting_Jacobian
, J0
,
, Write(file_name, walks_done)
,
, Write(file_name, steps_done)
,
, Write(file_name, steps)
,
, Write(file_name, index)
Elliptic Product= ,
, Write(file_name, J