Module no_small_factor 

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

Description

Both parties agree on verifier aux data and security level. Common input is n > 4*security.l. Prover additionally knows primes p, q < pow(2, security.l) * sqrt(n).

Proof guarantees that each p, q > pow(2, security.l).

Example

use fast_paillier::backend::Integer;
use paillier_zk::no_small_factor as p;

let shared_state = "some shared state";
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: 256,
    epsilon: 512,
};

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

let [p, q, ..] = pregenerated::primes_1536bits();
let n = &p * &q;
let n_root = n.sqrt_ref().unwrap();
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::non_interactive::prove::<sha2::Sha256>(
    &shared_state,
    &aux,
    data,
    p::PrivateData { p: &p, q: &q },
    &security,
    &mut 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().unwrap();
let data = p::Data {
    n: &n,
    n_root: &n_root,
};
p::non_interactive::verify::<sha2::Sha256>(&shared_state, &aux, data, &security, &proof)?;

If the verification succeeded, verifier can continue communication with prover

Modules

interactive

Interactive version of the proof

non_interactive

Non-interactive version of the proof

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

NiProof

The non-interactive ZK proof. Computed by non_interactive::prove. Combines commitment and proof.

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

Challenge

Verifier’s challenge to prover. Can be obtained deterministically by non_interactive::challenge or randomly by interactive::challenge