Cryptographic hash functions from expander graphs

DOI10.1007/s00145-007-9002-xzbMath1166.94006OpenAlexW2000932900MaRDI QIDQ1027970

Kristin E. Lauter, Eyal Z. Goren, Denis Xavier Charles

Publication date: 30 June 2009

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00145-007-9002-x

zbMATH Keywords

elliptic curve cryptography isogenies expander graphs cryptographic hash functions supersingular elliptic curves Ramanujan graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Cryptography (94A60)

Related Items

Multiradical isogenies ⋮ Automorphisms and isogeny graphs of abelian varieties, with applications to the superspecial Richelot isogeny graph ⋮ From graphs to keyed quantum hash functions ⋮ Group Key Exchange from CSIDH and Its Application to Trusted Setup in Supersingular Isogeny Cryptosystems ⋮ The Supersingular Isogeny Problem in Genus 2 and Beyond ⋮ On division polynomial PIT and supersingularity ⋮ Improved supersingularity testing of elliptic curves using Legendre form ⋮ Explicit Connections Between Supersingular Isogeny Graphs and Bruhat–Tits Trees ⋮ On isogeny graphs of supersingular elliptic curves over finite fields ⋮ On the hardness of the computational ring-LWR problem and its applications ⋮ $\mathrm{SL}_2$ homomorphic hash functions: worst case to average case reduction and short collision search ⋮ Geometry and Combinatorics via Right-Angled Artin Groups ⋮ Pseudorandom numbers and hash functions from iterations of multivariate polynomials ⋮ Faster isogenies for post-quantum cryptography: SIKE ⋮ A new adaptive attack on SIDH ⋮ A Survey on some Applications of Graph Theory in Cryptography ⋮ Orientations and the supersingular endomorphism ring problem ⋮ On the Isogeny Problem with Torsion Point Information ⋮ Radical Isogenies on Montgomery Curves ⋮ Séta: Supersingular Encryption from Torsion Attacks ⋮ SHealS and HealS: Isogeny-Based PKEs from a Key Validation Method for SIDH ⋮ Supersingular curves you can trust ⋮ Proving knowledge of isogenies: a survey ⋮ M-SIDH and MD-SIDH: countering SIDH attacks by masking information ⋮ Multiparty non-interactive key exchange and more from isogenies on elliptic curves ⋮ New techniques for SIDH-based NIKE ⋮ A subexponential-time, polynomial quantum space algorithm for inverting the CM group action ⋮ Orienteering with one endomorphism ⋮ Dakota – Hashing from a Combination of Modular Arithmetic and Symmetric Cryptography ⋮ On the Security of Supersingular Isogeny Cryptosystems ⋮ Isogeny formulas for Jacobi intersection and twisted Hessian curves ⋮ Spectrum of random d‐regular graphs up to the edge ⋮ Cryptanalysis of an oblivious PRF from supersingular isogenies ⋮ DeCSIDH: delegating isogeny computations in the CSIDH setting ⋮ New constructions of collapsing hashes ⋮ Parallel isogeny path finding with limited memory ⋮ Automorphisms of the supersingular isogeny graph ⋮ Efficient computation of $(3^n,3^n)$-isogenies ⋮ Computing isogeny volcanoes of composite degree ⋮ SQISign: compact post-quantum signatures from quaternions and isogenies ⋮ Cryptographic group actions and applications ⋮ Radical isogenies ⋮ Oblivious pseudorandom functions from isogenies ⋮ Explicit isogenies in quadratic time in any characteristic ⋮ CSIDH: an efficient post-quantum commutative group action ⋮ Towards factoring in $\mathrm{SL}(2,\mathbb F_{2^n})$ ⋮ On the cost of computing isogenies between supersingular elliptic curves ⋮ Ramanujan Graphs in Cryptography ⋮ Cycles in the Supersingular ℓ-Isogeny Graph and Corresponding Endomorphisms ⋮ A characterization of chameleon hash functions and new, efficient designs ⋮ How not to create an isogeny-based PAKE ⋮ Common composites of triangular polynomial systems and hash functions ⋮ Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata ⋮ On the supersingular GPST attack ⋮ Side-channel attacks on quantum-resistant supersingular isogeny Diffie-Hellman ⋮ Efficient post-quantum undeniable signature on 64-bit ARM ⋮ Supersingular Isogeny-based Cryptography: A Survey ⋮ Computational problems in supersingular elliptic curve isogenies ⋮ Keyed hash function from large girth expander graphs ⋮ Better path-finding algorithms in LPS Ramanujan graphs ⋮ Interpreting Hash Function Security Proofs ⋮ New Zémor-Tillich type hash functions over $\mathrm{GL}_2 (\mathbb{F}_{p^n})$ ⋮ Hash functions from superspecial genus-2 curves using Richelot isogenies ⋮ Hash Functions from Sigma Protocols and Improvements to VSH ⋮ Orienting supersingular isogeny graphs ⋮ A trade-off between classical and quantum circuit size for an attack against CSIDH ⋮ Towards isogeny-based password-authenticated key establishment ⋮ Algebraic approaches for solving isogeny problems of prime power degrees ⋮ A framework for reducing the overhead of the quantum oracle for use with Grover's algorithm with applications to cryptanalysis of SIKE ⋮ Super-expanders and warped cones ⋮ Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves ⋮ Some graph-based encryption schemes ⋮ Computing isogenies between supersingular elliptic curves over $\mathbb {F}_p$ ⋮ Cryptographic Hash Functions and Expander Graphs: The End of the Story? ⋮ Isogenies on twisted Hessian curves ⋮ Collisions for the LPS Expander Graph Hash Function ⋮ Generalized Group–Subgroup Pair Graphs ⋮ Ramanujan Graphs for Post-Quantum Cryptography ⋮ On 1-factorizations of bipartite Kneser graphs ⋮ Constructing cycles in isogeny graphs of supersingular elliptic curves ⋮ Identification protocols and signature schemes based on supersingular isogeny problems ⋮ Preimages for the Tillich-Zémor Hash Function ⋮ Endomorphism rings of supersingular elliptic curves over $\mathbb{F}_p$ ⋮ One-way functions and malleability oracles: hidden shift attacks on isogeny-based protocols ⋮ Eliptic curves in post-quantum cryptography ⋮ Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies ⋮ Implementation report of the Kohel-Lauter-Petit-Tignol algorithm for the constructive Deuring correspondence ⋮ Modular polynomials on Hilbert surfaces ⋮ Constructing an efficient hash function from $3$-isogenies ⋮ Counting Richelot isogenies between superspecial abelian surfaces ⋮ Computing newforms using supersingular isogeny graphs ⋮ Delegating supersingular isogenies over $\mathbb{F}_{p^2}$ with cryptographic applications ⋮ Efficient Finite Field Multiplication for Isogeny Based Post Quantum Cryptography ⋮ On the quaternion -isogeny path problem ⋮ SimS: a simplification of SiGamal ⋮ Quantum security analysis of CSIDH ⋮ Rational isogenies from irrational endomorphisms

Cites Work