PRISM: Efficient zkSNARKs for RNS-Based Homomorphic Encryption

A prototype implementation of PRISM, a practical zkSNARK for standard RNS-based Homomorphic Encryption (HE) schemes, including BGV and CKKS.

Warning: This is an academic proof-of-concept prototype, and has not received careful code review. This implementation is NOT ready for any production use.

Overview

PRISM consists of two main components: (i) (MF-)PCS; (ii) (zk-)PIOP for RNS-based HE evaluations.

Dependencies

• OS: Ubuntu 22.04 LTS
• Compiler: C++17 compatible (GCC/Clang)
• Libraries:
  • GMP 6.2.1
  • NTL 11.5.1
  • Microsoft SEAL 4.1.2
  • EMP-toolkit

Install basic build tools:

sudo apt-get update
sudo apt-get install -y cmake git build-essential

Then install GMP, NTL, and Microsoft SEAL according to their official documentation.

Build

mkdir build
cd build
cmake ..
make

Usage

All commands below assume you are in the ./build directory.

PIOP for CKKS (non-ZK)

Command	Scenario
./test/test_CKKS 1	Ciphertext multiplication (CM)
./test/test_CKKS 2	Matrix-vector multiplication (MVM)
./test/test_CKKS 3	Basic neural network layers (NN)
./test/test_CKKS 4	Logistic regression training (LR)
./test/test_CKKS 5	Comparison approximation (CA)
./test/test_CKKS 6	CM + noise flooding

PIOP for CKKS (ZK)

Command	Scenario
./test/test_CKKS_ZK 1	Ciphertext multiplication (CM)
./test/test_CKKS_ZK 2	Matrix-vector multiplication (MVM)
./test/test_CKKS_ZK 3	Basic neural network layers (NN)
./test/test_CKKS_ZK 4	Logistic regression training (LR)
./test/test_CKKS_ZK 5	Comparison approximation (CA)

PIOP for BGV (non-ZK)

Command	Scenario
./test/test_BGV 1	Ciphertext multiplication (CM)
./test/test_BGV 2	Matrix-vector multiplication (MVM)
./test/test_BGV 3	Basic neural network layers (NN)

PIOP for BGV (ZK)

Command	Scenario
./test/test_BGV_ZK 1	Ciphertext multiplication (CM)
./test/test_BGV_ZK 2	Matrix-vector multiplication (MVM)
./test/test_BGV_ZK 3	Basic neural network layers (NN)

PCS and MF-PCS Benchmarks

./test/test_pcs <scenario>

Argument	Scenario	Polynomial degree and fields	Batch size
1	CKKS CM/MVM	N=8192, four 48-bit fields	B=2^8
2	CKKS NN	N=4096, three 36-bit fields	B=2^8
3	CKKS LR	N=16384, eight 48-bit fields	B=2^8
4	CKKS CA	N=16384, nine 48-bit fields	B=2^8
5	CKKS CM+NF	N=8192, three 48-bit fields	B=2^8
6	BGV CM/MVM	N=8192, four 48-bit coefficient fields and one 32-bit plaintext field	B=2^8
7	BGV NN	N=4096, three 36-bit coefficient fields and one 32-bit plaintext field	B=2^8
8	Standalone MF-PCS sweep	N=16384, eight 48-bit fields, F=2,...,8	B in {2^4,2^6,2^8,2^10}

Scenarios 1–6 run the standard Brakedown PCS and MF-PCS benchmarks for the given parameters. Scenarios 7–8 run only the MF-PCS benchmark, sweeping the number of fields from 2 to 8.

For each scenario, test_pcs automatically runs all the MF-PCS configurations (field count and master-field type) that the corresponding PIOP scenario requires. Specifically:

Scenarios 1-7 run the Brakedown PCS/zk-PCS benchmark and then execute the MF-PCS configurations required by the matching PIOP scenario:

Scenario	MF-PCS configurations
1 (CKKS CM/MVM)	F=4
2 (CKKS NN)	F=2,3
3 (CKKS LR)	F=2,3,...,8
4 (CKKS CA)	F=3,4,...,9
5 (CKKS CM+NF)	F=2,3
6 (BGV CM/MVM)	F=4, master=coeff; F=4, master=plain; F=2, master=coeff
7 (BGV NN)	F=3, master=coeff; F=3, master=plain; F=2, master=coeff; F=2, master=plain

For CKKS, all primes have the same bit-width, so the choice of master field has negligible impact on performance. For BGV, the plain_modulus (~32-bit) is smaller than the coeff primes (~36/48-bit), so master=coeff and master=plain are benchmarked separately.

The primes and NTT roots used in each scenario are hardcoded to match those generated by SEAL's CoeffModulus::Create() in the corresponding PIOP tests.

(I)NTT PIOP benchmark

We reimplement the non-ZK (I)NTT PIOP of HasteBoots in C++. To compare the concrete efficiency of our non-ZK (I)NTT PIOP with that of HasteBoots, you can run the following command:

../run_ntt_piop_comparison.sh

Note that, we only measure the PIOP layer only.

Reproducing Experimental Results

The end-to-end benchmarks reported in the paper are obtained in two steps, because PRISM separates the PIOP layer from the PCS layer.

Step 1: Run the PIOP for RNS-HE

Execute the desired scenario (e.g., ./test/test_CKKS 1 for CKKS CM). Each run prints:

Output	Meaning
preprocessing time	PIOP preprocessing time (s)
prover time	PIOP prover time (s)
verifier time	PIOP verifier time (s)
proof size	PIOP proof size (KB)
Total #PCS needs to be invoked in preprocessing phase	Number of PCS instances in preprocessing (#PCS_prep)
Total #PCS needs to be invoked in online phase	Number of PCS instances in the online phase (#PCS_online)
Total #MF-PCS needs to be invoked for k fields, master=coeff/plain	Number of MF-PCS instances with k fields and the given master type (BGV only distinguishes coeff vs plain)

These numbers tell you (a) the PIOP-layer performance, and (b) exactly how many PCS / MF-PCS calls the full proof requires.

Step 2: Run the PCS / MF-PCS Benchmarks

Run test_pcs with the scenario number that matches the PIOP test's parameters:

PIOP scenario	PCS command
CKKS CM (test_CKKS[_ZK] 1) or MVM (... 2)	./test/test_pcs 1
CKKS NN (test_CKKS[_ZK] 3)	./test/test_pcs 2
CKKS LR (test_CKKS[_ZK] 4)	./test/test_pcs 3
CKKS CA (test_CKKS[_ZK] 5)	./test/test_pcs 4
CKKS CM+NF (test_CKKS 6)	./test/test_pcs 5
BGV CM (test_BGV[_ZK] 1) or MVM (... 2)	./test/test_pcs 6
BGV NN (test_BGV[_ZK] 3)	./test/test_pcs 7

The same mapping applies to the ZK variants (test_CKKS_ZK, test_BGV_ZK).

Each run of test_pcs benchmarks two components and reports amortized per-polynomial metrics:

• Brakedown PCS (small field): commit time, eval time, verifier time, proof size (and ZK variants)
• MF-PCS: for each required (F, master-field type) combination: prover time (commit + eval), verifier time, proof size (and ZK variants)

Step 3: Combine the Results

The final end-to-end numbers are computed as follows. Let pcs_commit and pcs_eval denote the per-instance PCS commit time and eval time.

Total preprocessing time = PIOP preprocessing time
                         + #PCS_prep × pcs_commit

Total prover time        = PIOP prover time
                         + #PCS_online × (pcs_commit + pcs_eval)
                         + #PCS_prep × pcs_eval
                         + #MF-PCS × per-MF-PCS prover time

Total verifier time      = PIOP verifier time
                         + (#PCS_prep + #PCS_online) × per-PCS verifier time
                         + #MF-PCS × per-MF-PCS verifier time

Total proof size         = PIOP proof size
                         + (#PCS_prep + #PCS_online) × per-PCS proof size
                         + #MF-PCS × per-MF-PCS proof size

The same decomposition applies to the ZK variants (test_CKKS_ZK, test_BGV_ZK), using the ZK PCS / ZK MF-PCS metrics from test_pcs.

Example (CKKS CM, non-ZK):

1. Run ./test/test_CKKS 1 → obtain PIOP metrics and the PCS/MF-PCS counts.
2. Run ./test/test_pcs 1 → obtain per-instance PCS and MF-PCS metrics (same primes).
3. Combine using the formulas above.