Values generated in BFV parameter generation

Library Questions
1

I was curious about values generated in function ParamsGenBFVRNS linked here.

To be specific,

  1. What’s assurance measure?
  2. What’s Bound of gaussian error polynomial. I understand error polynomial is sampled from gaussian dist, but what role does its bound play ?
  3. How are formulas for delta, Vnorm, nRLWE, noiseKS derived?
2

Although a Gaussian distribution is not bounded by nature, the probability for a Gaussian coefficient to be larger than Berr = 6σerr, is less than 2−30, therefore the two distributions are very close in practice. UQ denotes the uniform distribution over RQ, where every coefficient of a is sampled uniformly and independently from ZQ

Above is from page 5 of 2021/204 (last line in background of Section). Is this the reason why alpha in BFV set to 36?

3

Let me try to answer for each parameter.

  1. delta = 2 \sqrt{N}. See background in https://eprint.iacr.org/2021/204.pdf. It is often referred to in literature, e.g., in the FV paper, as the expansion factor.
  2. Vnorm is the fresh ciphertext noise (becomes smaller if we call modulus switching before first multiplication). See beginning of Section 3.1 in the same paper.
  3. nRLWE finds secure ring dimension for a given \log Q
  4. noiseKS - key switching noise; described in the same paper.
  5. assurance measure is the coefficient used for setting the bound for Gaussians in estimating the noise, i.e., 6 standard deviations. Your later comment is correct.
1 Like