Module paillier_affine_operation_in_range 

ZK-proof of paillier operation with group commitment in range. Called Пaff-g or Raff-g in the CGGMP24 paper.

Description

A party P performs a paillier affine operation with C, Y, and X obtaining D = C*X + Y. X and Y are encrypted values of x and y. P then wants to prove that y and x are at most L and L' bits, correspondingly, and P doesn’t want to disclose none of the plaintexts

Given:

• key0, pkey0, key1, pkey1 - pairs of public and private keys in paillier cryptosystem
• nonce_y, nonce - nonces in paillier encryption
• x, y - some numbers
• q, g such that <g> = Zq* - prime order group
• C is some ciphertext encrypted by key0
• Y = key1.encrypt(y, nonce_y)
• X = g * x
• D = oadd(enc(y, nonce), omul(x, C)) where enc, oadd and omul are paillier encryption, homomorphic addition and multiplication with key0

Prove:

• bitsize(abs(x)) <= l_x
• bitsize(abs(y)) <= l_y

Disclosing only: key0, key1, C, D, Y, X

Example

use paillier_zk::{paillier_affine_operation_in_range as p, IntegerExt};
use fast_paillier::backend::Integer;
use generic_ec::{Point, curves::Secp256k1 as E};

// Prover and verifier have a shared protocol state
let shared_state = "some shared state";

let mut rng = rand_core::OsRng;

// 0. Setup: prover and verifier share common Ring-Pedersen parameters:

let aux: p::Aux = pregenerated::verifier_aux();
let security = p::SecurityParams {
    l_x: 256,
    l_y: 256 * 5,
    epsilon: 256 * 2,
};

// 1. Setup: prover prepares the paillier keys

// C and D are encrypted by this key
let key_j: fast_paillier::EncryptionKey = pregenerated::someone_encryption_key0();
// Y is encrypted using this key
let key_i: fast_paillier::EncryptionKey = pregenerated::someone_encryption_key1();

// C is some number encrypted using key_j. Neither of parties
// need to know the plaintext
let ciphertext_c = Integer::sample_in_mult_group_of(&mut rng, &key_j.nn());

// 2. Setup: prover prepares all plaintexts

// x in paper
let plaintext_x = Integer::from_rng_half_pm(
    &mut rng,
    &(Integer::one() << security.l_x),
);
// y in paper
let plaintext_y = Integer::from_rng_half_pm(
    &mut rng,
    &(Integer::one() << security.l_y),
);

// 3. Setup: prover encrypts everything on correct keys and remembers some nonces

// X in paper
let ciphertext_x = Point::<E>::generator() * plaintext_x.to_scalar();
// Y and ρ_y in paper
let (ciphertext_y, nonce_y) = key_i.encrypt_with_random(
    &mut rng,
    &(plaintext_y),
)?;
// nonce is ρ in paper
let (ciphertext_y_by_key_j, nonce) = key_j.encrypt_with_random(
    &mut rng,
    &(plaintext_y)
)?;
// D in paper
let ciphertext_d = key_j
    .oadd(
        &key_j.omul(&plaintext_x, &ciphertext_c)?,
        &ciphertext_y_by_key_j,
    )?;

// 4. Prover computes a non-interactive proof that plaintext_x and
//    plaintext_y are at most `l_x` and `l_y` bits

let data = p::Data {
    key_j: &key_j,
    key_i: &key_i,
    c: &ciphertext_c,
    d: &ciphertext_d,
    x: &ciphertext_x,
    y: &ciphertext_y,
};
let pdata = p::PrivateData {
    x: &plaintext_x,
    y: &plaintext_y,
    nonce: &nonce,
    nonce_y: &nonce_y,
};
let proof =
    p::non_interactive::prove::<E, sha2::Sha256>(
        &shared_state,
        &aux,
        data,
        pdata,
        &security,
        &mut rng,
    )?;

// 5. Prover sends this data to verifier

send(&data, &proof);

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

let (data, proof) = recv();
let r = p::non_interactive::verify::<E, sha2::Sha256>(
    &shared_state,
    &aux,
    data,
    &security,
    &proof,
)?;

If the verification succeeded, verifier can continue communication with prover

Modules

interactive

The interactive version of the ZK proof. Should be completed in 3 rounds: prover commits to data, verifier responds with a random challenge, and prover gives proof with commitment and challenge.

non_interactive

The non-interactive version of proof. Completed in one round, for example see the documentation of parent module.

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