confium_tc_cmp20/

mta_proofs.rs

//! Zero-knowledge proofs for the MtA protocol — GG18/GG20 Appendix A
//! (Gennaro & Goldfeder, eprint 2019/114 A.1/A.2), the construction
//! spec 70-cmp20 requires on every MtA ciphertext.
//!
//! Two proofs, both sigma protocols made non-interactive via
//! Fiat-Shamir (SHA-256 over the full transcript, challenge reduced
//! mod `q`, the ECDSA group order):
//!
//! - [`RangeProof`] (initiator): for Paillier ciphertext
//!   `c = Γ^m·r^N mod N²`, proves knowledge of `(m, r)` with
//!   `m ∈ [0, q³]` — the "small ciphertext" guarantee that prevents
//!   the wrap-around attacks described in the paper.
//! - [`RespondentProof`] (responder, plain MtA): for
//!   `c₂ = c₁^x·Γ^y·r^N mod N²`, proves knowledge of `(x, y, r)` with
//!   `x ∈ [0, q³]` and `y ∈ [0, q⁷]` — binding the response to the
//!   received ciphertext and bounding the mask.
//!
//! The commitments use an auxiliary Strong-RSA modulus
//! `Ñ = P̃·Q̃` with `P̃ = 2p̃+1`, `Q̃ = 2q̃+1` (safe primes) and
//! `h₁, h₂ ∈ Z*_Ñ` with `h₂ = h₁^w` for discarded `w` — nobody (least
//! of all the prover) knows the discrete log of `h₂` in base `h₁`,
//! which is what makes the h-commitments binding.
//!
//! # Trust model and limitations (audit ledger)
//!
//! - A commitment key is generated by the VERIFIER and used by the
//!   OTHER party as prover. Never prove against a key you generated
//!   yourself — you would know the h₂/h₁ discrete log.
//! - The paper proves Ñ is of the correct form (safe-prime product)
//!   with an additional ZK proof ([Gennaro-Micciancio-Rabin]); this
//!   implementation generates such moduli honestly but does NOT yet
//!   prove their form to verifiers. A malicious verifier could
//!   mis-generate a key to break a prover's privacy. Trusted-setup
//!   gap, tracked in the audit ledger.
//! - Soundness holds under Strong RSA over Ñ; size Ñ accordingly
//!   (the paper's setting: 2048-bit Ñ alongside 2048-bit N).

use confium_tc::paillier::PaillierPublicKey;
use confium_tc::paillier::generate_prime;
use confium_tc::paillier::miller_rabin;
use num_bigint::BigUint;
use num_bigint::RandBigInt;
use num_traits::One;
use num_traits::Zero;
use rand::rngs::OsRng;
use sha2::Digest;
use sha2::Sha256;

/// Auxiliary commitment key `(Ñ, h₁, h₂)` — see the module docs.
#[derive(Debug, Clone)]
pub struct CommitmentKey {
    /// Safe-prime product modulus.
    pub n_tilde: BigUint,
    /// First generator (a random quadratic residue).
    pub h1: BigUint,
    /// Second generator (`h₁^w` for discarded `w`).
    pub h2: BigUint,
}

/// Generate a commitment key: `Ñ = P̃Q̃` with `P̃, Q̃` safe primes of
/// `prime_bits` each, `h₁` a random quadratic residue mod `Ñ`, and
/// `h₂ = h₁^w` for uniformly random discarded `w`.
///
/// The generator of this key is its VERIFIER — see the module docs
/// for the trust direction.
pub fn generate_commitment_key(prime_bits: u32) -> CommitmentKey {
    let p_tilde = generate_safe_prime(prime_bits);
    let q_tilde = loop {
        let candidate = generate_safe_prime(prime_bits);
        if candidate != p_tilde {
            break candidate;
        }
    };
    let n_tilde = &p_tilde * &q_tilde;

    let mut rng = OsRng;
    // h1: a random quadratic residue — squaring guarantees membership
    // in QR(Ñ) without knowing the factorization.
    let h1 = {
        let x = rng.gen_biguint_range(&BigUint::one(), &n_tilde);
        (&x * &x) % &n_tilde
    };
    // h2 = h1^w with w discarded: the discrete log of h₂ in base h₁
    // is unknown to everyone, including this generator.
    let w = rng.gen_biguint_range(&BigUint::one(), &n_tilde);
    let h2 = h1.modpow(&w, &n_tilde);

    CommitmentKey { n_tilde, h1, h2 }
}

/// The P-256 group order `q`, as the proofs' range parameter.
pub fn p256_order() -> num_bigint::BigUint {
    num_bigint::BigUint::parse_bytes(
        b"ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
        16,
    )
    .expect("static hex parses")
}

fn generate_safe_prime(prime_bits: u32) -> BigUint {
    loop {
        let p = generate_prime(prime_bits);
        let candidate = (&p << 1u32) + BigUint::one();
        if miller_rabin(&candidate, 20) {
            return candidate;
        }
    }
}

/// Initiator's range proof: knowledge of `(m, r)` with
/// `c = Γ^m·r^N mod N²` and `m ∈ [0, q³]`.
#[derive(Debug, Clone)]
pub struct RangeProof {
    /// Commitment `h₁^m·h₂^ρ mod Ñ`.
    pub z: BigUint,
    /// Announcement `Γ^α·β^N mod N²`.
    pub u: BigUint,
    /// Announcement `h₁^α·h₂^γ mod Ñ`.
    pub w: BigUint,
    /// Response `r^e·β mod N`.
    pub s: BigUint,
    /// Response `e·m + α` (checked `≤ q³` as an integer).
    pub s1: BigUint,
    /// Response `e·ρ + γ`.
    pub s2: BigUint,
}

/// Prove that `c = Γ^m·r^N mod N²` opens to `m ∈ [0, q³)`.
///
/// `r` must be the exact Paillier randomness used to build `c`.
pub fn prove_range(
    q: &BigUint,
    paillier: &PaillierPublicKey,
    ck: &CommitmentKey,
    c: &BigUint,
    m: &BigUint,
    r: &BigUint,
) -> RangeProof {
    let q3 = q * q * q;
    let q2 = q * q;
    let q_n_tilde = q * &ck.n_tilde;
    let q3_n_tilde = &q3 * &ck.n_tilde;

    let mut rng = OsRng;
    // α ← [0, q³ − q²): guarantees the honest s₁ = e·m + α stays
    // below q³ (e·m < q² for m < q), so completeness never fails.
    let alpha = rng.gen_biguint_range(&BigUint::zero(), &(&q3 - &q2));
    let beta = rng.gen_biguint_range(&BigUint::one(), &paillier.n);
    let gamma = rng.gen_biguint_range(&BigUint::zero(), &(&q3_n_tilde - &q_n_tilde));
    let rho = rng.gen_biguint_range(&BigUint::zero(), &q_n_tilde);

    let z = (&ck.h1.modpow(m, &ck.n_tilde) * &ck.h2.modpow(&rho, &ck.n_tilde)) % &ck.n_tilde;
    let u = (&paillier.g.modpow(&alpha, &paillier.n_squared)
        * &beta.modpow(&paillier.n, &paillier.n_squared))
        % &paillier.n_squared;
    let w = (&ck.h1.modpow(&alpha, &ck.n_tilde) * &ck.h2.modpow(&gamma, &ck.n_tilde)) % &ck.n_tilde;

    let e = range_challenge(q, paillier, ck, c, &z, &u, &w);

    let s = (r.modpow(&e, &paillier.n) * &beta) % &paillier.n;
    let s1 = &e * m + &alpha;
    let s2 = &e * &rho + &gamma;

    RangeProof { z, u, w, s, s1, s2 }
}

/// Verify an initiator range proof for ciphertext `c`.
pub fn verify_range(
    q: &BigUint,
    paillier: &PaillierPublicKey,
    ck: &CommitmentKey,
    c: &BigUint,
    proof: &RangeProof,
) -> bool {
    let q3 = q * q * q;
    // Integer range check: this is what actually bounds m (soundness
    // slack q⁴ for a q-range challenge).
    if proof.s1 > q3 {
        return false;
    }
    if proof.s.is_zero() || proof.s >= paillier.n || proof.s1.is_zero() {
        return false;
    }

    let e = range_challenge(q, paillier, ck, c, &proof.z, &proof.u, &proof.w);

    // u == Γ^{s1}·s^N·c^{-e}  (mod N²)
    let c_inv = match modinv(&to_bigint_helper(c), &to_bigint_helper(&paillier.n_squared)) {
        Some(inv) => inv.to_biguint().unwrap(),
        None => return false,
    };
    let lhs = (&paillier.g.modpow(&proof.s1, &paillier.n_squared)
        * &proof.s.modpow(&paillier.n, &paillier.n_squared)
        % &paillier.n_squared
        * &c_inv.modpow(&e, &paillier.n_squared))
        % &paillier.n_squared;
    if lhs != proof.u {
        return false;
    }

    // w == h1^{s1}·h2^{s2}·z^{-e}  (mod Ñ)
    let z_inv = match modinv(&to_bigint_helper(&proof.z), &to_bigint_helper(&ck.n_tilde)) {
        Some(inv) => inv.to_biguint().unwrap(),
        None => return false,
    };
    let lhs2 = (&ck.h1.modpow(&proof.s1, &ck.n_tilde) * &ck.h2.modpow(&proof.s2, &ck.n_tilde)
        % &ck.n_tilde
        * &z_inv.modpow(&e, &ck.n_tilde))
        % &ck.n_tilde;
    lhs2 == proof.w
}

/// Responder proof for plain MtA: knowledge of `(x, y, r)` with
/// `c₂ = c₁^x·Γ^y·r^N mod N²`, `x ∈ [0, q³]`, `y ∈ [0, q⁷]`.
#[derive(Debug, Clone)]
pub struct RespondentProof {
    /// Commitment `h₁^x·h₂^ρ mod Ñ` (binds the secret x).
    pub z: BigUint,
    /// Announcement `h₁^α·h₂^{ρ'} mod Ñ`.
    pub z_prime: BigUint,
    /// Commitment `h₁^y·h₂^σ mod Ñ` (binds the mask y).
    pub t: BigUint,
    /// Announcement `c₁^α·Γ^γ·β^N mod N²`.
    pub v: BigUint,
    /// Announcement `h₁^γ·h₂^τ mod Ñ`.
    pub w: BigUint,
    /// Response `r^e·β mod N`.
    pub s: BigUint,
    /// Response `e·x + α` (checked `≤ q³`).
    pub s1: BigUint,
    /// Response `e·ρ + ρ'`.
    pub s2: BigUint,
    /// Response `e·y + γ` (checked `≤ q⁷`).
    pub t1: BigUint,
    /// Response `e·σ + τ`.
    pub t2: BigUint,
}

/// Prove the responder statement for `c₂ = c₁^x·Γ^y·r^N mod N²`,
/// where `r` is the Paillier randomness used for the `Γ^y` term.
// The interface mirrors the paper's statement one-to-one: statement
// (c₁, c₂) + witness (x, y, r) + parameters (q, N-pair, ck).
#[allow(clippy::too_many_arguments)]
pub fn prove_respondent(
    q: &BigUint,
    paillier: &PaillierPublicKey,
    ck: &CommitmentKey,
    c1: &BigUint,
    c2: &BigUint,
    x: &BigUint,
    y: &BigUint,
    r: &BigUint,
) -> RespondentProof {
    let q3 = q * q * q;
    let q7 = &q3 * &q3 * q;
    let q6 = &q3 * &q3;
    let q2 = q * q;
    let q_n_tilde = q * &ck.n_tilde;
    let q3_n_tilde = &q3 * &ck.n_tilde;

    let mut rng = OsRng;
    let alpha = rng.gen_biguint_range(&BigUint::zero(), &(&q3 - &q2));
    let rho = rng.gen_biguint_range(&BigUint::zero(), &q_n_tilde);
    let rho_prime = rng.gen_biguint_range(&BigUint::zero(), &(&q3_n_tilde - &q_n_tilde));
    let sigma = rng.gen_biguint_range(&BigUint::zero(), &q_n_tilde);
    let beta = rng.gen_biguint_range(&BigUint::one(), &paillier.n);
    // γ ← [0, q⁷ − q⁶): keeps the honest t₁ = e·y + γ below q⁷.
    let gamma = rng.gen_biguint_range(&BigUint::zero(), &(&q7 - &q6));
    let tau = rng.gen_biguint_range(&BigUint::zero(), &(&q3_n_tilde - &q_n_tilde));

    let n_tilde = &ck.n_tilde;
    let h_pow = |a: &BigUint, b: &BigUint| ck.h1.modpow(a, n_tilde) * &ck.h2.modpow(b, n_tilde);

    let z = h_pow(x, &rho) % n_tilde;
    let z_prime = h_pow(&alpha, &rho_prime) % n_tilde;
    let t = h_pow(y, &sigma) % n_tilde;
    let v = (&c1.modpow(&alpha, &paillier.n_squared)
        * &paillier.g.modpow(&gamma, &paillier.n_squared)
        % &paillier.n_squared
        * &beta.modpow(&paillier.n, &paillier.n_squared))
        % &paillier.n_squared;
    let w = h_pow(&gamma, &tau) % n_tilde;

    let e = respondent_challenge(q, paillier, ck, c1, c2, &z, &z_prime, &t, &v, &w);

    let s = (r.modpow(&e, &paillier.n) * &beta) % &paillier.n;
    let s1 = &e * x + &alpha;
    let s2 = &e * &rho + &rho_prime;
    let t1 = &e * y + &gamma;
    let t2 = &e * &sigma + &tau;

    RespondentProof {
        z,
        z_prime,
        t,
        v,
        w,
        s,
        s1,
        s2,
        t1,
        t2,
    }
}

/// Verify a responder proof binding `c₂` to `c₁` with bounded secrets.
#[allow(clippy::too_many_arguments)]
pub fn verify_respondent(
    q: &BigUint,
    paillier: &PaillierPublicKey,
    ck: &CommitmentKey,
    c1: &BigUint,
    c2: &BigUint,
    proof: &RespondentProof,
) -> bool {
    let q3 = q * q * q;
    let q7 = &q3 * &q3 * q;
    if proof.s1 > q3 || proof.t1 > q7 {
        return false;
    }
    if proof.s.is_zero() || proof.s >= paillier.n || proof.s1.is_zero() || proof.t1.is_zero() {
        return false;
    }

    let e = respondent_challenge(
        q,
        paillier,
        ck,
        c1,
        c2,
        &proof.z,
        &proof.z_prime,
        &proof.t,
        &proof.v,
        &proof.w,
    );

    // z' == h1^{s1}·h2^{s2}·z^{-e}  (mod Ñ)
    let n_tilde = &ck.n_tilde;
    let z_inv = match modinv(&to_bigint_helper(&proof.z), &to_bigint_helper(n_tilde)) {
        Some(inv) => inv.to_biguint().unwrap(),
        None => return false,
    };
    let lhs1 = (&ck.h1.modpow(&proof.s1, n_tilde) * &ck.h2.modpow(&proof.s2, n_tilde) % n_tilde
        * &z_inv.modpow(&e, n_tilde))
        % n_tilde;
    if lhs1 != proof.z_prime {
        return false;
    }

    // w == h1^{t1}·h2^{t2}·t^{-e}  (mod Ñ)
    let t_inv = match modinv(&to_bigint_helper(&proof.t), &to_bigint_helper(n_tilde)) {
        Some(inv) => inv.to_biguint().unwrap(),
        None => return false,
    };
    let lhs2 = (&ck.h1.modpow(&proof.t1, n_tilde) * &ck.h2.modpow(&proof.t2, n_tilde) % n_tilde
        * &t_inv.modpow(&e, n_tilde))
        % n_tilde;
    if lhs2 != proof.w {
        return false;
    }

    // v == c1^{s1}·s^N·Γ^{t1}·c2^{-e}  (mod N²)
    let c2_inv = match modinv(
        &to_bigint_helper(c2),
        &to_bigint_helper(&paillier.n_squared),
    ) {
        Some(inv) => inv.to_biguint().unwrap(),
        None => return false,
    };
    let lhs3 = (&c1.modpow(&proof.s1, &paillier.n_squared)
        * &proof.s.modpow(&paillier.n, &paillier.n_squared)
        % &paillier.n_squared
        * &paillier.g.modpow(&proof.t1, &paillier.n_squared)
        % &paillier.n_squared
        * &c2_inv.modpow(&e, &paillier.n_squared))
        % &paillier.n_squared;
    lhs3 == proof.v
}

// ---- helpers -----------------------------------------------------------

fn range_challenge(
    q: &BigUint,
    paillier: &PaillierPublicKey,
    ck: &CommitmentKey,
    c: &BigUint,
    z: &BigUint,
    u: &BigUint,
    w: &BigUint,
) -> BigUint {
    let mut hasher = Sha256::new();
    hasher.update(b"confium-mta-range-v1");
    hasher.update(q.to_bytes_be());
    hasher.update(paillier.n.to_bytes_be());
    hasher.update(paillier.g.to_bytes_be());
    hasher.update(ck.n_tilde.to_bytes_be());
    hasher.update(ck.h1.to_bytes_be());
    hasher.update(ck.h2.to_bytes_be());
    hasher.update(c.to_bytes_be());
    hasher.update(z.to_bytes_be());
    hasher.update(u.to_bytes_be());
    hasher.update(w.to_bytes_be());
    challenge_from_hash(hasher, q)
}

// Transcript-hashing helper: every Fiat-Shamir input is a
// parameter by construction.
#[allow(clippy::too_many_arguments)]
fn respondent_challenge(
    q: &BigUint,
    paillier: &PaillierPublicKey,
    ck: &CommitmentKey,
    c1: &BigUint,
    c2: &BigUint,
    z: &BigUint,
    z_prime: &BigUint,
    t: &BigUint,
    v: &BigUint,
    w: &BigUint,
) -> BigUint {
    let mut hasher = Sha256::new();
    hasher.update(b"confium-mta-respondent-v1");
    hasher.update(q.to_bytes_be());
    hasher.update(paillier.n.to_bytes_be());
    hasher.update(paillier.g.to_bytes_be());
    hasher.update(ck.n_tilde.to_bytes_be());
    hasher.update(ck.h1.to_bytes_be());
    hasher.update(ck.h2.to_bytes_be());
    hasher.update(c1.to_bytes_be());
    hasher.update(c2.to_bytes_be());
    hasher.update(z.to_bytes_be());
    hasher.update(z_prime.to_bytes_be());
    hasher.update(t.to_bytes_be());
    hasher.update(v.to_bytes_be());
    hasher.update(w.to_bytes_be());
    challenge_from_hash(hasher, q)
}

/// Reduce the digest to a challenge in [0, q) by rejection sampling
/// with re-hash — never a biased or constant fallback.
fn challenge_from_hash(hasher: Sha256, q: &BigUint) -> BigUint {
    // The digest chunks are consumed 8 bytes at a time; each round
    // extends the hashed material so the next digest is independent.
    let mut current: Vec<u8> = hasher.finalize().to_vec();
    loop {
        let candidate = BigUint::from_bytes_be(&current);
        if &candidate < q {
            return candidate;
        }
        let mut h = Sha256::new();
        h.update(b"confium-mta-challenge-reduce-v1");
        h.update(&current);
        current = h.finalize().to_vec();
    }
}

/// Extended GCD can go negative; modinv needs signed arithmetic.
fn to_bigint_helper(x: &BigUint) -> num_bigint::BigInt {
    use num_bigint::ToBigInt;
    x.to_bigint().unwrap_or_default()
}

fn modinv(a: &num_bigint::BigInt, m: &num_bigint::BigInt) -> Option<num_bigint::BigInt> {
    use num_bigint::BigInt;
    let (g, x, _) = extended_gcd(a, m);
    if g != BigInt::one() {
        return None;
    }
    let r = &x % m;
    if r.sign() == num_bigint::Sign::Minus {
        Some(r + m)
    } else {
        Some(r)
    }
}

fn extended_gcd(
    a: &num_bigint::BigInt,
    b: &num_bigint::BigInt,
) -> (num_bigint::BigInt, num_bigint::BigInt, num_bigint::BigInt) {
    use num_bigint::BigInt;
    if b.is_zero() {
        return (a.clone(), BigInt::one(), BigInt::zero());
    }
    let (g, x, y) = extended_gcd(b, &(a % b));
    (g, y.clone(), x - (a / b) * y)
}