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

• SEAL (see 514d4a3)
• HElib @AlexanderViand
• Palisade (see c5161da)

CKKS

• SEAL @pjattke
• HElib @AlexanderViand
• Palisade (see 6fafb90)

CGGI

• TFHE
• Palisade [FHEW] (see abcd2ed)
• 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 792b09c.

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