, 1: Computing isogeny paths in ? g (?; p) Input: A and A ? in Sg(p) Output: A path ? : A ? A ? in ?g(?; p)
, A to some point B × E in Sg?1(p) × S1(p)
, ? from A ? to some point B ? × E ? in Sg?1(p) × S1(p)
, ? B ? in ?g?1(?; p) using Algorithm 1 recursively if g ? 1 > 1, or elliptic path-finding if g ? 1 = 1
, If b ? e (mod 2), then fail and return ? (or try again with another ? and/or ? ? , ?
,
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. ,
Parallel collision search with cryptanalytic applications, J. Cryptology, vol.12, issue.1, pp.1-28, 1999. ,
, Fp:=GF(p)
, Fp2<i>:=ExtensionField<Fp,x|x^2+1>; _<x>:=PolynomialRing(Fp2)
, Next_Walk := function(str) H := SHA1(str)
, 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
, return steps,index,walks_done,steps_done
, 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