PaperlayerView exact revision on arXiv

Source-linked AI summary

Mathematics of Isogeny Based Cryptography

Luca De Feo

arXiv:1711.04062v1cs.CRmath.NT

TL;DR

Isogeny-based cryptography centers on a notoriously difficult path problem, for which only general algorithms exponential in log #E are known. These notes describe controlling supersingular-curve group structure for SIDH and report classical security of ~n/4 bits and quantum security of ~n/6 qubits when log2 p = n.

  • Problem

    The isogeny path problem is notoriously difficult, with only algorithms exponential in log #E known in general.

    Source: §12 · p. 24

  • Method

    For SIDH, the notes address two problems by controlling the group structure of supersingular curves, a task described as elementary there.

    Source: §14.2 · p. 33

  • Results

    With log2 p = n, the cited best-known SIDH attacks imply classical security of ~n/4 bits and quantum security of ~n/6 qubits.

    Source: §14.2 · p. 35

  • Takeaways & Limitations

    Knowing the endomorphism rings of E and E/⟨A⟩ lets an attacker solve the isogeny path problem and then break SIDH in polynomial time.

    Source: §15 · p. 37

    Meeting the homogeneous-space protocol’s distribution and key-space conditions makes it essentially equivalent to Diffie-Hellman, only less efficient.

    Source: §14.1 · p. 28

Abstract

from arXiv · show

These lectures notes were written for a summer school on Mathematics for post-quantum cryptography in Thi\`es, Senegal. They try to provide a guide for Masters' students to get through the vast literature on elliptic curves, without getting lost on their way to learning isogeny based cryptography. They are by no means a reference text on the theory of elliptic curves, nor on cryptography; students are encouraged to complement these notes with some of the books recommended in the bibliography. The presentation is divided in three parts, roughly corresponding to the three lectures given. In an effort to keep the reader interested, each part alternates between the fundamental theory of elliptic curves, and applications in cryptography. We often prefer to have the main ideas flow smoothly, rather than having a rigorous presentation as one would have in a more classical book. The reader will excuse us for the inaccuracies and the omissions.

Introduction · Elliptic curves and cryptography · 1 Elliptic curves

The notes trace isogeny-based cryptography’s development amid the prospect of quantum attacks and introduce elliptic-curve foundations alongside cryptographic applications. They define elliptic curves and their group structure, then summarize torsion and the Mordell–Weil theorem and rank problem.

Introduction

  • Isogeny-based cryptography emerged in the 2000s from ECC, and interest shifted toward it as quantum computers threatened ECC and pairing-based cryptography.ECC began in the 1980s and gained traction in the 1990s; the notes identify work by Couveignes, Teske, and Rostovtsev & Stolbunov as initiating isogeny-based cryptography.Source: Introduction · p. 1
  • The notes review elliptic-curve and isogeny theory before presenting major isogeny-based systems and their cryptographic properties.Source: Introduction · p. 1

Elliptic curves and cryptography

  • This part reviews basic elliptic-curve theory and two classic cryptographic applications, with further reading cited for both topics.The notes refer readers to for elliptic curves and for cryptographic applications.Source: Elliptic curves and cryptography · p. 3

1 Elliptic curves

  • With characteristic different from 2 and 3, an elliptic curve is a genus-1 projective curve with a specified point, isomorphic to a Weierstrass equation.The isomorphism sends the specified point to the point at infinity.Source: §1 · p. 3
  • Because a line intersects a cubic elliptic curve in three points counting multiplicity, requiring collinear triples to sum to zero defines its Abelian group law.The point at infinity acts as the identity; the group of k-rational points is denoted E(k).Source: §1 · p. 4
  • When the characteristic of k does not divide m, the m-torsion group is isomorphic to (Z/mZ)^2; in positive characteristic, E[p] distinguishes ordinary from supersingular curves.Ordinary means E[p] ≃ Z/pZ, while supersingular means E[p] ≃ {O}.Source: §1 · pp. 4–5
  • For elliptic curves over number fields, E(k) is finitely generated, but its rank remains difficult to determine and is addressed by the Birch and Swinnerton-Dyer conjecture.Algorithms compute the rank of most elliptic curves over number fields; the conjecture is identified as a Clay Millennium Prize Problem.Source: §1 · p. 5

2 Maps between elliptic curves · 3 Elliptic curves over finite fields

The notes characterize maps between elliptic curves through isomorphisms, isogenies, and endomorphisms. For curves over finite fields, they introduce Frobenius and state that equal point counts over the base field characterize isogenous curves.

2 Maps between elliptic curves

  • Two elliptic curves are isomorphic over the algebraic closure if and only if they have the same j-invariant.The notes define the j-invariant for a curve in the stated Weierstrass form.Source: §2 · p. 5
  • A twist is an isomorphism over the algebraic closure that is not defined over the base field; curves defined over k that are isomorphic over the closure become isomorphic over an extension of degree dividing 6.Every curve has a quadratic twist, while curves with j-invariant 0 or 1728 also have cubic, sextic, and quartic twists.Source: §2 · p. 5
  • An isogeny is a surjective group morphism between elliptic curves that need not be invertible, and it is also an algebraic map.The notes call two curves isogenous when an isogeny exists between them and state that this relation is later shown to be an equivalence relation.Source: §2 · pp. 5–6
  • An endomorphism is an isogeny from a curve to itself; multiplication by m has kernel E[m], and for most curves the only endomorphisms are scalar multiplications.The notes also indicate that nontrivial endomorphisms will be considered later.Source: §2 · p. 6

3 Elliptic curves over finite fields

  • Every elliptic curve over a finite field has a Frobenius endomorphism, which raises each projective coordinate to the q-th power.The map is given as (X : Y : Z) ↦ (X^q : Y^q : Z^q).Source: §3 · p. 6
  • An elliptic curve’s number of points over its base field determines its number of points over every finite extension of that field.The notes connect this fact to the Weil conjectures.Source: §3 · p. 6
  • Over a finite field k, two elliptic curves are isogenous over k if and only if they have the same number of k-rational points.The notes identify this as Theorem 13 (Sato-Tate).Source: §3 · p. 6

4 Application: Diffie-Hellman key exhange · 5 Application: Elliptic curve factoring method

The section explains how elliptic curves support Diffie–Hellman key exchange and Lenstra’s method for factoring integers. It describes the security assumptions behind the former and the mechanism and practical advantages of the latter.

4 Application: Diffie-Hellman key exhange

  • Introduced by Diffie and Hellman in the 1970s, the protocol lets two parties agree on a secret; its public parameters include a large prime p and generator g.Source: §4 · p. 7
  • In a cyclic group G, an eavesdropper knows g and public data A and B and seeks the shared secret g^ab; the protocol’s strength rests on discrete-logarithm hardness.Source: §4 · p. 7
  • Generic discrete-log algorithms take O(√q) steps, but no better-than-generic algorithms are known for elliptic-curve subgroups, motivating Miller and Koblitz to propose them for key exchange.Source: §4 · p. 7

5 Application: Elliptic curve factoring method

  • Lenstra’s ECM has intermediate operation complexity between Pollard’s and Coppersmith’s factoring algorithms, uses constant memory, parallelizes easily, and is typically used for medium-sized prime factors.Source: §5 · p. 8
  • Pollard’s p−1 method uses an exponent multiple of p−1 to obtain a factor via a gcd, but its complexity grows exponentially with the bound B, limiting it to p−1 with small prime factors.Source: §5 · p. 8
  • ECM generalizes p−1 factoring by replacing multiplicative groups with E(Fp) and E(Fq); although #E(Fp) must have small prime factors, changing curves permits repeated attempts.Source: §5 · p. 8
  • ECM derives a curve from a random point to avoid a square-root computation modulo N, and a failed inversion of a nonunit in Z/NZ yields a factor of N.Source: §5 · pp. 8–9

Isogenies and applications · 6 Elliptic curves over C

The section relates complex tori to elliptic curves through lattice uniformization and the modular j-invariant. It then describes isogenies using lattice maps and summarizes their degree, kernel, and duality properties.

6 Elliptic curves over C

  • Complex lattices are homothetic exactly when they have the same modular j-invariant, classifying complex tori up to homothety.Source: §6 · p. 11
  • The Weierstrass ℘ map identifies C/Λ with an elliptic curve over C as both a Riemann surface and a group, linking their isomorphism classes.The text also states that the corresponding j-invariants agree and gives a uniformization theorem for nonsingular Weierstrass coefficients.Source: §6 · p. 12
  • The complex-torus model shows why E[m] ≃ (Z/mZ)^2, while multiplication by m gives an endomorphism because the associated lattices are homothetic.Source: §6 · p. 12
  • Isogenies between elliptic curves correspond to holomorphic group maps induced by complex scalings that relate their lattices by inclusion.Source: §6 · p. 13
  • Every isogeny has a unique dual; in the illustrated degree-3 example, composing the isogeny with its dual gives multiplication by 3, up to homothety.Both isogenies in the example have kernels of size 3.Source: §6 · pp. 13–14
  • An isogeny's degree is the finite function-field extension degree; purely inseparable isogenies have degree a power of the characteristic, and any isogeny factors into separable and purely inseparable parts.Source: §6 · p. 14
  • For a separable isogeny, the degree equals the kernel size and every fiber has that size; its kernel uniquely determines the isogeny and quotient curve.Source: §6 · p. 14

7 The endomorphism ring

Deuring’s theorem classifies elliptic-curve endomorphism rings as quadratic orders or, for supersingular curves in positive characteristic, maximal quaternion orders. Over finite fields, Frobenius provides a quadratic relation whose trace determines the curve’s cardinality.

7 The endomorphism ring

  • Deuring classifies End(E) as an order in an imaginary quadratic field or, only in positive characteristic, a maximal order in a quaternion algebra ramified at p and ∞.The first case is called complex multiplication; the second means E is supersingular.Source: §7 · p. 15
  • In positive characteristic, a curve that is not supersingular is ordinary and necessarily has complex multiplication.Source: §7 · p. 15
  • For a finite-field curve, Frobenius satisfies a quadratic equation, and its trace t gives the cardinality #E = q + 1 − t.The discriminant Dπ = t² − 4q is negative.Source: §7 · p. 15
  • In the ordinary finite-field case, the endomorphism algebra is K = Q[√Dπ], where Dπ = t² − 4q.The orders between Z[π] and OK have conductors dividing f when Dπ = f²dK.Source: §7 · p. 15
  • For a quadratic field K, each order is Z + fOK, with discriminant f²dK; O ⊂ O′ exactly when f′ divides f.Here f is the conductor, and OK is the maximal order; an order is a finitely generated Z-module subring of maximal dimension.Source: §7 · p. 15

8 Application: point counting

Hasse’s theorem relates a finite-field elliptic curve’s cardinality to its Frobenius trace but does not provide an algorithm to compute either. Schoof’s algorithm and the later Atkin–Elkies optimizations compute the trace using Frobenius action on torsion points.

Application: point counting

  • Schoof’s algorithm [63] computes the Frobenius trace modulo small primes and reconstructs it with the Chinese remainder theorem, representing torsion computations modulo the division polynomial ψℓ.The division polynomial vanishes on E[ℓ], enabling the formal computation on the whole ℓ-torsion group.Source: §8 · p. 16
  • Schoof’s algorithm runs in polynomial time in log #E(k), while Atkin–Elkies optimizations exploit Frobenius’s matrix action on rank-two E[ℓ].When the characteristic polynomial splits modulo ℓ with distinct roots, this is the Elkies case; when it does not split, it is the Atkin case, and SEA treats the cases differently.Source: §8 · pp. 16–17
  • Elkies’ method reduces the working polynomial degree from (ℓ^2 − 1)/2 in Schoof’s algorithm to approximately ℓ, improving efficiency by representing an eigenspace through an isogeny kernel.In the Elkies case, an eigenspace is the kernel of a degree-ℓ isogeny; determining the corresponding curve allows recovery of the eigenvalue λ.Source: §8 · p. 17

9 Isogeny graphs

The section defines isogeny graphs on j-invariants and describes how degree-ℓ isogenies structure them. In the ordinary case, isogenies between endomorphism orders and their conductor determine a volcano-shaped graph.

Isogeny graphs

  • An isogeny graph has j-invariants as nodes and isogenies as edges; dual isogenies give each isogeny a reverse of the same degree, so graphs are usually undirected.Isogeny classes cannot contain both ordinary and supersingular curves.Source: §9 · p. 17

Degree-ℓ isogenies

  • Over the algebraic closure, E has ℓ + 1 distinct degree-ℓ isogenies; over k, E has 0, 1, 2, or ℓ + 1 degree-ℓ isogenies.Source: §9 · pp. 17–18

Degree-p isogenies

  • For degree p, an ordinary curve has a unique separable isogeny, while a supersingular curve has none; the map (x, y) ↦ (x^p, y^p) is purely inseparable of degree p to E^(p).E^(p) has equation y^2 = x^3 + a^p x + b^p.Source: §9 · p. 18

Ordinary isogeny graphs

  • For prime-degree isogenies between ordinary curves, the corresponding orders are nested: index ℓ in the target order defines an ascending isogeny, and index ℓ in the source defines a descending one.Vertical isogenies can only exist for primes dividing the conductor of Z[π], so the horizontal case is generic.Source: §9 · p. 18
  • Ordinary isogeny graphs form a horizontal cycle—possibly one point in the Atkin case or two in the ramified case—with a descending tree of height v_ℓ(fπ).These structures are called isogeny volcanoes.Source: §9 · p. 19

10 Application: computing irreducible polynomials

The section presents an elliptic-curve and isogeny-based construction of irreducible polynomials, extending multiplicative-group methods to degrees ℓ^e. It describes the construction’s conditions, iteration, implementation ingredient, and related exercises.

10 Application: computing irreducible polynomials

  • Random polynomial testing is nondeterministic and has average complexity quadratic in both the polynomial degree and log q.Source: §10 · p. 19
  • For odd ℓ∤(q−1), ℓ≪q+1+2√q, and P∈E′(Fq)\[ℓ]E′(Fq), Couveignes and Lercier use an ℓ-isogeny fiber to obtain an irreducible polynomial.They decompose [ℓ] into isogenies and use the polynomial vanishing on φ⁻¹(P); the stated conditions ensure the relevant rational ℓ-torsion is cyclic.Source: §10 · pp. 19–20
  • Vélu’s formulas provide a rational-function representation of φ, a technical ingredient needed to compute the polynomial.Source: §10 · p. 20
  • Iterating the construction yields degree ℓ^e; for Elkies ℓ and horizontal φ_i, their composition forms an isogeny cycle, the crater of a volcano.Figure 8 summarizes the algorithm and depicts the computed isogeny cycle.Source: §10 · p. 20, Figure 8 · p. 21

Exercices

  • Exercises ask for proofs concerning Lemma 16, division-polynomial divisibility, the Sato–Tate isogeny criterion, dual-isogeny directions, and volcano-height formulas.Source: Exercices · p. 21

Cryptography from isogeny graphs · 11 Expander graphs

Isogeny-based cryptography relies on large isogeny graphs, whose expansion properties are presented as cryptographically important. The section connects spectral and edge expansion to graph connectivity, short diameter, and random-walk mixing, then gives expansion results for supersingular and horizontal-isogeny graphs.

11 Expander graphs

  • Isogeny-based cryptography relies fundamentally on large isogeny graphs, with cryptographically interesting properties usually tied to their expansion.Source: §11 · p. 22
  • Spectral expansion describes graph structure through adjacency-matrix eigenvalues, while edge expansion measures how strongly vertex subsets connect to their complements.Source: §11 · pp. 22–23
  • Edge expansion is zero exactly for disconnected graphs, and the discrete Cheeger inequality links edge expansion to spectral expansion.Source: §11 · p. 23
  • Expanders have short diameter and rapidly mixing walks; in particular, their diameter is O(log n), and sufficiently long walks reach any vertex subset with probability at least half its uniform probability.The section also notes their uses in pseudorandom generators, error-correcting codes, probabilistically checkable proofs, and cryptographic primitives.Source: §11 · p. 23
  • The graph of supersingular curves over the algebraic closure of Fp with ℓ-isogenies is connected, (ℓ + 1)-regular, and Ramanujan; their j-invariants lie in Fp2.Source: §11 · pp. 23–24
  • Under the generalized Riemann hypothesis, the graph of elliptic curves over Fq with complex multiplication by an order, joined by horizontal prime-degree isogenies within the stated logarithmic bound, is regular and a one-sided ε-expander for ε independent of the order and q.The theorem assumes the graph is non-empty.Source: §11 · p. 24

12 Isogeny graphs in cryptanalysis

Isogeny paths between elliptic curves of equal size are a central problem in isogeny-based cryptography, and general algorithms are exponential in log #E. Meet-in-the-middle walks can find paths, enabling attacks that transfer discrete logarithms from immune curves to weak curves in the same isogeny class.

12 Isogeny graphs in cryptanalysis

  • Vélu’s formulas compute an isogeny with kernel G in ˜O(#G) operations, nearly optimal for an output of size O(#G).When the isogeny composes many small-degree isogenies, rational fractions may be represented more compactly and computation can cost logarithmic time in #G.Source: §12 · p. 24
  • For explicit isogenies of known degree d, Elkies’s algorithms cost O(d3) generally and ˜O(d) in the SEA context [25, 26] [7, 50], while alternatives cost O(d2) generally [23] [21].The isogeny is typically unique up to automorphisms.Source: §12 · p. 24
  • Finding an isogeny path between equal-sized curves is notoriously difficult; only algorithms exponential in log #E are known in general.The problem asks for an isogeny of smooth degree, and it is the isogeny problem most often encountered in isogeny-based cryptography.Source: §12 · p. 24
  • The GHS extension attack reaches any curve in an ordinary isogeny class in O(#E^1/4) steps, improving on a generic discrete-log attack.Only a small fraction of curves in the class are vulnerable; finding an isogeny from an immune curve to a weak one transfers the discrete-log problem.Source: Figure 9 · p. 25, §12 · p. 25
  • A meet-in-the-middle attack uses random walks on an expander graph and expects a collision after roughly O(√#G) steps.The walks start from each curve; their composition yields the desired isogeny when they meet.Source: §12 · pp. 24–25

13 Provably secure hash functions

The CGL construction hashes by walking without backtracking on an expander graph, with input bits choosing edges. For supersingular-curve graphs, preimage and collision problems correspond to isogeny-path and endomorphism problems, but the construction is slow and weaknesses could potentially enable backdoors in standardized parameters.

13 Provably secure hash functions

  • CGL hashes a bit string by taking a deterministic, non-backtracking walk from a start vertex in an expander graph and outputting the arrival vertex.For a 3-regular graph, each bit selects one of the two edges that do not return to the previous vertex.Source: §13 · p. 25
  • The walk must exceed the graph’s mixing length, while preimage resistance means finding a path from the start to a given vertex and collision resistance means finding a non-trivial loop back to the start.Longer-than-mixing walks alone do not guarantee a cryptographically strong hash function.Source: §13 · p. 25
  • CGL’s Cayley-graph option was broken shortly afterwards; with supersingular-curve graphs, preimage finding is an isogeny-path problem and collision finding is equivalent to computing a non-trivial endomorphism of the start curve [8].The construction’s security is therefore reducible to well-defined mathematical problems believed hard.Source: §13 · p. 26
  • The CGL hash has not attracted practitioners because it is considerably slower than popular NIST-standardized hash functions, and highlighted weaknesses could potentially enable backdoors in standardized parameters.Source: §13 · p. 26

14 Post-quantum key exchange

The section surveys post-quantum key exchange based on isogenies, including protocols using random walks in isogeny graphs and SIDH’s use of secret isogenies and auxiliary torsion-point images to derive a shared curve. It also addresses short isogeny walks, attack approaches, efficiency and quantum-security challenges, and security parameter estimates.

14 Post-quantum key exchange

  • The protocols are motivated by Shor’s algorithm [65], which solves factoring and discrete logarithms in polynomial time on a quantum computer; both are less efficient than ECDH.Their shared-curve approach uses secret random walks whose algebraic steps must commute, rather than an arbitrary labeling of graph edges.Source: §14 · p. 26

14.1 Hard homogeneous spaces

  • Ordinary horizontal isogenies realize a class-group action that acts freely and transitively on curves with complex multiplication by an order, enabling a random-walk key exchange on a Schreier graph.Participants publish endpoint curves and apply their secret walks to the other’s endpoint; the shared result follows because the steps commute. The notes describe the basic Schreier-graph construction as a twisted classical Diffie–Hellman protocol.Source: §14.1 · pp. 27–30
  • The Rostovtsev–Stolbunov protocol is already very slow, mainly due to its relatively large isogeny degree set L; adapted quantum algorithms solve the ordinary isogeny path problem in subexponential time.The passages say walks should be longer than the mixing length, ∼log q, and ask for #L ∼log q/loglog q.Source: §14.1 · p. 31

14.2 Supersingular Isogeny Diffie-Hellman

  • SIDH uses two distinct isogeny graphs on the same supersingular j-invariants, with Alice and Bob walking using different small prime degrees; supersingular graphs can be expanders with one degree.The protocol was first proposed in. The notes also point to quaternion-algebra structures underlying supersingular isogenies as relevant to assessing security.Source: §14.2 · pp. 31–32
  • SIDH encodes each secret walk as a cyclic subgroup, but subgroup points may require exponentially much information to represent, and the shared quotient diagram alone does not hide secrets.The notes say both difficulties are addressed by carefully controlling the group structure of supersingular curves, which is elementary there but hard in the ordinary case.Source: §14.2 · pp. 32–33
  • Choosing p so E(Fq) ≃ (Z/(p ± 1)Z)² provides large torsion subgroups, allowing a single point to represent an isogeny walk of length eA.The notes say primes of the form p = ℓA^eA ℓB^eB f ∓ 1 are abundant in practice and can be chosen with f = 1.Source: §14.2 · p. 33
  • Alice and Bob choose secret subgroups and compute secret isogenies, then use the other party’s published torsion-point images to complete the shared-curve computation.The protocol’s setup fixes p, a supersingular curve over Fp², and public bases for the respective torsion groups.Source: §14.2 · pp. 33–34
  • Alice and Bob publish images of each other’s public torsion bases, enabling each to compute the shared isogeny kernel from the other party’s secret without learning that secret.The published images are conjectured not to help an attacker compute the shared curve E/⟨A, B⟩.Source: §14.2 · p. 34
  • SIDH’s walks are much shorter than the supersingular isogeny graph’s diameter: the graph has size O(p), while each party’s public-key space has size O(√p), and the security effect is unclear.The notes say this constrains the isogeny walks and leave open how that affects protocol security.Source: §14.2 · p. 34
  • With log2 p = n, the notes estimate SIDH security at approximately n/4 classical bits and n/6 quantum qubits, and call the discussed attacks the best known.They describe a meet-in-the-middle attack on published j-invariants and a quantum-oracle attack due to Tani; the notes say the short walks are expected to yield only one collision, Alice’s secret isogeny. They estimate that a 768-bit prime is needed for a 128-qubit and 192-bit secure system, typically using ℓA = 2 and ℓB = 3 for efficiency.Source: §14.2 · pp. 34–35

15 Further topics in isogeny based cryptography

The section surveys supersingular-isogeny cryptography, covering SIDH implementation and security, derived encryption and signature protocols, and remaining research challenges. It also includes exercises on earlier material.

15 Further topics in isogeny based cryptography

  • SIDH implementation optimizes prime-field arithmetic, Fp2 arithmetic, elliptic-curve formulas, and inversions using special primes, Montgomery models, and projective coordinates.The cited techniques include primes of the form p = 2^a3^b − 1, optimized curve operations, and avoiding inversions.Source: §15 · pp. 35–36
  • Computing and evaluating SIDH’s secret isogeny from a kernel generator uses a quasi-linear algorithm, identified as the most novel optimization.The notes refer readers to and for implementation details.Source: §15 · p. 36
  • SIDH can be made practical, but remains one or two orders of magnitude slower than other post-quantum competitors; its key sizes were the shortest among candidates at the time of writing.Compression can shrink keys further, while efficiently exploiting the larger isogeny graph to make keys shorter remains open.Source: §15 · p. 36
  • Assuming SSDDH is hard, SIDH key exchange is provably secure against passive adversaries, and the best known SSDDH algorithms have exponential complexity even on quantum computers.Passive adversaries can observe messages but do not modify them.Source: §15 · p. 36
  • Because SSDDH is a special isogeny-path instance, an efficient solution to a related problem can reveal SIDH’s secret isogeny and break SIDH without solving the generic path problem.The notes also report a polynomial-time route from knowing the endomorphism rings of the starting and quotient curves to solving the path problem and breaking SIDH.Source: §15 · pp. 36–37
  • Polynomial-time key-recovery attacks target static-key, leakage, and unbalanced SIDH variants, while a quantum subexponential attack applies when both curves are over Fp.The notes say SSDDH itself remained unbroken at the time of writing.Source: §15 · p. 37
  • An El Gamal-like encryption protocol derived from SIDH is IND-CPA secure under SSDDH, and a generic transformation can yield an IND-CCA-secure key encapsulation mechanism.The notes say achieving IND-CCA security is harder, citing the static-key attack.Source: §15 · p. 37
  • Fiat-Shamir can derive signatures from the zero-knowledge protocol, but protocols require iterating the basic building block hundreds of times; efficient signatures from isogeny assumptions remain open, and Schnorr and ECDSA need a group law on public data.The protocol is secure and zero-knowledge under SSDDH3 and DSSP.Source: §15 · pp. 37–38
Loading 1711.04062v1…