logicaffeine_proof/
rainbow.rs

1//! Rainbow — Jintai Ding & Dieter Schmidt's multilayer Oil-and-Vinegar signature (ACNS 2005),
2//! the multivariate scheme our XL engine is built to attack. This is a faithful reference over
3//! GF(2^8): a two-layer central map `F`, invertible affine transforms `S` and `T`, public key
4//! `P = S ∘ F ∘ T`, and the Oil-and-Vinegar trapdoor that inverts `F` at signing time.
5//!
6//! The public map is produced as `xl::Poly<Gf256>` per output, so [`forge_system`] hands it
7//! straight to [`crate::xl::xl_solve`] — the algebraic cryptanalysis Ding formalized through the
8//! degree of regularity — closing the build-and-break loop on one substrate. All finite-field
9//! linear algebra reuses the exhaustively-verified [`logicaffeine_base::gf256`].
10//!
11//! Field note: this reference works over the `logicaffeine_base::gf256` field (reduction
12//! polynomial `0x11d`). The NIST submission fixes its own GF(256) tower representation; matching
13//! that byte-for-byte is the separate bit-exact-vs-KAT effort.
14
15use crate::macaulay::{self, Monomial};
16use crate::xl::{eval, Field, Gf256, MQSystem, Poly};
17use logicaffeine_base::gf256;
18use std::collections::BTreeMap;
19
20/// Rainbow layer sizes: `v1` vinegars, then `o1` first-layer oils, then `o2` second-layer oils.
21#[derive(Clone, Copy, Debug)]
22pub struct RainbowParams {
23    pub v1: usize,
24    pub o1: usize,
25    pub o2: usize,
26}
27
28impl RainbowParams {
29    pub fn n(&self) -> usize {
30        self.v1 + self.o1 + self.o2
31    }
32    pub fn m(&self) -> usize {
33        self.o1 + self.o2
34    }
35    /// The index one past the first-layer variables (start of the second-layer oils).
36    fn l1(&self) -> usize {
37        self.v1 + self.o1
38    }
39}
40
41pub struct SecretKey {
42    pub params: RainbowParams,
43    s_inv: Vec<Vec<u8>>,
44    s_vec: Vec<u8>,
45    t_inv: Vec<Vec<u8>>,
46    t_vec: Vec<u8>,
47    central: Vec<Poly<Gf256>>,
48}
49
50pub struct PublicKey {
51    pub params: RainbowParams,
52    /// One quadratic polynomial per output coordinate: `P_k(x)`.
53    pub polys: Vec<Poly<Gf256>>,
54}
55
56// ── Polynomial plumbing over GF(256) ──────────────────────────────────────────────────
57
58fn padd(dst: &mut Poly<Gf256>, m: &Monomial, c: Gf256) {
59    if c.is_zero() {
60        return;
61    }
62    let v = dst.get(m).copied().unwrap_or_else(Gf256::zero).add(c);
63    if v.is_zero() {
64        dst.remove(m);
65    } else {
66        dst.insert(m.clone(), v);
67    }
68}
69
70fn poly_add_into(dst: &mut Poly<Gf256>, src: &Poly<Gf256>) {
71    for (m, &c) in src {
72        padd(dst, m, c);
73    }
74}
75
76fn poly_mul(a: &Poly<Gf256>, b: &Poly<Gf256>) -> Poly<Gf256> {
77    let mut r = BTreeMap::new();
78    for (ma, &ca) in a {
79        for (mb, &cb) in b {
80            padd(&mut r, &macaulay::mul(ma, mb, false), ca.mul(cb));
81        }
82    }
83    r
84}
85
86/// Substitute an affine form for every variable: `x_i ↦ subs[i]` (each a polynomial). Used to
87/// compose the central map with the affine `T`.
88fn substitute_affine(f: &Poly<Gf256>, subs: &[Poly<Gf256>]) -> Poly<Gf256> {
89    let mut out = BTreeMap::new();
90    for (mono, &c) in f {
91        let mut term: Poly<Gf256> = BTreeMap::new();
92        term.insert(Vec::new(), c); // the constant polynomial c
93        for &v in mono {
94            term = poly_mul(&term, &subs[v as usize]);
95        }
96        poly_add_into(&mut out, &term);
97    }
98    out
99}
100
101/// Substitute concrete field values for a subset of variables (`fixed[i] = Some(val)`), leaving
102/// the rest symbolic. Used to freeze the vinegars before solving the oils.
103fn substitute_values(f: &Poly<Gf256>, fixed: &[Option<Gf256>]) -> Poly<Gf256> {
104    let mut out = BTreeMap::new();
105    for (mono, &c) in f {
106        let mut coeff = c;
107        let mut rem: Monomial = Vec::new();
108        for &v in mono {
109            match fixed[v as usize] {
110                Some(val) => coeff = coeff.mul(val),
111                None => rem.push(v),
112            }
113        }
114        rem.sort_unstable();
115        padd(&mut out, &rem, coeff);
116    }
117    out
118}
119
120// ── Deterministic randomness ──────────────────────────────────────────────────────────
121
122struct Rng(u64);
123impl Rng {
124    fn next(&mut self) -> u64 {
125        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
126        let mut z = self.0;
127        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
128        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
129        z ^ (z >> 31)
130    }
131    fn byte(&mut self) -> u8 {
132        self.next() as u8
133    }
134    fn gf(&mut self) -> Gf256 {
135        Gf256(self.byte())
136    }
137}
138
139fn random_invertible(rng: &mut Rng, size: usize) -> (Vec<Vec<u8>>, Vec<Vec<u8>>) {
140    loop {
141        let mat: Vec<Vec<u8>> = (0..size)
142            .map(|_| (0..size).map(|_| rng.byte()).collect())
143            .collect();
144        if let Some(inv) = gf256::invert(&mat) {
145            return (mat, inv);
146        }
147    }
148}
149
150/// Generate the two-layer Oil-and-Vinegar central map. Each polynomial omits oil×oil products in
151/// its layer, so fixing the vinegars leaves it LINEAR in that layer's oils — the trapdoor.
152fn gen_central(p: &RainbowParams, rng: &mut Rng) -> Vec<Poly<Gf256>> {
153    let (n, v1, l1) = (p.n(), p.v1, p.l1());
154    let mut central = Vec::with_capacity(p.m());
155    // Layer 1: variables [0, l1); quadratic terms need the smaller index to be a vinegar (< v1).
156    for _ in 0..p.o1 {
157        let mut f = BTreeMap::new();
158        for i in 0..l1 {
159            if i < v1 {
160                for j in i..l1 {
161                    padd(&mut f, &vec![i as u32, j as u32], rng.gf());
162                }
163            }
164        }
165        for i in 0..l1 {
166            padd(&mut f, &vec![i as u32], rng.gf());
167        }
168        padd(&mut f, &Vec::new(), rng.gf());
169        central.push(f);
170    }
171    // Layer 2: variables [0, n); quadratic terms need the smaller index to be in V2 (< l1).
172    for _ in 0..p.o2 {
173        let mut f = BTreeMap::new();
174        for i in 0..n {
175            if i < l1 {
176                for j in i..n {
177                    padd(&mut f, &vec![i as u32, j as u32], rng.gf());
178                }
179            }
180        }
181        for i in 0..n {
182            padd(&mut f, &vec![i as u32], rng.gf());
183        }
184        padd(&mut f, &Vec::new(), rng.gf());
185        central.push(f);
186    }
187    central
188}
189
190// ── Key generation, signing, verification ─────────────────────────────────────────────
191
192pub fn keygen(params: RainbowParams, seed: u64) -> (SecretKey, PublicKey) {
193    let (n, m) = (params.n(), params.m());
194    let mut rng = Rng(seed);
195
196    let (t_mat, t_inv) = random_invertible(&mut rng, n);
197    let t_vec: Vec<u8> = (0..n).map(|_| rng.byte()).collect();
198    let (s_mat, s_inv) = random_invertible(&mut rng, m);
199    let s_vec: Vec<u8> = (0..m).map(|_| rng.byte()).collect();
200    let central = gen_central(&params, &mut rng);
201
202    // Compose the public map P = S ∘ F ∘ T. First the affine forms w_i = Σ_a T[i][a] x_a + t_i.
203    let t_forms: Vec<Poly<Gf256>> = (0..n)
204        .map(|i| {
205            let mut p: Poly<Gf256> = BTreeMap::new();
206            padd(&mut p, &Vec::new(), Gf256(t_vec[i]));
207            for a in 0..n {
208                padd(&mut p, &vec![a as u32], Gf256(t_mat[i][a]));
209            }
210            p
211        })
212        .collect();
213    let f_comp: Vec<Poly<Gf256>> = central
214        .iter()
215        .map(|f| substitute_affine(f, &t_forms))
216        .collect();
217
218    let mut polys = Vec::with_capacity(m);
219    for k in 0..m {
220        let mut pk: Poly<Gf256> = BTreeMap::new();
221        for l in 0..m {
222            let c = Gf256(s_mat[k][l]);
223            if !c.is_zero() {
224                for (mono, &fc) in &f_comp[l] {
225                    padd(&mut pk, mono, c.mul(fc));
226                }
227            }
228        }
229        padd(&mut pk, &Vec::new(), Gf256(s_vec[k]));
230        polys.push(pk);
231    }
232
233    (
234        SecretKey {
235            params,
236            s_inv,
237            s_vec,
238            t_inv,
239            t_vec,
240            central,
241        },
242        PublicKey { params, polys },
243    )
244}
245
246fn hash_seed(msg_hash: &[u8]) -> u64 {
247    let mut seed = 0x9E37_79B9_7F4A_7C15u64;
248    for &b in msg_hash {
249        seed = seed.rotate_left(7) ^ (b as u64).wrapping_mul(0x1_0000_0001_B3);
250    }
251    seed
252}
253
254/// Sign a message hash (`m` field elements). Returns the signature `x ∈ GF(256)^n`, or `None` if
255/// the Oil-and-Vinegar inversion kept hitting singular systems (astronomically unlikely).
256pub fn sign(sk: &SecretKey, msg_hash: &[u8]) -> Option<Vec<u8>> {
257    let u = central_target(sk, msg_hash);
258    for attempt in 0..256u64 {
259        let mut rng = Rng(hash_seed(msg_hash) ^ attempt.wrapping_mul(0xA5A5_A5A5));
260        let vinegars: Vec<u8> = (0..sk.params.v1).map(|_| rng.byte()).collect();
261        if let Some(x) = sign_core(sk, &u, &vinegars) {
262            return Some(x);
263        }
264    }
265    None
266}
267
268/// Sign with the `v1` vinegar values supplied explicitly (deterministic; `None` if they make a
269/// layer's linear system singular). This is the exact core the LOGOS `rainbowSign` mirrors.
270pub fn sign_with_vinegars(sk: &SecretKey, msg_hash: &[u8], vinegars: &[u8]) -> Option<Vec<u8>> {
271    sign_core(sk, &central_target(sk, msg_hash), vinegars)
272}
273
274/// `u = S⁻¹ · (d − S_vec)` — the value the central map must hit.
275fn central_target(sk: &SecretKey, msg_hash: &[u8]) -> Vec<u8> {
276    let d_minus_s: Vec<u8> = (0..sk.params.m())
277        .map(|k| msg_hash[k] ^ sk.s_vec[k])
278        .collect();
279    gf256::matvec(&sk.s_inv, &d_minus_s)
280}
281
282/// The deterministic Oil-and-Vinegar inversion: fix the vinegars, solve each layer's oils.
283fn sign_core(sk: &SecretKey, u: &[u8], vinegars: &[u8]) -> Option<Vec<u8>> {
284    let p = sk.params;
285    let (n, v1, o1, o2, l1) = (p.n(), p.v1, p.o1, p.o2, p.l1());
286    let mut fixed: Vec<Option<Gf256>> = vec![None; n];
287    for i in 0..v1 {
288        fixed[i] = Some(Gf256(vinegars[i]));
289    }
290
291    // Layer 1: solve for the first-layer oils [v1, l1).
292    let mut a1 = vec![vec![0u8; o1]; o1];
293    let mut b1 = vec![0u8; o1];
294    for k in 0..o1 {
295        let red = substitute_values(&sk.central[k], &fixed);
296        b1[k] = u[k] ^ red.get(&Vec::new()).copied().unwrap_or_else(Gf256::zero).0;
297        for c in 0..o1 {
298            a1[k][c] = red
299                .get(&vec![(v1 + c) as u32])
300                .copied()
301                .unwrap_or_else(Gf256::zero)
302                .0;
303        }
304    }
305    let sol1 = gf256::solve(&a1, &b1)?;
306    for c in 0..o1 {
307        fixed[v1 + c] = Some(Gf256(sol1[c]));
308    }
309
310    // Layer 2: solve for the second-layer oils [l1, n).
311    let mut a2 = vec![vec![0u8; o2]; o2];
312    let mut b2 = vec![0u8; o2];
313    for k in 0..o2 {
314        let red = substitute_values(&sk.central[o1 + k], &fixed);
315        b2[k] = u[o1 + k] ^ red.get(&Vec::new()).copied().unwrap_or_else(Gf256::zero).0;
316        for c in 0..o2 {
317            a2[k][c] = red
318                .get(&vec![(l1 + c) as u32])
319                .copied()
320                .unwrap_or_else(Gf256::zero)
321                .0;
322        }
323    }
324    let sol2 = gf256::solve(&a2, &b2)?;
325    for c in 0..o2 {
326        fixed[l1 + c] = Some(Gf256(sol2[c]));
327    }
328
329    // x = T⁻¹ · (w − T_vec).
330    let w: Vec<u8> = (0..n).map(|i| fixed[i].unwrap().0).collect();
331    let w_minus_t: Vec<u8> = (0..n).map(|i| w[i] ^ sk.t_vec[i]).collect();
332    Some(gf256::matvec(&sk.t_inv, &w_minus_t))
333}
334
335/// Verify a signature: evaluate every public polynomial at `x` and compare to the message hash.
336pub fn verify(pk: &PublicKey, msg_hash: &[u8], sig: &[u8]) -> bool {
337    if sig.len() != pk.params.n() {
338        return false;
339    }
340    let x: Vec<Gf256> = sig.iter().map(|&b| Gf256(b)).collect();
341    (0..pk.params.m()).all(|k| eval(&pk.polys[k], &x).0 == msg_hash[k])
342}
343
344/// The MQ system a forger must solve — `P_k(x) − d_k = 0` for every output — handed straight to
345/// [`crate::xl::xl_solve`]. A solution is a signature forgery produced with NO secret key.
346pub fn forge_system(pk: &PublicKey, msg_hash: &[u8]) -> MQSystem<Gf256> {
347    let polys = pk
348        .polys
349        .iter()
350        .enumerate()
351        .map(|(k, p)| {
352            let mut q = p.clone();
353            padd(&mut q, &Vec::new(), Gf256(msg_hash[k])); // − d_k  (= xor in char 2)
354            q
355        })
356        .collect();
357    MQSystem {
358        n: pk.params.n(),
359        polys,
360    }
361}
362
363/// Flatten the public key into three byte arrays for a coefficient-driven verifier: `pubq` holds
364/// the upper-triangular quadratic coefficients per output (order `i ≤ j`), `publin` the linear
365/// coefficients, `pubc` the constants. This is the exact layout the LOGOS `rainbowVerify` consumes.
366pub fn flatten_public(pk: &PublicKey) -> (Vec<u8>, Vec<u8>, Vec<u8>) {
367    let (n, m) = (pk.params.n(), pk.params.m());
368    let mut pubq = Vec::new();
369    let mut publin = Vec::new();
370    let mut pubc = Vec::new();
371    for k in 0..m {
372        for i in 0..n {
373            for j in i..n {
374                pubq.push(
375                    pk.polys[k]
376                        .get(&vec![i as u32, j as u32])
377                        .copied()
378                        .unwrap_or_else(Gf256::zero)
379                        .0,
380                );
381            }
382        }
383        for i in 0..n {
384            publin.push(
385                pk.polys[k]
386                    .get(&vec![i as u32])
387                    .copied()
388                    .unwrap_or_else(Gf256::zero)
389                    .0,
390            );
391        }
392        pubc.push(
393            pk.polys[k]
394                .get(&Vec::new())
395                .copied()
396                .unwrap_or_else(Gf256::zero)
397                .0,
398        );
399    }
400    (pubq, publin, pubc)
401}
402
403/// The secret key flattened for the LOGOS `rainbowSign`: the central map in the same per-output
404/// layout as [`flatten_public`], plus the affine inverses `S⁻¹` / `T⁻¹` (row-major) and their shifts.
405#[derive(Clone, Debug)]
406pub struct SecretFlat {
407    pub central_q: Vec<u8>,
408    pub central_lin: Vec<u8>,
409    pub central_c: Vec<u8>,
410    pub s_inv: Vec<u8>,
411    pub s_vec: Vec<u8>,
412    pub t_inv: Vec<u8>,
413    pub t_vec: Vec<u8>,
414}
415
416pub fn flatten_secret(sk: &SecretKey) -> SecretFlat {
417    let (n, m) = (sk.params.n(), sk.params.m());
418    let mut central_q = Vec::new();
419    let mut central_lin = Vec::new();
420    let mut central_c = Vec::new();
421    for k in 0..m {
422        for i in 0..n {
423            for j in i..n {
424                central_q.push(
425                    sk.central[k]
426                        .get(&vec![i as u32, j as u32])
427                        .copied()
428                        .unwrap_or_else(Gf256::zero)
429                        .0,
430                );
431            }
432        }
433        for i in 0..n {
434            central_lin.push(
435                sk.central[k]
436                    .get(&vec![i as u32])
437                    .copied()
438                    .unwrap_or_else(Gf256::zero)
439                    .0,
440            );
441        }
442        central_c.push(
443            sk.central[k]
444                .get(&Vec::new())
445                .copied()
446                .unwrap_or_else(Gf256::zero)
447                .0,
448        );
449    }
450    SecretFlat {
451        central_q,
452        central_lin,
453        central_c,
454        s_inv: sk.s_inv.iter().flatten().copied().collect(),
455        s_vec: sk.s_vec.clone(),
456        t_inv: sk.t_inv.iter().flatten().copied().collect(),
457        t_vec: sk.t_vec.clone(),
458    }
459}
460
461/// Inputs for the LOGOS `rainbowKeygen` (the public-map composition `P = S∘F∘T`): the FORWARD
462/// affine maps `T`/`S` (recovered by inverting the stored inverses) and the central map, all
463/// row-major / packed like [`flatten_public`].
464#[derive(Clone, Debug)]
465pub struct KeygenInputs {
466    pub t_mat: Vec<u8>,
467    pub t_vec: Vec<u8>,
468    pub s_mat: Vec<u8>,
469    pub s_vec: Vec<u8>,
470    pub central_q: Vec<u8>,
471    pub central_lin: Vec<u8>,
472    pub central_c: Vec<u8>,
473}
474
475fn reshape(flat: &[u8], k: usize) -> Vec<Vec<u8>> {
476    (0..k).map(|r| flat[r * k..(r + 1) * k].to_vec()).collect()
477}
478
479pub fn flatten_keygen(sk: &SecretKey) -> KeygenInputs {
480    let sf = flatten_secret(sk);
481    let (n, m) = (sk.params.n(), sk.params.m());
482    let t_mat = gf256::invert(&reshape(&sf.t_inv, n)).expect("T⁻¹ is invertible");
483    let s_mat = gf256::invert(&reshape(&sf.s_inv, m)).expect("S⁻¹ is invertible");
484    KeygenInputs {
485        t_mat: t_mat.into_iter().flatten().collect(),
486        t_vec: sf.t_vec,
487        s_mat: s_mat.into_iter().flatten().collect(),
488        s_vec: sf.s_vec,
489        central_q: sf.central_q,
490        central_lin: sf.central_lin,
491        central_c: sf.central_c,
492    }
493}
494
495#[cfg(test)]
496#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/rainbow/tests.rs"]
497mod tests;
logicaffeine_proof/rainbow.rs

logicaffeine_proof/
rainbow.rs
