zkBFV: Proving Homomorphic BFV Addition Using Plonky2

Cryptography continues to advance at a rapid pace, driving innovations in areas such as secure data processing and privacy-preserving computation. Among these advancements, the Brakerski-Fan-Vercauteren (BFV) homomorphic encryption scheme and Zero-Knowledge Proofs (ZKPs) represent powerful tools for enabling secure, private computations. BFV allows for homomorphic operations on encrypted data, while ZKPs allow us to verify these operations without revealing sensitive information.

In this blog post, we’ll walk through building a simple BFV-based encryption system, performing homomorphic addition on encrypted data, and verifying it using zero-knowledge proofs (ZKPs) with the Plonky2 library in Rust. This step-by-step guide will give you an introduction to the world of verifiable homomorphic encryption, starting with basic operations and progressing toward more advanced applications.

Introduction to BFV

BFV is a type of homomorphic encryption scheme that allows computations, like addition and multiplication, to be performed directly on encrypted data. This means that even though the data is encrypted, useful computations can still be carried out. BFV is especially well-suited for applications where large amounts of numerical data need to be processed privately, such as in financial transactions or medical research.

For example, imagine you have sensitive financial data stored in the cloud, and you want the cloud to compute the total amount of all your transactions. With BFV, you can send the encrypted data to the cloud, perform the addition on the encrypted data, and then receive the encrypted result. Only you, with the secret key, can decrypt the final sum.

Key Properties of BFV

- Privacy-preserving computations: Allows operations on encrypted data without decrypting it.

- Scalability: Can handle large sets of encrypted data, making it suitable for real-world applications.

- Homomorphic addition and multiplication: BFV supports both addition and multiplication of ciphertexts, essential for performing complex computations.

Use Cases of BFV

- Private financial analysis: Perform encrypted calculations on sensitive financial data.

- Medical data processing: Process encrypted medical records without revealing patient information.

- Encrypted cloud computing: Allow cloud services to perform computations on encrypted data without accessing the raw data.

BFV Encryption

The BFV encryption scheme operates over polynomials and allows for homomorphic operations on encrypted data. It relies on polynomial arithmetic, modular arithmetic, and noise addition to ensure security. Here's a breakdown of the key mathematical components of BFV encryption.

Key Parameters

- Secret key (s(x)): A polynomial with small coefficients (e.g., coefficients in {-1, 0, 1} that serves as the private key.

- Plaintext modulus (t): A small modulus, typically a prime number (e.g., t = 65537), used to encode the message.

- Ciphertext modulus (q): A large modulus to ensure the encryption stays within a finite field and supports homomorphic operations.

- Scaling factor (Δ): A scaling factor defined as Δ = q/t, which is used to encode plaintext into the ciphertext space.

- Error (noise) term (e(x)): A small random polynomial added to the ciphertext to make it difficult for an adversary to recover the secret key or plaintext.

- Random polynomial (a(x)): A uniformly random polynomial that helps "hide" the secret key during encryption.

- Public key (p1(x), p2(x)): p1(x) = a(x) and p2(x) = a(x) • s(x) + e(x).

$$c_1(x) = pk_1(x) \cdot u(x) + e_1(x)$$

$$c_2(x) = pk_2(x) \cdot u(x) + e_2(x) + \Delta \cdot m(x)$$

The pair (c1(x), c2(x)) is our ciphertext!

Building a Rust Code to Prove Homomorphic BFV Additions

Now, let’s dive into building our BFV-based homomorphic encryption system, performing ciphertext addition, and verifying the results using a ZKP built with Plonky2. Below, we outline the step-by-step implementation in Rust.

Step 1: Setting Up Dependencies

use anyhow::Result;
use plonky2::field::types::Field;
use plonky2::iop::witness::{PartialWitness, WitnessWrite};
use plonky2::plonk::circuit_builder::CircuitBuilder;
use plonky2::plonk::circuit_data::CircuitConfig;
use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
use rand::random;

Step 2: Defining BFV Parameters and Keys

In this step, we define the BFV scheme parameters such as the secret key and public key. These keys will be used for encryption and decryption.

pub const NOISE_BOUND: u64 = 10;  // Limit for noise terms
pub const Q: u64 = 1 << 59;  // Ciphertext modulus

fn main() -> Result<()> {
    const D: usize = 2;
    const N: usize = 2048;  // Polynomial degree

    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;

    // Key generation: sample secret key
    let secret_key: [F; N] = sample_r2_poly();

    // Generate public key
    let (public_key_a, public_key_b) = generate_public_key(&secret_key, F::from_canonical_u64(Q));

    // Encrypt messages
    let m1: [F; N] = [F::from_canonical_u64(1); N];  // Message 1
    let m2: [F; N] = [F::from_canonical_u64(0); N];  // Message 2

    let delta = F::from_canonical_u64(Q) / F::from_canonical_u64(65537);  // Delta for scaling

    // Encrypt two messages
    let (c1_1, c1_2) = encrypt_with_public_key(&public_key_a, &public_key_b, &m1, delta);
    let (c2_1, c2_2) = encrypt_with_public_key(&public_key_a, &public_key_b, &m2, delta);
}

Step 3: Homomorphic Ciphertext Addition

Next, we perform homomorphic addition of the encrypted messages. This allows us to add encrypted values without needing to decrypt them first.

// Perform homomorphic addition
let c3_1 = add_polynomials(&c1_1, &c2_1, N);
let c3_2 = c1_2 + c2_2;

Step 4: Verifying Homomorphic Addition Using ZKP

We now create a ZKP circuit to verify that the homomorphic addition was performed correctly.

// Build the circuit to prove correctness of addition
let config = CircuitConfig::standard_recursion_config();
let mut builder = CircuitBuilder::<F, D>::new(config);

let c1_1_targets = builder.add_virtual_target_arr::<{ N }>();
let c2_1_targets = builder.add_virtual_target_arr::<{ N }>();
let secret_key_targets = builder.add_virtual_target_arr::<{ N }>();
let c1_2_target = builder.add_virtual_target();
let c2_2_target = builder.add_virtual_target();

// Compute homomorphic addition in the circuit
let c3_1_targets: Vec<_> = c1_1_targets.iter().zip(c2_1_targets.iter()).map(|(&c1_1i, &c2_1i)| builder.add(c1_1i, c2_1i)).collect();
let c3_2_calc = builder.add(c1_2_target, c2_2_target);

// Verify the result matches the expected sum
let mut c3_1_computed = builder.constant(F::ZERO);
for i in 0..N {
    let term = builder.mul(secret_key_targets[i], c3_1_targets[i]);
    c3_1_computed = builder.add(c3_1_computed, term);
}

// Build and verify the proof
let data = builder.build::<C>();
let proof = data.prove(PartialWitness::new())?;

data.verify(proof)?;

println!("Homomorphic BFV ciphertext sum verified.");
Ok(())

Conclusion

In this tutorial, we built a BFV-based encryption system in Rust, performed homomorphic addition, and used Plonky2 to verify the correctness of the operation with zero-knowledge proofs. By combining homomorphic encryption and zero-knowledge proofs, we can securely compute on encrypted data while maintaining privacy.

This is a powerful tool for applications where sensitive data needs to remain private during computation, and future posts will explore more advanced uses of BFV and ZKPs for verifiable encryption systems.