Module paillier_zk::paillier_affine_operation_in_range

source ·
Expand description

ZK-proof of paillier operation with group commitment in range. Called Пaff-g or Raff-g in the CGGMP21 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 rug::{Integer, Complete};
use generic_ec::{Point, curves::Secp256k1 as E};

// Prover and verifier have a shared protocol state
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:

let aux: p::Aux = pregenerated::verifier_aux();
let security = p::SecurityParams {
    l_x: 256,
    l_y: 848,
    epsilon: 230,
    q: (Integer::ONE << 128_u32).complete(),
};

// 1. Setup: prover prepares the paillier keys

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

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

// 2. Setup: prover prepares all plaintexts

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

// 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) = key1.encrypt_with_random(
    &mut rng,
    &(plaintext_y.signed_modulo(key1.n())),
)?;
// nonce is ρ in paper
let (ciphertext_y_by_key1, nonce) = key0.encrypt_with_random(
    &mut rng,
    &(plaintext_y.signed_modulo(key0.n()))
)?;
// D in paper
let ciphertext_d = key0
    .oadd(
        &key0.omul(&plaintext_x, &ciphertext_c)?,
        &ciphertext_y_by_key1,
    )?;

// 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 {
    key0: &key0,
    key1: &key1,
    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 (commitment, proof) =
    p::non_interactive::prove(
        shared_state_prover,
        &aux,
        data,
        pdata,
        &security,
        &mut rng,
    )?;

// 5. Prover sends this data to verifier

send(&data, &commitment, &proof);

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

let (data, commitment, proof) = recv();
let r = p::non_interactive::verify(
    shared_state_verifier,
    &aux,
    data,
    &commitment,
    &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§

Type Aliases§