In my work I am attempting to reduce some of the computational complexity needed with multiplication by using a version of bitshifting. I am wondering if this is possible? Despite reading through the documention and the code, how to actually interact with the FHE Ciphertext is not fully clear given that its format as a Ciphertext; it’s unclear if it’s possible to do some variation of a bitshift, whether it is an actual shift or if it is multiplying by a constant. Any guidance on how this may be implemented would be greatly appreciated.
Hi @cdailey, in OpenFHE, ciphertexts are generally opaque to the application (and user). You can really (should really) only interact with them via methods and function calls in the library.
Can you elaborate on what it is you are trying to achieve?
Are you trying to do bitshifting on the encrypted content? or actually trying to manipulate the ciphertext object?
In BGV-like FHE schemes, a ciphertext is typically a vector of polynomials (in most cases, 2 polynomials). Each polynomial can be viewed as a vector of big integers.
Depending on the FHE scheme used, multiplying a ciphertext by a constant is typically done by first iterating over the polynomials and then iterating over each big integer in the polynomials and multiplying it by the input constant or (a scaled version of it, this depends on the scheme).
Note that big integers might be represented in Residual Numbering System (RNS) making the multiplication a little trickier.
If you could share which scheme you are using, and what you are trying to do in detail, we might be able to help you better.
So what i am attempting to accomplish is transciphering, basically using a lightweight cipher to encrypt ptxt, then encrypt that key and the resulting ctxt homorphically (using BFV), then homorphically decrypting the lightweight in order to be left with just a homorphically encrypted ctxt. To do this, once everything is double encrypted, i would mimic the lightweight ciphers decryption function using homomorphic addition and multiplication along with some form of bitshifting.
I was originally looking at using CoefPacked encoding (though if there is a better way then I am open to suggestions.
The way I was homomorphically encrypting the LWC ctxt was by taking the ctxt vector into a HE plaintext using cc->MakeCoefPackedPlainedtext(ctxt). From there I was encrypting using cc->Encrypt(public_key, he_ptxt).
I am new to this library and working with FHE in general, so my approach may not be the best, or I might be missing some component to make this simpler. I hope this answers your questions.
If the input is encoded as a vector of integers, then multiplication and addition are easy but bit shifting is hard. In this case, in BFV it typically requires bootstrapping (very expensive operation).
If the input is in bits (for example, each coefficient represents a bit), then bit shifting is is not too hard (requires rotations in the worst case), but multiplication is hard (number of bits doubles with each multiplication).
In other words, evaluating the decryption circuit with BFV will be computationally expensive. This is why the community has focused on special ciphers, like PASTA, RASTA, and FASTA (see the other thread for details and references). These ciphers have an FHE-friendly decryption circuit. Using any LWC without considering the complexity of the decryption circuit from the FHE perspective may not be the best approach.
Thanks for the explanation. That definitely clears some things up.
The complexity of the decryption circuit with BFV has been a forefront decision maker in the choices I have been making, which is why I was looking into the bit shifting. I will take a look at PASTA, RASTA, and FASTA along with re-evaluating the LWC I was looking at going forward.
Since we were talking about computational complexity, I am wondering the computational cost/complexity of multiplying by a constant since bit shifting is basically equivalent to it? I know in FHE multiplication is usually more costly, but does that mean overall or just multiplying two ciphertexts together?
Left shifting is multiplying by a constant, but right shifting is dividing by a constant, which typically requires BFV bootstrapping. What specific bit shifting operations are you referring to?
Would it be possible to invert the ciphertext in order to change the right shifts into left shifts? If so then multiplying by a constant should be straightforward?
Depends on the modulus used for LWC. Multiplicative inverse exists only if the input and modulus are coprime. If the modulus is an extension of 2, then the inverse of a multiple of 2 does not exist.
Hi, What is easy/hard with digital circuits, does not always carry over into FHE encrypted computation.
Multiplication by a plaintext constant is cheaper that multiplication by an encrypted constant, but the latter is not much different than multiplication of two encrypted vectors (hadamard multiplication). As Yuriy says, bit shifting in digital ckts is trival, but not in encrypted math. If you look at how AES was implemented in BFV and BGV (see https://eprint.iacr.org/2012/099.pdf), it was not using the typical “hardware optimized” approach (using lookups and shifts which are based on optimization of the underlying math) but rather implemented the underlying math directly. The result is pretty complicated.
Thus, why FHE friendly ciphers are considered.