1
$\begingroup$

In the context of lattice-based cryptography, in particular the Learning With Errors (LWE) problem, I see some definitions given in terms of equations modulo 1 (see for example, Appendix A of this paper).

Can someone explain why such modulo is used? It simply doesn't have any sense to me. Any expression modulo 1 is 0, right?

$\endgroup$
  • 5
    $\begingroup$ I think the value is supposed to be fractional, and in that case mod 1 results in a value between 0 and < 1 $\endgroup$ – Richie Frame Dec 4 '14 at 9:43
  • 1
    $\begingroup$ @RichieFrame do you plan on expanding this into an answer? In particular, I'm curious to know the mathematical value of doing modulo 1. Could make a nice answer :) $\endgroup$ – mikeazo Dec 4 '14 at 13:29
  • $\begingroup$ @RichieFrame: Yes, now that you mention it, it seems that this is the case. In particular, this equation is in $\mathbb R / \mathbb Z$. $\endgroup$ – cygnusv Dec 4 '14 at 13:43
3
$\begingroup$

The equations mod 1 are supposed to have solutions that are very close to an integer value, say 3.99 or 4.01, which are reduced to a value very close to 0 (or 1, which is 0 mod 1).

Specifically, they describe a set of samples that equate to the distance from an integer value all within $± {1/n}$ for some large value $n$, and the sum of the sample set is therefore also very close to an integer value, which then makes it approximately congruent to 0, modulo 1. The original paper assumes that it is close enough to 0 to be treated as 0 in their calculations.

I do not know much about lattice cryptography, but it appears the purpose of the equations is to show the behavior of the sample set falls within a predictable set of values, but only for those who know the shared secret, and for those who do not it looks like noise, to quote:

the observation that any set of $n$ (linearly independent) approximate equations essentially give us an approximation of $s$ up to the noise distribution, so by subtracting that approximation from the LWE secret, we obtain an LWE instance whose secret is distributed like the noise distribution

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