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

New contributor
kevin is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
4
  • 3
    $\begingroup$ Might insight you crypto.stackexchange.com/q/87501/18298 $\endgroup$
    – kelalaka
    Sep 18 at 10:34
  • $\begingroup$ @kelalaka what are sk and pk respectively in the keygen section ? $\endgroup$
    – kevin
    Sep 18 at 14:44
  • $\begingroup$ sk for the private key, pk for the public key.. $\endgroup$
    – kelalaka
    Sep 18 at 14:45
  • $\begingroup$ @kelalaka May I ask why v-su equals q/2 M + r e ? $\endgroup$
    – kevin
    Sep 20 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$
3
  • $\begingroup$ you did not explain how the choice of α expression is being derived ? $\endgroup$
    – kevin
    2 days ago
  • $\begingroup$ I do not understand your last two sentences of your answer $\endgroup$
    – kevin
    20 hours ago
  • $\begingroup$ What does n^(−1/o(1)) means ? $\endgroup$
    – kevin
    19 hours ago

Your Answer

kevin is a new contributor. Be nice, and check out our Code of Conduct.

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.