Module paillier_zk::no_small_factor

source ·
Expand description

ZK-proof for factoring of a RSA modulus. Called Пfac or Rfac in the CGGMP21 paper.

§Description

A party P has a modulus N = pq. P wants to prove to a verifier V that p and q are sufficiently large without disclosing p or q, with p and q each no larger than sqrt(N) * 2^l, or equivalently no smaller than sqrt(N) / 2^l

§Example

use rug::{Integer, Complete};
use paillier_zk::no_small_factor::non_interactive as p;

let shared_state_prover = sha2::Sha256::default();
let shared_state_verifier = sha2::Sha256::default();
let mut rng = rand_core::OsRng;

// 0. Setup: prover and verifier share common Ring-Pedersen parameters, and
// agree on the level of security

let aux: p::Aux = pregenerated::verifier_aux();
let security = p::SecurityParams {
    l: 4,
    epsilon: 128,
    q: (Integer::ONE << 128_u32).complete(),
};

// 1. Prover prepares the data to obtain proof about

let p = fast_paillier::utils::generate_safe_prime(&mut rng, 256);
let q = fast_paillier::utils::generate_safe_prime(&mut rng, 256);
let n = (&p * &q).complete();
let n_root = n.sqrt_ref().complete();
let data = p::Data {
    n: &n,
    n_root: &n_root,
};

// 2. Prover computes a non-interactive proof that both factors are large enough

let proof = p::prove(
    shared_state_prover,
    &aux,
    data,
    p::PrivateData { p: &p, q: &q },
    &security,
    rng,
)?;

// 4. Prover sends this data to verifier

send(data.n, &proof);

// 5. Verifier receives the data and the proof and verifies it

let (n, proof) = recv();
let n_root = n.sqrt_ref().complete();;
let data = p::Data {
    n: &n,
    n_root: &n_root,
};
p::verify(shared_state_verifier, &aux, data, &security, &proof)?;

If the verification succeeded, verifier can continue communication with prover

Modules§

Structs§

  • Aux
    Auxiliary data known to both prover and verifier
  • Commitment
    Prover’s first message, obtained by interactive::commit
  • Data
    Public data that both parties know
  • InvalidProof
    Error indicating that proof is invalid
  • PrivateCommitment
    Prover’s data accompanying the commitment. Kept as state between rounds in the interactive protocol.
  • PrivateData
    Private data of prover
  • Proof
    The ZK proof, computed by interactive::prove
  • SecurityParams
    Security parameters for proof. Choosing the values is a tradeoff between speed and chance of rejecting a valid proof or accepting an invalid proof

Type Aliases§