Design & implement Benchmarks for libraries

[AlexanderViand]

Benchmarking the libraries against each other:

Micro-benchmarks

• Ctxt-Ctxt Multiplication time (incl. relin)
• Ctxt-Ptxt Multiplication time (incl. relin)
• Ctxt-Ctxt Addition time
• Ctxt-Ptxt Addition
• Sk Encryption time
• Pk Encryption Time
• Decryption time
• Rotation (native, i.e. single-key) [Only where applicable]

Libraries to evaluate

BFV/BGV

• [x] SEAL (see 514d4a3cc3beb5a31c5777f029a70683acce5d66)
• [ ] HElib @AlexanderViand
• [x] Palisade (see c5161da3ea7ef9b3f92327712ccf5ec52028a062)

  CKKS

• [ ] SEAL @pjattke
• [ ] HElib @AlexanderViand
• [x] Palisade (see 6fafb908d33ace6b0bf5e376c72ede7a0064078c)

  CGGI

• [ ] TFHE
• [x] Palisade [FHEW] (see abcd2edee519403f319f1d19af6fab4dd3a6ba6e)
• [ ] Concrete

Parameter settings to evaluate

• Plaintext space: t = 1 or t = 2^64
• For levelled schemes: n=16k, 128-bit security, choose q s.t.: 1-level or 10-level

We should fix two plaintext space sizes, e.g. 1-bit (binary) and 64-bit and use that for all benchmarks, just so that we don't blow up the space of possibilities too much. For levelled schemes, we should evaluate with 1-mult params and with e.g. 10 levels.

For binary-only libraries like TFHE, the 64-bit version then uses an adder/mult circuit. In that case, Ctxt-Ptxt optimizations are possible but not implemente which is fine, since this isn't the main core of the paper anyway. For fair comparison among implementations of the same scheme, we should hardcode the parameters to be equal everywhere.

Finally, we could consider implementing the benchmark applications (NN, cardio, Chi-Squared) for each library, but this out of scope for the current timeframe.

[AlexanderViand]

Ideally, we would also benchmark Cingulata's built-in implementation, but that might not be feasible. The same goes for Alchemy.

[pjattke]

Python script for plotting added in 792b09c18a3489a8ccc20ff938c91b952caa972e.

Please use the following column names for the CSV of the measurements:

• t_mul_ct_ct
• t_mul_ct_ct_inplace
• t_mul_ct_pt
• t_mul_ct_pt_inplace
• t_add_ct_ct
• t_add_ct_ct_inplace
• t_add_ct_pt
• t_add_ct_pt_inplace
• t_enc_sk
• t_enc_pk
• t_dec
• t_rot

[pjattke]

Parameters

(✔︎): Parameter configured in current benchmark implementation.

BFV Parameters

Parameter	Value	SEAL	PALISADE	HElib
Plaintext modulus (t/p)	2^64
Security level (λ)	128 bit		✔︎
Cyclotomic Order (n)	2
Ctxt coefficient modulus (q)
RLWE error distribution (ꭓ)	3.2		✔︎

CKKS Parameters

TODO

CGGI Parameters

TODO

[pjattke]

@AlexanderViand It looks like PALISADE does not implement TFHE but FHEW only, although in their README they list both Ducas-Micciancio (FHEW) and Chillotti-Gama-Georgieva-Izabachene (TFHE) schemes for Boolean circuit evaluation. Should I just use FHEW instead?

[AlexanderViand]

Oh, that's interesting! But sure, let's compare it anyway - might be interesting to see if there's a significant difference to TFHE