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§
- Interactive version of the proof
- Non-interactive version of the proof
Structs§
- Auxiliary data known to both prover and verifier
- Prover’s first message, obtained by
interactive::commit
- Public data that both parties know
- Error indicating that proof is invalid
- Prover’s data accompanying the commitment. Kept as state between rounds in the interactive protocol.
- Private data of prover
- The ZK proof, computed by
interactive::prove
- 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§
- Verifier’s challenge to prover. Can be obtained deterministically by
non_interactive::challenge
or randomly byinteractive::challenge