qssm_le/protocol/
commit.rs

1//! Module-LWE commitment \(C = A r + \mu\) with Lyubashevsky-style Fiat–Shamir + rejection (no witness in proof).
2#![forbid(unsafe_code)]
3
4use crate::DeterministicRng;
5use core::hint::black_box;
6use qssm_utils::hashing::DOMAIN_MS;
7use qssm_utils::LE_FS_PUBLIC_BINDING_LAYOUT_VERSION;
8use subtle::{Choice, ConstantTimeEq, ConstantTimeLess};
9use zeroize::{Zeroize, ZeroizeOnDrop};
10
11use crate::algebra::ring::{
12    encode_rq_coeffs_le, short_vec_to_rq, short_vec_to_rq_bound, RqPoly, ScrubbedPoly,
13};
14use crate::crs::VerifyingKey;
15use crate::protocol::params::{
16    BETA, C_POLY_SIZE, C_POLY_SPAN, ETA, GAMMA, MAX_PROVER_ATTEMPTS, N, PUBLIC_DIGEST_COEFFS,
17    PUBLIC_DIGEST_COEFF_MAX, Q,
18};
19use crate::LeError;
20
21const DOMAIN_LE_FS: &str = "QSSM-LE-FS-LYU-v1.0";
22const DOMAIN_LE_CHALLENGE_POLY: &str = "QSSM-LE-CHALLENGE-POLY-v1.0";
23const CROSS_PROTOCOL_BINDING_LABEL: &[u8] = b"cross_protocol_digest_v1";
24const DST_LE_COMMIT: [u8; 32] = *b"QSSM-LE-V1-COMMIT...............";
25const DST_MS_VERIFY: [u8; 32] = *b"QSSM-MS-V1-VERIFY...............";
26
27/// Public inputs visible to all verifiers (no secret witness).
28#[derive(Debug, Clone, PartialEq, Eq)]
29#[non_exhaustive]
30pub enum PublicBinding {
31    /// Bind digest-derived coefficient vector (4-bit lanes, each ≤ 15).
32    DigestCoeffVector { coeffs: [u32; PUBLIC_DIGEST_COEFFS] },
33}
34
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub struct PublicInstance {
37    binding: PublicBinding,
38}
39
40impl PublicInstance {
41    #[must_use]
42    pub fn binding(&self) -> &PublicBinding {
43        &self.binding
44    }
45
46    /// Construct from digest coefficients. Validates all ≤ `PUBLIC_DIGEST_COEFF_MAX`.
47    pub fn digest_coeffs(coeffs: [u32; PUBLIC_DIGEST_COEFFS]) -> Result<Self, LeError> {
48        for &c in &coeffs {
49            if c > PUBLIC_DIGEST_COEFF_MAX {
50                return Err(LeError::OversizedInput);
51            }
52        }
53        Ok(Self {
54            binding: PublicBinding::DigestCoeffVector { coeffs },
55        })
56    }
57
58    /// Encode a `u64` scalar as 4-bit nibble coefficients (16 nibbles, rest zero).
59    /// Standard migration path from the removed legacy single-limb message mode.
60    #[must_use]
61    pub fn from_u64_nibbles(value: u64) -> Self {
62        let mut coeffs = [0u32; PUBLIC_DIGEST_COEFFS];
63        for i in 0..16 {
64            coeffs[i] = ((value >> (i * 4)) & 0x0f) as u32;
65        }
66        Self {
67            binding: PublicBinding::DigestCoeffVector { coeffs },
68        }
69    }
70
71    pub fn validate(&self) -> Result<(), LeError> {
72        let PublicBinding::DigestCoeffVector { coeffs } = &self.binding;
73        for &c in coeffs {
74            if c > PUBLIC_DIGEST_COEFF_MAX {
75                return Err(LeError::OversizedInput);
76            }
77        }
78        Ok(())
79    }
80}
81
82/// Secret witness (prover-only).
83#[derive(Zeroize, ZeroizeOnDrop)]
84#[cfg_attr(test, derive(PartialEq, Eq))]
85pub struct Witness {
86    r: [i32; N],
87}
88
89impl core::fmt::Debug for Witness {
90    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
91        f.debug_struct("Witness").field("r", &"[REDACTED]").finish()
92    }
93}
94
95impl Witness {
96    /// Construct a new witness from short coefficients.
97    #[must_use]
98    pub fn new(r: [i32; N]) -> Self {
99        Self { r }
100    }
101
102    /// Read-only access to witness coefficients.
103    #[must_use]
104    pub fn coeffs(&self) -> &[i32; N] {
105        &self.r
106    }
107
108    pub fn validate(&self) -> Result<(), LeError> {
109        for &v in &self.r {
110            if v.unsigned_abs() > BETA {
111                return Err(LeError::RejectedSample);
112            }
113        }
114        Ok(())
115    }
116}
117
118/// Secret witness key material (alias wrapper for forward-compatible APIs).
119#[derive(Zeroize, ZeroizeOnDrop)]
120#[cfg_attr(test, derive(PartialEq, Eq))]
121#[allow(dead_code)]
122pub(crate) struct SecretKey {
123    pub(crate) r: [i32; N],
124}
125
126impl core::fmt::Debug for SecretKey {
127    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
128        f.debug_struct("SecretKey")
129            .field("r", &"[REDACTED]")
130            .finish()
131    }
132}
133
134/// Prover masking randomness sampled per-attempt.
135#[derive(Zeroize, ZeroizeOnDrop)]
136#[cfg_attr(test, derive(PartialEq, Eq))]
137pub struct CommitmentRandomness {
138    y: [i32; N],
139}
140
141impl CommitmentRandomness {
142    /// Construct a new commitment randomness from nonce coefficients.
143    #[must_use]
144    pub fn new(y: [i32; N]) -> Self {
145        Self { y }
146    }
147
148    /// Read-only access to nonce coefficients.
149    #[must_use]
150    pub fn coeffs(&self) -> &[i32; N] {
151        &self.y
152    }
153}
154
155impl core::fmt::Debug for CommitmentRandomness {
156    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
157        f.debug_struct("CommitmentRandomness")
158            .field("y", &"[REDACTED]")
159            .finish()
160    }
161}
162
163/// Commitment as a full ring element (canonical coeffs mod \(q\)).
164#[derive(Debug, Clone, PartialEq, Eq)]
165pub struct Commitment(pub RqPoly);
166
167/// Witness-hiding proof: masking commitment \(t = Ay\) and response \(z = y + c r\) with FS challenge \(c\).
168#[derive(Debug, Clone, PartialEq, Eq)]
169pub struct LatticeProof {
170    pub t: RqPoly,
171    pub z: RqPoly,
172    /// Fiat–Shamir seed bytes (recomputed by verifier).
173    pub challenge_seed: [u8; 32],
174}
175
176/// Serializes [`PublicBinding`] for Fiat–Shamir. **Sync:** any change to this byte layout or to
177/// [`fs_challenge_bytes`] hash-input order must bump [`qssm_utils::LE_FS_PUBLIC_BINDING_LAYOUT_VERSION`]
178/// and the gadget `TranscriptMap` / `TRANSCRIPT_MAP_LAYOUT_VERSION` in `qssm-gadget`.
179fn public_binding_fs_bytes(public: &PublicInstance) -> Vec<u8> {
180    let _ = LE_FS_PUBLIC_BINDING_LAYOUT_VERSION;
181    let PublicBinding::DigestCoeffVector { coeffs } = &public.binding;
182    let mut out = Vec::with_capacity(1 + coeffs.len() * 4);
183    out.push(1);
184    for &c in coeffs {
185        out.extend_from_slice(&c.to_le_bytes());
186    }
187    out
188}
189
190fn fs_challenge_bytes(
191    binding_context: &[u8; 32],
192    vk: &VerifyingKey,
193    public: &PublicInstance,
194    commitment: &Commitment,
195    t: &RqPoly,
196) -> [u8; 32] {
197    let mut h = blake3::Hasher::new();
198    h.update(DOMAIN_LE_FS.as_bytes());
199    h.update(&DST_LE_COMMIT);
200    h.update(&DST_MS_VERIFY);
201    // Explicit cross-protocol binding context to prevent Engine-A/Engine-B replay confusion.
202    h.update(CROSS_PROTOCOL_BINDING_LABEL);
203    h.update(DOMAIN_MS.as_bytes());
204    h.update(b"fs_v2");
205    h.update(binding_context);
206    h.update(vk.crs_seed.as_slice());
207    h.update(&public_binding_fs_bytes(public));
208    h.update(&encode_rq_coeffs_le(&commitment.0));
209    h.update(&encode_rq_coeffs_le(t));
210    *h.finalize().as_bytes()
211}
212
213#[inline(never)]
214fn gamma_bound_scan(poly: &RqPoly) -> Choice {
215    #[inline(always)]
216    fn check_coeff(coeff: u32) -> Choice {
217        let q_half = Q / 2;
218        let x = coeff;
219        let gt_half_mask = ((q_half.wrapping_sub(x)) >> 31).wrapping_neg();
220        let centered = i64::from(x) - (i64::from(Q) & i64::from(gt_half_mask));
221        let sign_mask = centered >> 63;
222        let abs_centered = ((centered ^ sign_mask) - sign_mask) as u64;
223        (abs_centered as u32).ct_lt(&(GAMMA + 1))
224    }
225    let mut ok = Choice::from(1u8);
226    macro_rules! check4 {
227        ($a:expr, $b:expr, $c:expr, $d:expr) => {{
228            ok &= check_coeff(poly.0[$a]);
229            ok &= check_coeff(poly.0[$b]);
230            ok &= check_coeff(poly.0[$c]);
231            ok &= check_coeff(poly.0[$d]);
232        }};
233    }
234    check4!(0, 1, 2, 3);
235    check4!(4, 5, 6, 7);
236    check4!(8, 9, 10, 11);
237    check4!(12, 13, 14, 15);
238    check4!(16, 17, 18, 19);
239    check4!(20, 21, 22, 23);
240    check4!(24, 25, 26, 27);
241    check4!(28, 29, 30, 31);
242    check4!(32, 33, 34, 35);
243    check4!(36, 37, 38, 39);
244    check4!(40, 41, 42, 43);
245    check4!(44, 45, 46, 47);
246    check4!(48, 49, 50, 51);
247    check4!(52, 53, 54, 55);
248    check4!(56, 57, 58, 59);
249    check4!(60, 61, 62, 63);
250    check4!(64, 65, 66, 67);
251    check4!(68, 69, 70, 71);
252    check4!(72, 73, 74, 75);
253    check4!(76, 77, 78, 79);
254    check4!(80, 81, 82, 83);
255    check4!(84, 85, 86, 87);
256    check4!(88, 89, 90, 91);
257    check4!(92, 93, 94, 95);
258    check4!(96, 97, 98, 99);
259    check4!(100, 101, 102, 103);
260    check4!(104, 105, 106, 107);
261    check4!(108, 109, 110, 111);
262    check4!(112, 113, 114, 115);
263    check4!(116, 117, 118, 119);
264    check4!(120, 121, 122, 123);
265    check4!(124, 125, 126, 127);
266    check4!(128, 129, 130, 131);
267    check4!(132, 133, 134, 135);
268    check4!(136, 137, 138, 139);
269    check4!(140, 141, 142, 143);
270    check4!(144, 145, 146, 147);
271    check4!(148, 149, 150, 151);
272    check4!(152, 153, 154, 155);
273    check4!(156, 157, 158, 159);
274    check4!(160, 161, 162, 163);
275    check4!(164, 165, 166, 167);
276    check4!(168, 169, 170, 171);
277    check4!(172, 173, 174, 175);
278    check4!(176, 177, 178, 179);
279    check4!(180, 181, 182, 183);
280    check4!(184, 185, 186, 187);
281    check4!(188, 189, 190, 191);
282    check4!(192, 193, 194, 195);
283    check4!(196, 197, 198, 199);
284    check4!(200, 201, 202, 203);
285    check4!(204, 205, 206, 207);
286    check4!(208, 209, 210, 211);
287    check4!(212, 213, 214, 215);
288    check4!(216, 217, 218, 219);
289    check4!(220, 221, 222, 223);
290    check4!(224, 225, 226, 227);
291    check4!(228, 229, 230, 231);
292    check4!(232, 233, 234, 235);
293    check4!(236, 237, 238, 239);
294    check4!(240, 241, 242, 243);
295    check4!(244, 245, 246, 247);
296    check4!(248, 249, 250, 251);
297    check4!(252, 253, 254, 255);
298    ok
299}
300
301#[inline(never)]
302fn ct_reject_if_above_gamma(poly: &RqPoly) -> Choice {
303    #[inline(never)]
304    fn invoke(f: &dyn Fn(&RqPoly) -> Choice, p: &RqPoly) -> Choice {
305        f(p)
306    }
307    let dispatch: &dyn Fn(&RqPoly) -> Choice = &gamma_bound_scan;
308    black_box(invoke(dispatch, poly))
309}
310
311fn challenge_poly(seed: &[u8; 32]) -> [i32; C_POLY_SIZE] {
312    let mut coeffs = [0i32; C_POLY_SIZE];
313    let span = C_POLY_SPAN as u32;
314    let mut filled = 0usize;
315    let mut ctr = 0u32;
316    while filled < C_POLY_SIZE {
317        let mut h = blake3::Hasher::new();
318        h.update(DOMAIN_LE_CHALLENGE_POLY.as_bytes());
319        h.update(seed);
320        h.update(&ctr.to_le_bytes());
321        let block = h.finalize();
322        for chunk in block.as_bytes().chunks_exact(4) {
323            if filled >= C_POLY_SIZE {
324                break;
325            }
326            let u = u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]);
327            coeffs[filled] = (u % (2 * span + 1)) as i32 - C_POLY_SPAN;
328            filled += 1;
329        }
330        ctr = ctr.wrapping_add(1);
331    }
332    coeffs
333}
334
335fn challenge_poly_to_rq(poly: &[i32; C_POLY_SIZE]) -> RqPoly {
336    let mut out = [0u32; N];
337    for i in 0..C_POLY_SIZE {
338        let c = poly[i];
339        out[i] = if c >= 0 {
340            (c as u32) % Q
341        } else {
342            Q - ((-c) as u32 % Q)
343        };
344    }
345    RqPoly(out)
346}
347
348fn is_canonical_poly(poly: &RqPoly) -> bool {
349    poly.0.iter().all(|&c| c < Q)
350}
351
352fn mu_from_public(public: &PublicInstance) -> RqPoly {
353    let PublicBinding::DigestCoeffVector { coeffs } = &public.binding;
354    let mut out = [0u32; N];
355    out[..PUBLIC_DIGEST_COEFFS].copy_from_slice(coeffs);
356    RqPoly(out)
357}
358
359/// \(C = A r + \mu(public)\).
360pub fn commit_mlwe(
361    vk: &VerifyingKey,
362    public: &PublicInstance,
363    witness: &Witness,
364) -> Result<Commitment, LeError> {
365    public.validate()?;
366    witness.validate()?;
367    let a = vk.matrix_a_poly();
368    let r = ScrubbedPoly::from_public(&short_vec_to_rq(&witness.r)?);
369    let ar = r.mul_public(&a)?;
370    let mu = mu_from_public(public);
371    Ok(Commitment(ar.as_public().add(&mu)))
372}
373
374pub fn prove_with_witness(
375    vk: &VerifyingKey,
376    public: &PublicInstance,
377    witness: &Witness,
378    commitment: &Commitment,
379    binding_context: &[u8; 32],
380    rng: &mut impl DeterministicRng,
381) -> Result<LatticeProof, LeError> {
382    public.validate()?;
383    witness.validate()?;
384    let a = vk.matrix_a_poly();
385    let r_poly = ScrubbedPoly::from_public(&short_vec_to_rq(&witness.r)?);
386    let mu = mu_from_public(public);
387    let u = ScrubbedPoly::from_public(&commitment.0.sub(&mu));
388
389    for _ in 0..MAX_PROVER_ATTEMPTS {
390        let mut y_arr = [0i32; N];
391        for coeff in &mut y_arr {
392            *coeff = (rng.next_u32() % (2 * ETA + 1)) as i32 - ETA as i32;
393        }
394        let y_poly = ScrubbedPoly::from_public(&short_vec_to_rq_bound(&y_arr, ETA)?);
395        y_arr.zeroize();
396        let t = y_poly.mul_public(&a)?.as_public();
397        let challenge_seed = fs_challenge_bytes(binding_context, vk, public, commitment, &t);
398        let c_poly = challenge_poly(&challenge_seed);
399        let c_rq = challenge_poly_to_rq(&c_poly);
400        let c_rq_secret = ScrubbedPoly::from_public(&c_rq);
401        let cr = r_poly.mul_public(&c_rq)?;
402        let z = y_poly.add(&cr);
403        if ct_reject_if_above_gamma(&z.as_public()).unwrap_u8() == 0 {
404            continue;
405        }
406        let lhs = z.mul_public(&a)?.as_public();
407        let rhs = t.add(&c_rq_secret.mul_scrubbed(&u)?.as_public());
408        if lhs == rhs {
409            return Ok(LatticeProof {
410                t,
411                z: z.into_public(),
412                challenge_seed,
413            });
414        }
415    }
416    Err(LeError::ProverAborted)
417}
418
419/// Algebraic verification: \(\|z\|_\infty \le \gamma\), recompute \(c\), check \(Az = t + c(C-\mu)\). **No `Witness`.**
420pub fn verify_lattice_algebraic(
421    vk: &VerifyingKey,
422    public: &PublicInstance,
423    commitment: &Commitment,
424    proof: &LatticeProof,
425    binding_context: &[u8; 32],
426) -> Result<bool, LeError> {
427    public.validate()?;
428    if !is_canonical_poly(&commitment.0)
429        || !is_canonical_poly(&proof.t)
430        || !is_canonical_poly(&proof.z)
431    {
432        return Err(LeError::OversizedInput);
433    }
434    if ct_reject_if_above_gamma(&proof.z).unwrap_u8() == 0 {
435        return Err(LeError::InvalidNorm);
436    }
437    let a = vk.matrix_a_poly();
438    let mu = mu_from_public(public);
439    let u = commitment.0.sub(&mu);
440    let challenge_seed = fs_challenge_bytes(binding_context, vk, public, commitment, &proof.t);
441    if challenge_seed.ct_eq(&proof.challenge_seed).unwrap_u8() == 0 {
442        return Err(LeError::DomainMismatch);
443    }
444    let c_poly = challenge_poly(&challenge_seed);
445    let c_rq = challenge_poly_to_rq(&c_poly);
446    let lhs = a.mul(&proof.z)?;
447    let rhs = proof.t.add(&c_rq.mul(&u)?);
448    if lhs == rhs {
449        Ok(true)
450    } else {
451        Err(LeError::DomainMismatch)
452    }
453}
qssm_le/protocol/commit.rs

qssm_le/protocol/
commit.rs
