Multiplicative Depth and Bootstrapping

Library Questions
1

Hello.

I had a question about multiplicative depth for CKKS with FHEW scheme switching for comparison operations and bootstrapping.

First my understanding of multiplicative depth is how many consecutive multiplies of the same level you can do, until you reach the depth level, in which case the noise budget has been reached. Once this happens, you must perform bootstrapping or you are stuck with levelled FHE.

How does a FHEW scheme switch operation (such as comparison) affect this initial CKKS multiplicative depth budget (since this also bootstraps)?

Also if I scheme switch to FHEW and bootstrap, how would this change the multiplicative depth budget once switching back to CKKS?

Thanks.

2

Please read openfhe-development/src/pke/examples/SCHEME_SWITCHING_CAPABILITY.md at main · openfheorg/openfhe-development · GitHub and the examples in openfhe-development/src/pke/examples/scheme-switching.cpp at main · openfheorg/openfhe-development · GitHub for more details.

  • When the noise budget is reached you have to perform bootstrapping otherwise the results are incorrect. So it’s not that you are stuck with leveled FHE, but you can’t do further multiplicative operations without bootstrapping.
  • You always have to set the multiplicative depth in CKKS from the beginning, so you need to know in advance the operations you are doing.
  • If you switch from CKKS to FHEW, there is no “full bootstrapping”: you change the encoding (in OpenFHE is done via a linear transform), do modulus switch and key switch, so the multiplication depth required in CKKS is small. If you remain in FHEW and the bootstrap that you do is in FHEW, there is no extra depth required in CKKS.
  • If you switch from FHEW to CKKS, you need to do an operation similar to bootstrapping (without the initial encoding change, but with a multiplication of the encryption of the secret key), so the multiplication depth required in CKKS has to be large enough to support this (12 or 13).
  • If you do a switch from CKKS to FHEW and back to CKKS, and also do multiplications in CKKS (for example this is done in comparison), you need to account for the multiplicative depth of the scheme switch as showed above, as well as the multiplicative depth of the operations you do in CKKS.
1 Like
3

Thank you for the quick and detailed reply.

Just to confirm, when doing doing a CKKS->FHEW->CKKS operation, such as EvalCompareSchemeSwitching, this is breakdown of the depth requirements:

  1. switch from CKKS to FHEW: small multiplication depth required, 1 will suffice?
  2. comparison operation happens in FHEW and does not affect the multiplication depth
  3. when switching back from FHEW to CKKS, need to do a operation similar to bootstrapping, which requires a depth of 12 to 13.
    So in total the Comparison should require a depth of 13?

One more question about the computation cost/runtime of scheme switching.
Since CKKS to FHEW requires a low depth, is this a relatively lightweight procedure and comparable to a CKKS mult?
From FHEW to CKKS, you mentioned you have to do operations similar to boostrapping, is this runtime cost comparable to CKKS boostrapping or is it significantly less?

Thanks again.

4

Comparison should require a depth of 13, but if you want to do some more multiplications over the CKKS result of the comparison, you need to increase the multiplicative depth. You can print the number of levels consumed via cResult->GetLevel() and cResult->GetNoiseScaleDeg().

CKKS to FHEW involves a plaintext matrix-encrypted vector multiplication, so it is definitely more expensive than a single CKKS multiplication. The FHEW to CKKS is similar to bootstrapping, but it is not apples-to-apples comparions: the hom. encoding and hom. decoding steps in bootstrapping are replaced by a different-sized linear transform that does (encrypted) partial decryption, but while the former transformations can also be run via collapsed FFT, the latter is only implemented as a linear transform (gets very expensive when switching a large number of slots).

1 Like