1
$\begingroup$

For https://asecuritysite.com/public/lwe_ring.pdf#page=9 , could anyone explain how the encryption and decryption for LWE work ?

When I do more reading on https://summerschool-croatia.cs.ru.nl/2015/Lattice-based%20crypto.pdf#page=29 , someone told me that when decrypting we get $q/2 M + r e$. If we can bound $r e$ by $q/4$ then we can retrieve $M$ by checking if this is closer to $0$ or $q/2$. May I ask how bounding $r e$ by $q/4$ helps?

On page 33 of a similar document, what is the purpose of the assumption on α ? and how to derive the expressions for this assumption and its corresponding probability?

LWE

$\endgroup$
4
  • 3
    $\begingroup$ Might insight you crypto.stackexchange.com/q/87501/18298 $\endgroup$
    – kelalaka
    Commented Sep 18, 2022 at 10:34
  • $\begingroup$ @kelalaka what are sk and pk respectively in the keygen section ? $\endgroup$
    – kevin
    Commented Sep 18, 2022 at 14:44
  • $\begingroup$ sk for the private key, pk for the public key.. $\endgroup$
    – kelalaka
    Commented Sep 18, 2022 at 14:45
  • $\begingroup$ @kelalaka May I ask why v-su equals q/2 M + r e ? $\endgroup$
    – kevin
    Commented Sep 20, 2022 at 15:39

1 Answer 1

3
$\begingroup$

Someone told me that when decrypting we get $qM/2 + r e$. If we can bound $r e$ by $q/4$ then we can retrieve $M$ by checking if this is closer to 0 or $q/2$. May I ask how bounding $r e$ by $q/4$ helps ?

In this case, $M$ is either $0$ or $1$ and what we actually receive on decrypting is a value $d=qM/2+re\mod q$. Suppose for example that $q=10,000$, then

  • $qM/2$ will be either 0 (corresponding to $M=0$) or
  • It will be 5000 (corresponding to $M=1$).

If we can be sure that $|re|\le 2499$ then

  • in the case $M=1$ our decryption can only lie in $[2501,7499]$ and
  • in the case $M=0$ our can only lie in the ranges $[0,2499]$ and $[7501,9999]$.

These ranges do not overlap and so recovery of $M$ is unambiguous.

On page 33 of the similar document, what is the purpose of the assumption on $\alpha$? and how to derive the expressions for this assumption and its corresponding probability?

In these slides, $\alpha$ is chosen to be the standard deviation of the discretised Gaussian from which the coefficients of $\mathbf e$ are sampled. Likewise, coefficients of $\mathbf r$ are taken to be either 0 or 1 based on independent coin-flips. This means that the value $\mathbf r\cdot\mathbf e$ is the sum of approximately $m/2$ discrete Gaussian samples, each with standard deviation $\alpha q$ and so we expect this value to be distributed roughly Gaussian with standard deviation $\sqrt{m/2}\alpha q$. By the choice $\alpha=o(1/\sqrt m\log n)$, the standard deviation of $\mathbf r\cdot\mathbf e$ will be $o(q/\sqrt{\log n})$ and so the chance of observing a value of absolute value greater than $q/4$ will be bounded by the chance of observing a Gaussian outside of $\sqrt{\log n}/o(1)$-standard deviations. Standard tail estimates for the Gaussian distribution then apply to give the bound $n^{-1/o(1)}$ on the probability of such an event.

$\endgroup$
9
  • $\begingroup$ you did not explain how the choice of α expression is being derived ? $\endgroup$
    – kevin
    Commented Sep 22, 2022 at 17:13
  • $\begingroup$ I do not understand your last two sentences of your answer $\endgroup$
    – kevin
    Commented Sep 24, 2022 at 2:02
  • $\begingroup$ What does n^(−1/o(1)) means ? $\endgroup$
    – kevin
    Commented Sep 24, 2022 at 3:03
  • 1
    $\begingroup$ @kevin for $\alpha$, practically everyone uses the lattice estimator. Increasing $\alpha$ yields better security, but can make protocols less efficient, so there's a tradeoff. $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 29, 2022 at 23:26
  • $\begingroup$ Regarding the last two sentences, it's a (brief summary of) a theoretical (probabilistic) calculation underlying precisely how high we can set $\alpha$ without it making decryption start failing. If we set $\alpha$ too high, we both get "more security", and incorrect constructions (unless we also raise $q$, making things less efficient). $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 29, 2022 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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