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;