8
$\begingroup$

Background

I'm trying to make sense of the error in implementations of LWE and R-LWE. In LWE and R-LWE error is added to vectors in lattices to make it computationally infeasible to recover any meaningful data.

It was said here that using float operations in PRNG's aren't reliable enough across different environments.

According to the accepted answer on this question though, it's possible to "trivially" generate cryptographically secure, nearly uniform distributions of floating point decimals.

Questions

  1. Does the error used in LWE or R-LWE rely primarily on float operations?
  2. Do float operations need to be in a finite field to be secure?
  3. Before rounding occurs, are all numbers floating decimals?

Conjectures

My assumption is that Case 1 may be likely, but Case 2 is true. This leads me to believe that only error terms are treated as floating point decimals as a way to maintain efficiency and security, but taking everything either modulo a number or modulo an ideal generates an integer. So in effect, the error taken modulo a number produces a lattice point (integer), or error taken modulo an ideal produces a lattice (finite field).

Is this an accurate assessment?

$\endgroup$
  • $\begingroup$ Sampling a uniformly distributed number in the range $[0,1)$ is different from building a CSPRNG that is built on floating point operations. Being able to do the former does not imply the latter. $\endgroup$ – puzzlepalace May 3 '17 at 0:13
  • $\begingroup$ This is one part of my question, yes. The rest of the question focuses on the specific operations an implementation of LWE or R-LWE requires in order to introduce error securely. $\endgroup$ – nonce May 3 '17 at 0:26
  • 1
    $\begingroup$ As far as I know there isn't any floating points involved in either LWE or Ring-LWE errors. The error vector is an element in Z_q^n or Z_q[x]/(x^n+1), which has small coefficients (compared to q) when lifted to the integers. $\endgroup$ – zhenfei zhang Jun 2 '17 at 18:07
  • 1
    $\begingroup$ @zhenfeizhang: Well, the construct (r)LWE, as used within cryptography, doesn't involve any floating point values being exchanged. However, we still have the possibility of whether constructing the 'discrete gaussian' error vectors could be done faster by using floating point internally. I personally suspect not, but the answer isn't obvious... $\endgroup$ – poncho Jun 2 '17 at 18:33
  • 1
    $\begingroup$ No, it's not obvious; in addition, performance questions like this would generally depend on the CPU architecture. $\endgroup$ – poncho Jun 3 '17 at 19:12
2
$\begingroup$

Answering point 3, no. Rounding a floating point number just leads to a floating point number. It just has less significant digits. So they're still represented as a significand and exponent. This is a widely accepted format these days. An integer is a totally different storage method that does not lead to accumulated errors. They're 100% precise. The uniform distribution problem is exacerbated by the gargantuan 24 orders of magnitude variance in precision of floating point numbers as:-

precision variance

Further arithmetic operations on a rounded floating point number will still accrue rounding errors in difficult to predict ways. And different languages have different types of numbers. For example Java has different types of numbers compared to Perl, and those are different to C /C++. This contributes to the difficulty of native random floating point number generators.

It's typical to cast a number from one kind to another if you want to change type.

$\endgroup$
  • $\begingroup$ Can you address the remaining issues raised in the question? I understand your answer in the context of float operations and integers, but the main question is how these impact lattice cryptography dealing with error. $\endgroup$ – nonce May 3 '17 at 15:35
  • $\begingroup$ And when you use the term "rounding" do you mean the cross-rounding function used in R-LWE? $\endgroup$ – nonce May 3 '17 at 15:39
  • $\begingroup$ At PQCrypto 2017 Peter Schwab mentioned in passing that they used double-precision...couldn't catch if it was in assembly or not... videos.2017.pqcrypto.org/school Peter Schwabe: "Implementation of post-quantum cryptography" 41:10 in. $\endgroup$ – nonce Jun 2 '18 at 1:49

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.