3
$\begingroup$

I'm trying to sample HE ciphertexts which serve as ciphertexts encrypting some random values. I have realized a example program using Microsoft SEAL, which implements a variant of BFV scheme. Unfortunately, the ''noise budget'' of these uniformly-distributed ciphertexts is zero and thus they cannot support any further homomorphic evaluation. However, when I draw these ciphertexts from discrete Guassian distribution (with mean = 0), they have non-zero ''noise budget'' and work fine.

I'm quite confused about this result. Since BFV scheme is IND-CPA secure, its valid fresh ciphertexts should be indistinguishable from malformed ones (i.e., drawn from uniform distribution). However, the experiment result shows that a uniformly-distributed ciphertext does not form a valid ciphertext of BFV scheme with overwhelming probability.

Is there something wrong? Many thanks.

$\endgroup$
1
$\begingroup$

Since BFV scheme is IND-CPA secure, its valid fresh ciphertexts should be indistinguishable from malformed ones (i.e., drawn from uniform distribution).

IND-CPA says that someone who doesn't know the secret key cannot distinguish those two distributions.

However, the experiment result shows that a uniformly-distributed ciphertext does not form a valid ciphertext of BFV scheme

You can only check whether a ciphertext is "valid" if you have the secret key. So there is no contradiction.

An analogy is a length-doubling PRG $G: \{0,1\}^n \to \{0,1\}^{2n}$. The output of the PRG is indistinguishable from the uniform distribution over $\{0,1\}^{2n}$. That doesn't mean that most strings in $\{0,1\}^{2n}$ are "valid outputs" of the PRG. In fact, only a negligible fraction ($2^n$ out of $2^{2n}$) of them are.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.