1

The key generation algorithm for Ring-LWE is as follows. Have a ring $R_p =Z_p[x]/(x^n + 1)$. Then pick a uniformly random $a$ from $R_p$. Pick $s$ from an appropriate distribution. Pick $e$ from the error distribution (typically a constant-size Gaussian). Compute $b = as + e$. Reveal $(a, b)$ as the public key and $s$ is the secret key.

I've been reading The Homomorphic Encryption Standard. It says that $s$ can be picked as a uniform random element from $R_p$. How is this possible? For instance if the (admittedly insecure) choice $n=1$ was picked, then for any values of $a$, $b$ and $e$ there is some value $s$ which satisfies the equation. More seriously, the LPR scheme, for instance, assumes that $(re - se_1 + e_2)$ is small in order for decryption to be correct. How can it be small if $s$ is chosen uniformly at random from $R_p$?

Daniel-耶稣活着
  • 399
  • 3
  • 11

2 Answers2

1

You're right that essentially all schemes require that the secrets are small in a concrete sense. While I'm not terribly familiar with the standard, I believe the tables in question were generated by the LWE Estimator of Albrecht et al. This page of its documentation states various secret distributions they support. I expect "uniform" corresponds to "bounded uniform", but I'm unsure of which particular bound was used to generate that table.

Mark Schultz-Wu
  • 12,944
  • 19
  • 41
1

Let's first think about the ordinary LWE. There are two ways of choosing the secret, one is that there is no restriction on the secret; Another way is to choose a short secret. Applebaum, Cash, Peikert, Sahai prove that the latter is still sound. In other words, the secret can be chosen uniformly from the polynomial ring or from its bounded distribution, depending on the application. This is true also for Ring-LWE.

Eri
  • 31
  • 3