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?

Improve this question
$\endgroup$
9
  • $\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, 2017 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$
    – floor cat
    May 3, 2017 at 0:26
  • 3
    $\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, 2017 at 18:07
  • 2
    $\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, 2017 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, 2017 at 19:12

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$
3
  • $\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$
    – floor cat
    May 3, 2017 at 15:35
  • $\begingroup$ And when you use the term "rounding" do you mean the cross-rounding function used in R-LWE? $\endgroup$
    – floor cat
    May 3, 2017 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$
    – floor cat
    Jun 2, 2018 at 1:49

Your Answer

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

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