Skip to main content

logicaffeine_proof/
isogeny.rs

1//! # Certified isogeny torsion-image witnesses — the SIDH/SIKE public-data structure, in the prover
2//!
3//! An SIDH/SIKE public key is not merely the codomain curve `E' = φ(E₀)`: to make the scheme a key
4//! exchange it also publishes the **images of a public torsion basis**, `φ(P), φ(Q)`. That auxiliary
5//! torsion data is exactly what the 2022 Castryck–Decru attack weaponized. Its internal consistency is
6//! governed by the Weil pairing's isogeny-compatibility law:
7//!
8//! ```text
9//!     e_N(φ(P), φ(Q)) = e_N(P, Q)^{deg φ}.
10//! ```
11//!
12//! This module bakes that relation into the prover as a re-checkable certificate — the same discipline as
13//! the rest of the campaign ([`crate::ait::DescriptionBound`], `LinearRigidityCert`, …): a
14//! [`TorsionImageWitness`] whose [`verify`](TorsionImageWitness::verify) re-derives the pairings on *both*
15//! curves from scratch and checks the law. It is the exact check an SIDH verifier performs, and the
16//! structural symmetry the break pulls on.
17
18use crate::elliptic::{torsion_basis, weil_pairing, Curve, Isogeny, Point};
19use crate::factor::modpow;
20use logicaffeine_base::BigInt;
21
22/// A re-checkable witness that an isogeny `φ: E → E'` is consistently specified by its action on an
23/// `N`-torsion basis — the SIDH/SIKE public-key format.
24#[derive(Clone, Debug)]
25pub struct TorsionImageWitness {
26    pub domain: Curve,
27    pub codomain: Curve,
28    /// The isogeny degree `deg φ`.
29    pub degree: u64,
30    /// The torsion order `N` (coprime to `deg φ`, so `φ` restricts to an isomorphism on `E[N]`).
31    pub torsion_order: u64,
32    /// A basis `(P, Q)` of `E[N]`.
33    pub basis: (Point, Point),
34    /// The published images `(φ(P), φ(Q))` on the codomain.
35    pub images: (Point, Point),
36}
37
38impl TorsionImageWitness {
39    /// Re-check the witness from scratch, trusting nothing about how it was produced:
40    /// 1. `(P, Q)` is a genuine basis of `E[N]` — the Weil pairing `e_N(P,Q)` is a *primitive* `N`th root
41    ///    of unity (the points are independent, so the pairing is non-degenerate);
42    /// 2. `(φP, φQ)` lie on the codomain and are killed by `N`;
43    /// 3. the **isogeny-compatibility law** `e_N(φP, φQ) = e_N(P, Q)^{deg φ}` holds.
44    pub fn verify(&self) -> bool {
45        let n = self.torsion_order;
46        let one = BigInt::from_i64(1);
47
48        // (1) The basis pairing on the domain must be a primitive Nth root (non-degenerate ⟹ independent).
49        let ep = match weil_pairing(&self.domain, &self.basis.0, &self.basis.1, n) {
50            Some(e)
51                if e != one && modpow(&e, &BigInt::from_i64(n as i64), &self.domain.p) == one =>
52            {
53                e
54            }
55            _ => return false,
56        };
57
58        // (2) The images sit on the codomain and have order dividing N.
59        let ord_n = BigInt::from_i64(n as i64);
60        for pt in [&self.images.0, &self.images.1] {
61            if !self.codomain.is_on_curve(pt) || self.codomain.mul(&ord_n, pt) != Point::Infinity {
62                return false;
63            }
64        }
65
66        // (3) The compatibility law: e_N(φP, φQ) = e_N(P,Q)^{deg φ}.
67        match weil_pairing(&self.codomain, &self.images.0, &self.images.1, n) {
68            Some(eq) => eq == modpow(&ep, &BigInt::from_i64(self.degree as i64), &self.domain.p),
69            None => false,
70        }
71    }
72}
73
74/// Build a *genuine* certified witness: the real `ell`-isogeny with kernel `⟨kernel_gen⟩` on `domain`,
75/// together with the images of an actual `E[n]` basis (`n` coprime to `ell`, so `φ` is an isomorphism on
76/// the `n`-torsion). Its `verify()` passes by construction. `None` if the isogeny or basis cannot be formed.
77pub fn certify_isogeny(
78    domain: &Curve,
79    kernel_gen: &Point,
80    ell: u64,
81    n: u64,
82) -> Option<TorsionImageWitness> {
83    let iso = Isogeny::from_kernel(domain, kernel_gen, ell)?;
84    let (p, q) = torsion_basis(domain, n)?;
85    let images = (iso.eval(&p), iso.eval(&q));
86    Some(TorsionImageWitness {
87        domain: domain.clone(),
88        codomain: iso.codomain.clone(),
89        degree: ell,
90        torsion_order: n,
91        basis: (p, q),
92        images,
93    })
94}
95
96/// The structural verdict on SIDH/SIKE-style public data.
97#[derive(Clone, Debug, PartialEq, Eq)]
98pub enum SidhAudit {
99    /// Consistent (the Weil-pairing law holds) — but it publishes the full action of `φ` on `E[N]`, the
100    /// auxiliary torsion information the Castryck–Decru attack requires. Valid data, structurally exposed:
101    /// post-2022 this whole class of scheme is broken, and the exposure is *why*.
102    ConsistentButTorsionExposed,
103    /// The torsion-image data fails the Weil-pairing law — not a valid isogeny witness at all.
104    Inconsistent,
105}
106
107/// Audit an isogeny public key: consistent, and what does it structurally expose?
108pub fn audit(w: &TorsionImageWitness) -> SidhAudit {
109    if w.verify() {
110        SidhAudit::ConsistentButTorsionExposed
111    } else {
112        SidhAudit::Inconsistent
113    }
114}
115
116// ---- Kani's theorem: the glue-and-split core -------------------------------------------------------
117//
118// Kani's theorem powers the Castryck–Decru break by GLUING two elliptic curves into an abelian surface:
119// given an isogeny `φ: E → E'` and a torsion basis, the GRAPH `K = {(T, φ(T)) : T ∈ E[N]} ⊂ (E × E')[N]`
120// is a candidate kernel of an `(N,N)`-isogeny. It is a valid kernel exactly when it is **Lagrangian**
121// (maximal isotropic) under the product Weil pairing — and that isotropy is decided by the pairing law we
122// certified: on the graph generators, `e_product((P,φP),(Q,φQ)) = e_N(P,Q)·e_N(φP,φQ) = e_N(P,Q)^{1+deg φ}`,
123// so the graph is isotropic ⟺ `deg φ ≡ −1 (mod N)`. The torsion images are exactly what make this pairing
124// computable — which is *why* publishing them is the leak. This certificate computes and re-checks that
125// gluing pairing; the remaining glue-and-split machinery (Richelot `(2,2)`-isogenies of the surface, theta
126// coordinates, and split detection) is genuine research-grade work built ON this isotropic core, NOT
127// claimed here.
128
129use crate::fp2::{
130    aut_1728, derive_isogeny_path2, fp2_const, fp2_pow, full_order_basis2, kernel_generator2,
131    keyspace_codomain_classes, point_of_order2, point_order2, product_weil_pairing, push_through2,
132    recover_secret2, recover_secret_recursive2, torsion_basis2, weil_pairing2, Curve2, Fp2,
133    Isogeny2, IsogenyStep2, Point2,
134};
135
136/// A **Kani glue kernel**: the graph `{(T, φ(T))}` of an isogeny on the `N`-torsion, the candidate kernel of
137/// an `(N,N)`-isogeny of the abelian surface `E × E'`.
138#[derive(Clone, Debug)]
139pub struct KaniGlue {
140    pub e1: Curve2,
141    pub e2: Curve2,
142    pub degree: u64,
143    pub torsion_order: u64,
144    pub basis: (Point2, Point2),
145    pub images: (Point2, Point2),
146}
147
148impl KaniGlue {
149    /// The product Weil pairing on the graph generators `(P,φP)` and `(Q,φQ)`.
150    pub fn glue_pairing(&self) -> Option<Fp2> {
151        product_weil_pairing(
152            &self.e1,
153            &self.e2,
154            (&self.basis.0, &self.images.0),
155            (&self.basis.1, &self.images.1),
156            self.torsion_order,
157        )
158    }
159
160    /// Re-check Kani's gluing relation: the graph pairing equals `e_N(P,Q)^{1+deg φ}`. This is what makes
161    /// the isotropy of the glue kernel *decidable*, and it re-derives the pairings from scratch.
162    pub fn verify(&self) -> bool {
163        let ep = match weil_pairing2(&self.e1, &self.basis.0, &self.basis.1, self.torsion_order) {
164            Some(e) => e,
165            None => return false,
166        };
167        match self.glue_pairing() {
168            Some(glue) => glue == fp2_pow(&ep, 1 + self.degree, &self.e1.p),
169            None => false,
170        }
171    }
172
173    /// Whether the glue kernel is **Lagrangian** (isotropic) — i.e. an `(N,N)`-isogeny of `E × E'` exists
174    /// with this kernel. True exactly when the graph pairing is trivial, i.e. `deg φ ≡ −1 (mod N)`.
175    pub fn is_lagrangian(&self) -> bool {
176        self.glue_pairing()
177            .map_or(false, |g| g == fp2_const(1, &self.e1.p))
178    }
179}
180
181/// Build a genuine Kani glue kernel over `𝔽_{p²}` from a real `ell`-isogeny and an `N`-torsion basis.
182pub fn build_kani_glue(domain: &Curve2, kernel_gen: &Point2, ell: u64, n: u64) -> Option<KaniGlue> {
183    let iso = Isogeny2::from_kernel(domain, kernel_gen, ell)?;
184    let (p, q) = torsion_basis2(domain, n)?;
185    let images = (iso.eval(&p), iso.eval(&q));
186    Some(KaniGlue {
187        e1: domain.clone(),
188        e2: iso.codomain.clone(),
189        degree: ell,
190        torsion_order: n,
191        basis: (p, q),
192        images,
193    })
194}
195
196/// Whether `n` is `bound`-smooth (every prime factor ≤ `bound`) — the auxiliary isogeny degree of a Kani
197/// diamond must be smooth to be efficiently computable.
198pub fn is_smooth(mut n: u64, bound: u64) -> bool {
199    if n == 0 {
200        return false;
201    }
202    let mut f = 2u64;
203    while f * f <= n {
204        while n % f == 0 {
205            n /= f;
206        }
207        f += 1;
208    }
209    n == 1 || n <= bound
210}
211
212/// **The Kani degree condition.** To embed a degree-`d` secret isogeny in a `(2,2)`-isogeny *chain* of an
213/// abelian surface (the Castryck–Decru diamond), pick an exponent `e` and an auxiliary isogeny of degree
214/// `c = 2^e − d`, so the two sides of the diamond sum to `2^e` — the surface isogeny is then a length-`e`
215/// Richelot chain. `c` must be positive and smooth (efficiently computable). Returns the smallest such
216/// `(e, c)`. This is the diamond's number-theoretic bookkeeping.
217pub fn kani_diamond_degrees(d: u64, max_e: u32, smooth_bound: u64) -> Option<(u32, u64)> {
218    (1..=max_e).find_map(|e| {
219        let n = 1u64 << e;
220        // c must be a NONTRIVIAL auxiliary (degree > 1 — a degree-1 "isogeny" is the identity, no gluing).
221        (n > d + 1)
222            .then(|| n - d)
223            .filter(|&c| is_smooth(c, smooth_bound))
224            .map(|c| (e, c))
225    })
226}
227
228/// A Castryck–Decru **Kani diamond**: a secret isogeny `φ: E₀ → E` of degree `d` and an auxiliary isogeny
229/// `γ: E₀ → C` of degree `c`, chosen so `c + d = 2^e`. Kani's lemma then supplies a `(2^e, 2^e)`-isogeny of
230/// the abelian surface `E × C` — a length-`e` Richelot chain — whose codomain **splits** into a product of
231/// elliptic curves iff the diamond is consistent. The split-test
232/// ([`crate::hyperelliptic::surface_is_reducible`]) is the per-digit oracle that reads that
233/// splitting off. **Honest boundary:** this builds and validates the diamond's *degree structure and both
234/// isogeny sides*; constructing the surface's `2^e`-torsion kernel from the diamond and the torsion images —
235/// the input the split-oracle consumes — is the remaining SageMath-scale research core and is **not**
236/// fabricated here.
237#[derive(Clone, Debug)]
238pub struct KaniDiamond {
239    pub e0: Curve2,
240    /// Codomain of the secret isogeny `φ` (degree `d`).
241    pub e_curve: Curve2,
242    /// Codomain of the auxiliary isogeny `γ` (degree `c`).
243    pub c_curve: Curve2,
244    pub d: u64,
245    pub c: u64,
246    /// `c + d = 2^e`.
247    pub e: u32,
248}
249
250/// Build a Kani diamond over `𝔽_{p²}`: the secret side `φ` is an `ell_phi^a`-isogeny with kernel `⟨phi_gen⟩`;
251/// the auxiliary side `γ` is a `c`-isogeny (`c` an odd prime) with kernel `⟨gamma_gen⟩`. Succeeds only when
252/// `c + ell_phi^a` is a power of two — the Kani degree condition.
253pub fn build_kani_diamond(
254    e0: &Curve2,
255    phi_gen: &Point2,
256    ell_phi: u64,
257    a: u32,
258    gamma_gen: &Point2,
259    c: u64,
260) -> Option<KaniDiamond> {
261    let d = ell_phi.pow(a);
262    let n = d + c;
263    if !n.is_power_of_two() {
264        return None;
265    }
266    let phi = derive_isogeny_path2(e0, phi_gen, ell_phi, a)?;
267    let gamma = Isogeny2::from_kernel(e0, gamma_gen, c)?;
268    Some(KaniDiamond {
269        e0: e0.clone(),
270        e_curve: phi.last()?.codomain.clone(),
271        c_curve: gamma.codomain,
272        d,
273        c,
274        e: n.trailing_zeros(),
275    })
276}
277
278/// A **law the recovery invoked** — auto-formalized as a re-checkable obligation, not prose. The recovery
279/// engine does not merely return an answer; it pops out the rules and laws it relied on, each of which
280/// [`SecretRecovery::verify`] re-derives from scratch.
281#[derive(Clone, Debug, PartialEq)]
282pub enum RecoveryLaw {
283    /// The secret kernel generator has order exactly `ℓᵃ`.
284    GeneratorOrder { ell: u64, a: u32 },
285    /// The unfolded chain is `a` connected `ℓ`-isogeny steps, each quotienting an order-`ℓ` subgroup.
286    DescendingKernels { ell: u64 },
287    /// Pushing the auxiliary torsion basis through the chain reproduces the published images (the defining
288    /// property of the recovered isogeny).
289    ImagesReproduced,
290    /// The `ℓ`-adic **tree** recursion (auto-partitioning the keyspace by digit, sharing prefixes) recovers
291    /// the same secret as the flat enumeration — the partition is faithful.
292    KeyspaceTreePartition { ell: u64, a: u32 },
293    /// `E₀/⟨K⟩ ≅ E₀/⟨ι(K)⟩` under the automorphism `ι`: recovering one kernel recovers its whole orbit.
294    AutOrbitClosure,
295}
296
297impl RecoveryLaw {
298    /// The formalized statement of the law — the "learning" the recovery pops out.
299    pub fn statement(&self) -> String {
300        match self {
301            RecoveryLaw::GeneratorOrder { ell, a } => format!("ord(gen) = {ell}^{a} on E₀"),
302            RecoveryLaw::DescendingKernels { ell } => {
303                format!("each of the a chain steps quotients an order-{ell} subgroup; the chain is connected")
304            }
305            RecoveryLaw::ImagesReproduced => "φ(P_B), φ(Q_B) = the published torsion images".into(),
306            RecoveryLaw::KeyspaceTreePartition { ell, a } => {
307                format!("the {ell}-adic keyspace tree (depth {a}) recovers the same secret as flat search")
308            }
309            RecoveryLaw::AutOrbitClosure => {
310                "E₀/⟨K⟩ ≅ E₀/⟨ι(K)⟩ — recovering one kernel recovers its orbit".into()
311            }
312        }
313    }
314}
315
316/// A recovered SIDH secret **together with the self-checking record of the laws its recovery invoked**. The
317/// certificate carries everything needed to re-derive itself: [`verify`](SecretRecovery::verify) re-runs
318/// every law from scratch, trusting nothing about how the answer was produced. This is the auto-formalizing
319/// recovery — it inverts images → generator *and* emits the re-checkable mathematics it stands on.
320#[derive(Clone, Debug)]
321pub struct SecretRecovery {
322    pub e0: Curve2,
323    pub basis_a: (Point2, Point2),
324    pub basis_b: (Point2, Point2),
325    pub images: (Point2, Point2),
326    pub ell: u64,
327    pub a: u32,
328    pub secret: BigInt,
329    pub generator: Point2,
330    pub path: Vec<IsogenyStep2>,
331    pub laws: Vec<RecoveryLaw>,
332}
333
334impl SecretRecovery {
335    /// The formalized laws this recovery relied on, as statements — the rules and learnings, popped out.
336    pub fn learnings(&self) -> Vec<String> {
337        self.laws.iter().map(RecoveryLaw::statement).collect()
338    }
339
340    /// Re-check every law from scratch. Trusts nothing about how the recovery ran.
341    pub fn verify(&self) -> bool {
342        let n = self.ell.pow(self.a);
343        let (pa, qa) = (&self.basis_a.0, &self.basis_a.1);
344        let (pb, qb) = (&self.basis_b.0, &self.basis_b.1);
345        // The recovered generator is P_A + [s]Q_A of order ℓᵃ.
346        if kernel_generator2(&self.e0, pa, qa, &self.secret) != self.generator {
347            return false;
348        }
349        for law in &self.laws {
350            let ok = match law {
351                RecoveryLaw::GeneratorOrder { ell, a } => {
352                    let m = ell.pow(*a);
353                    point_order2(&self.e0, &self.generator, m + 1) == Some(m)
354                }
355                RecoveryLaw::DescendingKernels { ell } => {
356                    self.path.len() as u32 == self.a
357                        && self.path.iter().enumerate().all(|(k, st)| {
358                            let order_ok =
359                                point_order2(&st.domain, &st.kernel, *ell + 1) == Some(*ell);
360                            let connected = k == 0 || st.domain == self.path[k - 1].codomain;
361                            order_ok && connected
362                        })
363                }
364                RecoveryLaw::ImagesReproduced => {
365                    push_through2(&self.path, self.ell, pb).as_ref() == Some(&self.images.0)
366                        && push_through2(&self.path, self.ell, qb).as_ref() == Some(&self.images.1)
367                }
368                RecoveryLaw::KeyspaceTreePartition { ell, a } => {
369                    // The ℓ-adic tree walk independently recovers a generator that reproduces the images —
370                    // the partition is faithful. (It need not be the identical scalar: symmetry-equivalent
371                    // kernels are genuine co-solutions, which is precisely the AutOrbitClosure law below.)
372                    recover_secret_recursive2(
373                        &self.e0,
374                        (pa, qa),
375                        *ell,
376                        *a,
377                        (pb, qb),
378                        (&self.images.0, &self.images.1),
379                    )
380                    .and_then(|(_, _s, g)| {
381                        let path = derive_isogeny_path2(&self.e0, &g, *ell, *a)?;
382                        Some(
383                            push_through2(&path, *ell, pb).as_ref() == Some(&self.images.0)
384                                && push_through2(&path, *ell, qb).as_ref() == Some(&self.images.1),
385                        )
386                    })
387                    .unwrap_or(false)
388                }
389                RecoveryLaw::AutOrbitClosure => {
390                    let j = |g: &Point2| {
391                        derive_isogeny_path2(&self.e0, g, self.ell, self.a)
392                            .and_then(|p| p.last().and_then(|st| st.codomain.j_invariant()))
393                    };
394                    let ig = aut_1728(&self.e0.p, &self.generator);
395                    point_order2(&self.e0, &ig, n + 1) == Some(n)
396                        && j(&self.generator) == j(&ig)
397                        && j(&ig).is_some()
398                }
399            };
400            if !ok {
401                return false;
402            }
403        }
404        true
405    }
406}
407
408/// **Certify an images → generator recovery**, emitting the answer with its self-checking law record. Runs
409/// the flat recovery for the answer, then attaches the full set of re-checkable laws (order, descent, image
410/// reproduction, the faithful ℓ-adic tree partition, and the Aut-orbit closure rule).
411pub fn certify_recovery(
412    e0: &Curve2,
413    basis_a: (&Point2, &Point2),
414    ell: u64,
415    a: u32,
416    basis_b: (&Point2, &Point2),
417    images: (&Point2, &Point2),
418) -> Option<SecretRecovery> {
419    let (secret, generator, path) = recover_secret2(e0, basis_a, ell, a, basis_b, images)?;
420    let laws = vec![
421        RecoveryLaw::GeneratorOrder { ell, a },
422        RecoveryLaw::DescendingKernels { ell },
423        RecoveryLaw::ImagesReproduced,
424        RecoveryLaw::KeyspaceTreePartition { ell, a },
425        RecoveryLaw::AutOrbitClosure,
426    ];
427    Some(SecretRecovery {
428        e0: e0.clone(),
429        basis_a: (basis_a.0.clone(), basis_a.1.clone()),
430        basis_b: (basis_b.0.clone(), basis_b.1.clone()),
431        images: (images.0.clone(), images.1.clone()),
432        ell,
433        a,
434        secret,
435        generator,
436        path,
437        laws,
438    })
439}
440
441#[cfg(test)]
442#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/isogeny/tests.rs"]
443mod tests;