Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies

Abstract We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the non-commutativity of the endomorphism ring. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [Lecture Notes in Comput. Sci. 7071, Springer (2011), 19–34]. We add a new zero-knowledge identification scheme and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.

• Publication year

  2011

• Venue

  Journal of Mathematical Cryptology

• Publication date

  2011-11-29

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1515/jmc-2012-0015
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Improved algorithm for the isogeny problem for ordinary elliptic curves

  2011cited by this paper
• Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves

  2010influential reference
• Reductionist Security Arguments for Public-Key Cryptographic Schemes Based on Group Action

  2009cited by this paper
• The Case for Quantum Key Distribution

  2009influential reference
• Twisted Edwards Curves

  2008influential reference
• Cryptographic Hash Functions from Expander Graphs

  2008cited by this paper
• Full Cryptanalysis of LPS and Morgenstern Hash Functions

  2008cited by this paper
• Number theoretic algorithms for elliptic curves

  2008influential reference
• Homomorphisms of abelian varieties over nite elds

  2008cited by this paper
• Expander graphs based on GRH with an application to elliptic curve cryptography

  2008cited by this paper
• CONSTRUCTING SUPERSINGULAR ELLIPTIC CURVES

  2007cited by this paper
• Claw finding algorithms using quantum walk

  2007cited by this paper
• Public-Key Cryptosystem Based on Isogenies

  2006cited by this paper
• Hard Homogeneous Spaces

  2006cited by this paper
• Fast algorithms for computing isogenies between elliptic curves

  2006influential reference
• Promised and Distributed Quantum Search

  2005cited by this paper
• Accelerated Verification of ECDSA Signatures

  2005cited by this paper
• On the Correspondence between Supersingular Elliptic Curves and maximal quaternionic Orders

  2004cited by this paper
• The On-Line Encyclopedia of Integer Sequences

  2003cited by this paper
• Elementary number theory, group theory, and Ramanujan graphs

  2003cited by this paper
• Extending the GHS Weil Descent Attack

  2002cited by this paper
• The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems

  2002cited by this paper
• Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels

  2001cited by this paper
• Low-Weight Binary Representations for Pairs of Integers

  2001cited by this paper
• Differential power analysis, advances in cryptology-CRYPTO'99

  1999cited by this paper
• The Pohlig-Hellman Method Generalized for Group Structure Computation

  1999influential reference
• Differential Power Analysis

  1999cited by this paper
• Constructing Isogenies between Elliptic Curves Over Finite Fields

  1999cited by this paper
• Endomorphism rings of elliptic curves over finite fields

  1996cited by this paper
• A New Identification Scheme Based on the Perceptrons Problem

  1995cited by this paper
• Designing Identification Schemes with Keys of Short Size

  1994cited by this paper
• Discrete Groups

  1994cited by this paper
• Discrete groups, expanding graphs and invariant measures

  1994cited by this paper
• EFFECTIVE VERSIONS OF THE CHEBOTAREV DENSITY THEOREM FOR FUNCTION FIELDS

  1994cited by this paper
• A New Identification Scheme Based on Syndrome Decoding

  1993cited by this paper
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

  1991cited by this paper
• Ramanujan graphs and Hecke operators

  1990influential reference
• Some Applications of Modular Forms

  1990cited by this paper
• Zero-knowledge proofs of identity

  1987cited by this paper
• Speeding the Pollard and elliptic curve methods of factorization

  1987cited by this paper
• The arithmetic of elliptic curves

  1986cited by this paper
• A public key cryptosystem and a signature scheme based on discrete logarithms

  1984cited by this paper
• Endomorphisms of abelian varieties over finite fields

  1966cited by this paper
• Ramanujan Graphs

  1965cited by this paper
• La méthode des graphes

  1965cited by this paper
• Elementary number theory

  1959cited by this paper
• An Efficient Identification Scheme Based on Permuted Kernels ( extended abstract )

  year unknowncited by this paper

• Return of the Kummer: a toolbox for genus 2 cryptography

  2026cites this paper
• Isogeny-based cryptography: A comprehensive review on advancements, analysis of attacks, and future directions

  2026cites this paper
• SoK: Evolution of the Key Encapsulation Mechanism’s Role in Cryptographic Migrations for IoT Systems

  2026cites this paper
• Timed Commitments and Timed Encryption: Generic Constructions and Instantiations from Isogenies

  2026cites this paper
• Hensel-lifting black-box algorithms and fast trace computation for elliptic-curve endomorphisms

  2026influential citation
• Future Digital Identity Management With Quantum Secure Blockchain

  2026cites this paper
• POKEx: Performance Analysis of POKÉ-Key Exchange and SIDH-Variants

  2026cites this paper
• Key exchange based on three-dimensional Segre products and their projections

  2025cites this paper
• Modular Forms and Hecke Operators for Post-Quantum Cryptography

  2025cites this paper
• A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies

  2025cites this paper
• A Survey of Post-Quantum Oblivious Protocols

  2025cites this paper
• How (not) to Build Identity-Based Encryption from Isogenies

  2025cites this paper
• Deterministic algorithms for class group actions

  2025cites this paper
• An Efficient Quantum Blockchain Framework With Edge Computing for Privacy-Preserving 6G Networks

  2025cites this paper
• Establishing Quantum-Classical Trust: Initialization and Key Exchange Phase

  2025cites this paper
• Efficient and Secure Montgomery Curve Based Substitution Box Generator With Optimal Nonlinearity

  2025cites this paper
• Quantum-Safe Blockchains with Supersingular Isogenies

  2025cites this paper
• Leveled Isogeny Problems with Hints

  2025cites this paper
• Explicit class field generation via chains of modular polynomials

  2025cites this paper
• Advancing Data Security: A Comparative Study of Classical and Post-Quantum Encryption Algorithms

  2025cites this paper
• Recovery for secret key in CTIDH-512 through Fault Injection Attack

  2025cites this paper
• WaterSQI and PRISMO: Quaternion Signatures for Supersingular Isogeny Group Actions

  2025cites this paper
• SQIsign2D2: New SQIsign2D Variant by Leveraging Power Smooth Isogenies in Dimension One

  2025cites this paper
• Integrating MQTT protocol to improve the performance using dynamic lightweight key sharing protocol for secure IoT communications

  2025cites this paper
• Machine Learning and Side-Channel Attacks on Post-Quantum Cryptography

  2025cites this paper
• Performance evaluation of isogeny-based digital signature algorithms: introducing FIBS—fast isogeny-based digital signature*

  2025influential citation
• SISE: Supersingular Isogeny-Based Symmetric Encryption

  2025cites this paper
• Efficient Algorithms for Isogeny Computation on Hyperelliptic Curves: Their Applications in Post-Quantum Cryptography

  2025cites this paper
• The Chaotic Entropic Expansion (CEE): A Transparent Post-Quantum Data Confidentiality Primitive via Entropic Chaotic Maps

  2025cites this paper
• Simpler and Faster Pairings from the Montgomery Ladder

  2025cites this paper
• Engel p-adic Isogeny-based Cryptography over Laurent Series: Foundations, Security, and an ESP32 Implementation

  2025cites this paper
• Enhancing Post-Quantum Cryptographic Protocols with Quantum-Resistant Key Exchange Mechanisms

  2025cites this paper
• An Internet Messenger Using Post-Quantum Cryptography Algorithms Based on Isogenies of Elliptic Curves

  2025cites this paper
• A Constant-Time Hardware Architecture for the CSIDH Key-Exchange Protocol

  2025cites this paper
• Optimized Constant-Time Implementation of terSIDH

  2025cites this paper
• Kani's lemma from Clifford algebra

  2025cites this paper
• Compact, Efficient and CCA-Secure Updatable Encryption from Isogenies

  2025cites this paper
• Multi-party post-quantum key exchange schemes

  2025cites this paper
• Constant-time Quaternion Algorithms for SQIsign

  2025cites this paper
• Post-Quantum Threshold Oblivious Signature

  2025cites this paper
• Erebor and Durian: Full Anonymous Ring Signatures from Quaternions and Isogenies

  2025cites this paper
• Multisignature on Isogenies of Elliptic Curves with Participant Masking and Authentication

  2025cites this paper
• Optimizing tweaked Montgomery curves and its application in isogeny-based cryptography

  2025cites this paper
• Enabling Robust Security in MQTT-Based IoT Networks with Dynamic Resource-Aware Key Sharing

  2025cites this paper
• SQIsign2DPush: Faster Signature Scheme Using 2-Dimensional Isogenies

  2025cites this paper
• Isogeny-based key exchange from orientations of large discriminant

  2025cites this paper
• Reusable Fuzzy Extractor from Isogeny-Based Assumptions

  2025cites this paper
• Implementing the Elliptic Curve CSIDH Cryptosystem

  2025cites this paper
• New types of formula for isogenies between elliptic curves

  2025cites this paper
• Accelerating Isogeny Walks for VDF Evaluation

  2025influential citation
• HELP: Everlasting Privacy through Server-Aided Randomness

  2025cites this paper
• HPQKE: Hybrid Post-Quantum Key Exchange Protocol for SSH Transport Layer From CSIDH

  2025cites this paper
• Exploring Post-Quantum Cryptography: Evaluating Algorithm Resilience against Global Quantum Threats

  2025cites this paper
• Quantum-resistant modifications to ECDSA for blockchain security

  2025cites this paper
• A survey on isogeny-based cryptographic protocols

  2025influential citation
• Gross lattices of supersingular elliptic curves

  2025cites this paper
• Computing isogeny on Edwards curves for quantum safe cryptography

  2025cites this paper
• Advancements in Isogeny-Based Cryptography: A Mathematical Approach to Post-Quantum Security

  2025cites this paper
• Efficient Implementations of Square-root Vélu's Formulas

  2025cites this paper
• Performance Analysis of Dynamic Light Weight Cryptographic Algorithm for Message Queuing Telemetry Transport based IoT Communications

  2025cites this paper
• INKE: Fast Isogeny-Based PKE using Intermediate Curves

  2025influential citation
• Universal Blind and Verifiable Delegated Quantum Computation with Classical Clients

  2025cites this paper
• Quantum Secure Multiparty Computation: Bridging Privacy, Security, and Scalability in the Post-Quantum Era

  2025cites this paper
• Postgraduate Cybersecurity Education for Non-Specialist Professionals

  2025cites this paper
• Optimization of isogeny computation algorithms for post-quantum cryptography

  2025cites this paper
• Side-channel Information Leakage with CPU Frequency Scaling, but without CPU Frequency

  2025cites this paper
• An Improved ChaCha Algorithm Based on Quantum Random Number

  2025cites this paper
• SWOOSH: Efficient Lattice-Based Non-Interactive Key Exchange

  2024cites this paper
• A Survey and Comparison of Post-Quantum and Quantum Blockchains

  2024cites this paper
• Optimizations and Practicality of High-Security CSIDH

  2024cites this paper
• Towards Optimally Small Smoothness Bounds for Cryptographic-Sized Smooth Twins and Their Isogeny-Based Applications

  2024cites this paper
• RISC-V Instruction Set Extensions for Multi-Precision Integer Arithmetic : A Case Study on Post-Quantum Key Exchange Using CSIDH-512

  2024cites this paper
• High-Speed FPGA Implementation of Modular Multiplication Over Prime Field

  2024cites this paper
• On random sampling of supersingular elliptic curves

  2024cites this paper
• Isogeny-based Proxy Signature

  2024cites this paper
• Sharing the Path: A Threshold Scheme from Isogenies and Error Correcting Codes

  2024cites this paper
• Practical Fault Injection Attacks on Constant Time CSIDH and Mitigation Techniques

  2024cites this paper
• Evaluation framework for quantum security risk assessment: A comprehensive strategy for quantum-safe transition

  2024cites this paper
• End-to-end QKD network with non-localized trust

  2024cites this paper
• A Comprehensive Review of Post-Quantum Cryptography: Challenges and Advances

  2024cites this paper
• Isogeny interpolation and the computation of isogenies from higher dimensional representations

  2024cites this paper
• Future-Proofing Security for UAVs With Post-Quantum Cryptography: A Review

  2024cites this paper
• Towards efficient and secure quantum-classical communication networks

  2024cites this paper
• Lightweight Authentication Scheme Based on ECC for IoT

  2024cites this paper
• The Supersingular Isogeny Path and Endomorphism Ring Problems: Unconditional Reductions

  2024cites this paper
• A Faster Software Implementation of SQIsign

  2024cites this paper
• Quantum Group Actions

  2024cites this paper
• Faster Proofs and VRFs from Isogenies

  2024cites this paper
• Optimized One-Dimensional SQIsign Verification on Intel and Cortex-M4

  2024influential citation
• The Security of SSH Protocol Public Key Sharing in the Post-Quantum Era

  2024cites this paper
• Video-Based Cryptanalysis: Extracting Cryptographic Keys from Video Footage of a Device’s Power LED Captured by Standard Video Cameras

  2024cites this paper
• Computational Analysis of Plausibly Post-Quantum-Secure Recursive Arguments of Knowledge

  2024cites this paper
• MODRED: A code-based non-interactive key exchange protocol

  2024cites this paper
• More Efficient Isogeny Proofs of Knowledge via Canonical Modular Polynomials

  2024cites this paper
• Qcrypt: Leveraging Post-Quantum Cryptography for Enhanced Security of Data at Rest

  2024cites this paper
• ZKFault: Fault attack analysis on zero-knowledge based post-quantum digital signature schemes

  2024cites this paper
• Securing the future: exploring post-quantum cryptography for authentication and user privacy in IoT devices

  2024cites this paper
• Full Quantum Equivalence of Group Action DLog and CDH, and More

  2024cites this paper
• Quantum Cryptography in 5G Networks: A Comprehensive Overview

  2024cites this paper
• Faster Complete Addition Laws for Montgomery Curves

  2024cites this paper