MarbleHE/SoK

Design & implement Benchmarks for libraries

AlexanderViand opened this issue · 5 comments

AlexanderViand commented

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

CKKS

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 commented

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

pjattke commented

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
  • 🎉1
pjattke commented

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 commented

@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 commented

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

  • 👍1