Cryptography Stack Exchange
Cryptography Stack Exchange

Questions tagged [ring-lwe]

Ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption.

RLWE is more properly called Learning with Errors over Rings and is simply the larger learning with errors (LWE) problem specialized to polynomial rings over finite fields. Because of the presumed difficulty of solving the RLWE problem even on a quantum computer, RLWE based cryptography may form the fundamental base for public-key cryptography in the future just as the integer factorization and discrete logarithm problem have served as the base for public key cryptography since the early 1980s. An important feature of basing cryptography on the ring learning with errors problem is the fact that the solution to the RLWE problem may be reducible to the NP-hard shortest vector problem (SVP) in a lattice.

(source: Wikipedia)

154 questions
12
votes
2 answers

Is Ring-LWE now (2021) broken?

A recent (29 Mar 2021) article "Ring-LWE over two-to-power cyclotomics is not hard" by Hao Chen is available in pre-print here: https://eprint.iacr.org/2021/418 I'm not a cryptographer. Does this article mean that Ring-LWE is unsuitable for…
A. Hersean
  • 934
  • 10
  • 21
3
votes
1 answer

RLWE decision to search: probability that oracle work on all automorphic images

After watching this talk https://www.youtube.com/watch?v=Eg_pyyeT_Qc&feature=plcp, I tried to formalize the presented search-to-decision reduction for Ring LWE, but got stuck at one point. I understand how we can construct an algorithm that finds…
Feanor
  • 133
  • 3
2
votes
1 answer

Distortion of the spherical gaussian error through the canonical embedding in Ring - LWE

In the paper, "On Error Distributions in Ring-based LWE" by Castryck, Iliashenko and Vercauteren, page 3, It is shown that the distrotion to the spherical gaussian in Ring - LWE is caused by the inverse of the vandermonde matrix and the matrix of…
Alcedias
  • 23
  • 2
2
votes
0 answers

What is optimal error distribution in Ring-LWE?

I am new to Ring-LWE. I had assumed that error distribution in Ring-LWE (or, in any lattice-based cryptography) is always Gaussian. However, while reading a few research papers (e.g. page 5, Section "Noise distribution and reconciliation" in…
Niranjan
  • 43
  • 4
2
votes
0 answers

What is the intuition of attacks on ring lwe?

I know that there are several attacks on ring lwe. But I am not sure why they work. Does anyone have intuition of such attacks? What is the common idea used? Reducing the Search space (modulus space)? I want to know them.
mallea
  • 1,605
  • 1
  • 9
  • 21
2
votes
1 answer

$\ell_2$-norm vs canonical embedding norm on ring-lwe

Ring-LWE based encryption (I pick up homomorphic encryption here) requires canonical embedding norm rather than $\ell_2$ norm to quantify the polynomial size (e.g. noise). Why is this better than $\ell_2$ norm? Isn't $\ell_2$ norm always be…
mallea
  • 1,605
  • 1
  • 9
  • 21
1
vote
0 answers

Ring-LWE definition

I'm trying to understand the structure of Rings used in Ring-LWE based on Chris Peikert's Decade of Lattice Based Cryptography paper. The paper says that $$R := \mathbb{Z}[x]\big /\langle f(x) \rangle$$ and clearly for this to make sense, $f(x) \in…
Suman Thakur
  • 11
  • 1
1
vote
1 answer

How is the Chinese remainder theorem used in this proof？

Can you explain it in detail ?
Bob
  • 509
  • 2
  • 8
1
vote
2 answers

Ring LWE: How can the secret be chosen from the "uniform distribution"?

The key generation algorithm for Ring-LWE is as follows. Have a ring $R_p =Z_p[x]/(x^n + 1)$. Then pick a uniformly random $a$ from $R_p$. Pick $s$ from an appropriate distribution. Pick $e$ from the error distribution (typically a constant-size…
Daniel-耶稣活着
  • 399
  • 3
  • 11
1
vote
0 answers

Computational benefits of using exponent as a power of 2 in Ring-LWE

In most of the RLWE based cryptosystems, the parameter $n$, which defines the cyclotomic polynomial $\Phi_{n}(X)$, is chosen to be a power of $2$. Apart from other benefits such as ease of writing proofs and simplicity, are there any significant…
AdveRSAry
  • 624
  • 3
  • 14
1
vote
0 answers

Security of ring-lwe sample? can we do it simpler?

Assuming a secret key $s\in \mathbb{Z}_2[X]/\langle X^n+1\rangle$, a plaintext $m\in \mathbb{Z}_2[X]/\langle X^n+1\rangle$, $e,e'$ are sampled from B-bounded Discrete Gaussian Distribution over $\mathbb{Z}[X]/\langle X^n+1 \rangle $ with reasonable…
mallea
  • 1,605
  • 1
  • 9
  • 21
1
vote
1 answer

sampling ring polynomials in ring learning with errors - what's the trick?

I'm trying to digest the "new hope" paper on post-quanum key exchange and understanding parts of Ring Learning with Errors, despite using every online resource I can find (including the references of 1). I'm sure regular Learning with Errors made…
WillowFinch
  • 11
  • 1
0
votes
0 answers

Ring-LWE instance with errors also in the public polynomial

Consider the ring $R_q = \mathbb{Z}_q[X]/(X^d+1)$, the Ring-Learning-With-Error assumption states that the distribution of $(a, as + e)$ is close to uniformly random, where $s \in R_q$, $a$ is uniform in $R_q$ and $e$ has small norm (say…
Eri
  • 31
  • 3
0
votes
1 answer

FFT multiplication for RLWE key exchange

I am try to multiply two polynomial quotient ring of type $R=Z[x]/\phi(x) $ in sage using Fast Fourier Transform.: a=Rq.random_element() R. = PolynomialRing(GF(40961)) # Gaussian field of integers Y. = R.quotient(X^(dimension) + 1) #…
vivek
  • 197
  • 3
  • 13