2
$\begingroup$

So I'm a bit of a cryptography/HE noob, and I was wondering if it is possible to keep track of the noise growth that happens when you do some kind of mathematical operation on your encrypted data, and by keeping track of such growth, would it be possible to clip off the noise once it reaches a threshold (If I've understood correctly, after certain point your decryption process will be useless, because of noise?).

  1. Now by learning that noise growth what else can I gain?
  2. Is it even possible to clip off the unwanted noise and continue with your operation?
$\endgroup$
5
$\begingroup$

You can't know exactly how much noise your ciphertext has because when you encrypt a message, you sample random values that are combined to the message and they also make part of the noise (so, the noise is also random). But you can have good estimations for the magnitude of the noise because all the distributions from where we sample the values are known.

That said, the better you can do to keep track of the noise growth is to use the estimative provided (generally) by the authors of the scheme: in general, for the scheme we are using, we know upper bounds to the noise of a ciphertext that is the result of an operation, that is, we know functions $f$ and $g$ such that

if $noise(c_1) \le n_1$ and $noise(c_2) \le n_2$, then

$noise(c_1 + c_2) \le f(n_1, n_2)$ and $noise(c_1 \cdot c_2) \le g(n_1, n_2)$

(For instance, we could have $f(n_1, n_2) = n_1 + n_2 + 128$ and $g(n_1, n_2) = 128 \cdot n_1 \cdot n_2$).

It is worth noting that those estimations are quite pessimist: for instance, on the paper A Comparison of the Homomorphic Encryption Schemes FV and YASHE, authors say that they could select parameters with size about 30% smaller than expected because the noise growth was always below the theoretical upper bound, as they show in the following figure (which is on the 12th page):

Comparison of noise growth in practice vs expected noise growth.

That difference occurs because the theoretical upper bound uses a kind of "worst-case analysis", considering the biggest noise that can occur, but in practice, that biggest values of noise will occur only with small probability (remember that, in general, we sample those values following a Gaussian, therefore values close to the mean are more likely to occur...)

  1. Is it even possible to clip off the unwanted noise and continue with your operation?

Yes. This is called bootstrapping and it consists in running a "refresh" procedure to remove the noise of the ciphertext. But that is not a simple procedure and can be quite expensive computational-wise.

  1. Now by learning that noise growth what else can I gain?

You can try to reduce the number of times you use the "refresh" procedure removing the noise only when it is needed instead of doing that after each operation.

$\endgroup$
2
$\begingroup$

Great answer, Hilder Vitor Lima Pereira!

An example of estimating the noise of a particular scheme is done in the SEAL library, which implements a variant of the FV cryptosystem. It can be found here: https://sealcrypto.codeplex.com

They implement noise estimation and use it to help non-expert users to select proper parameters to optimize their systems. Worth checking out if you're interested.

You can read more about it here: https://www.microsoft.com/en-us/research/wp-content/uploads/2017/06/sealmanual_v2.2.pdf

$\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.