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.

Filter by
Sorted by
Tagged with
2
votes
0answers
33 views

Why should the smudge noise be used?

Consider a threshold FHE scheme based on RLWE like this: Refer to this paper $\textbf{Initialization:}$ Every party generates his own secret key $s_i$, then uses the common polynomial $a$ to generate ...
4
votes
3answers
66 views

Is it secure to compute the exponentiation and the LWE operation?

Suppose Alice and Bob have specified an elliptic curve, for example, secp256k1. Alice has a secret number $s$ (can be seen as secret key), Bob choose a point $g$ on the curve and send it to Alice. ...
0
votes
0answers
34 views

FHE Bootstrapping in FV12

I am trying to understand the bootstrapping step in FV12 cipher to obtain the FHE. I know the basic idea of bootstrapping is to homomorphic calculate decryption on ciphertext to obtain new equivalent ...
1
vote
1answer
38 views

How small can the error be in LWE?

For modulus $Q$ and stddev $\sigma$, [GHS12] suggests that, to achieve 128-bit security, just choose the dimension $N$: $$ N\geq(Q/\sigma)\cdot 33.1 $$ This seems to suggest flexibility to choose ...
0
votes
0answers
38 views

Why is the proof on the commitment correct?

In the paper "Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings", they gave a commitment from Ring-LWE: to commit to a polynomial $m$ in $Rq(Zq[x]/(x^n+1))$...
0
votes
0answers
27 views

GSW and homomorphic addition on integers

Is it possible to use the GSW scheme (Gentry, Sahai, Waters) also on integer values and not just single bits? If not, are there any schemes that support integer arithmetic with the same nice property ...
0
votes
0answers
17 views

Module LWE with an even modulus

Does module-LWE remains hard for an even modulus $q$, or a power of two? This is true for Ring-LWE (pseudorandomness) and Module-LWR (SABER). I can't find any reference to it!
1
vote
0answers
29 views

CRT decomposition in NTT for BFV

AS explained in section 4.5, decomposition for relinearization (2nd step of ciphertext multiplication in bfv) can be done using RNS components of ciphertext. In other words, they proposed a way to do ...
5
votes
1answer
110 views

What is the difference between Poly-LWE and Ring-LWE?

I am often confused by Poly-LWE and Ring-LWE, always thinking that they are different names for the same thing. In some literature, Poly-LWE is a simplified version of Ring-LWE? What is the difference?...
2
votes
1answer
36 views

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 ...
3
votes
1answer
109 views

Famous ideal lattices

I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ... In more ...
7
votes
1answer
409 views

NewHope and NIST's Post-quantum standardization

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules. Is being a ring-based KEM ...
3
votes
1answer
58 views

Replay attacks and LWE

Just a small question. Since in LWE the error is rather small, is there a problem with replay attacks? What I mean is that if we use the typical scheme of Regev [1] to encrypt a vector m, but this ...
5
votes
2answers
177 views

MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
1
vote
1answer
32 views

Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
1
vote
0answers
76 views

What are the prerequisites for understanding Lattice based Cryptography, LWE or RLWE based on SVP?

I'm new to Quantum Resistant Cryptography, so, I thought of diving into Lattice based crypto, LWE and ring LWE. I realise that the hard problem involving them is the "shortest vector problem"...
3
votes
2answers
125 views

Ring-LWE in other fields

Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$? Can we use another fields without losing in hardness of the ...
0
votes
0answers
37 views

Binomial distribution sampling - concrete example

Can anyone give me an explicit example of how one can samples from the binomial distribution defined in NewHope's paper? What is the difference of sampling from rounded Gaussian in practice?
1
vote
0answers
25 views

Difference between polynomial embedding and canonical embedding

Can anyone tell me the difference between working in the polynomial embedding for $R$-LWE, and working in the canonical embedding?
1
vote
0answers
33 views

Forging a new secret key in RLWE

In a RLWE setting where you are given a secret key $s$ and an associated public key $pk = (p_0,p_1) = (-(p_1s+e),p_1)$, is it possible/easy to forge a new secret key $s'$ such that $p_0+p_1s'$ has a ...
0
votes
0answers
25 views

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 ...
1
vote
2answers
82 views

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 ...
0
votes
1answer
99 views

Trying to Understand Ring Learning With Error Encryption

I'm trying to understand the following RLWE encryption scheme from this Chris Peikert's paper Say i choose $q = 97$, $n=8$ and the polynomial $a = 96 x^8+30 x^7+76 x^6+12 x^5+57 x^4+77 x^3+70 x^2+49 ...
4
votes
2answers
205 views

what does output parameters of lwe estimator stands for?

I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on lwe estimator given bellow. ...
2
votes
1answer
74 views

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 ...
2
votes
1answer
214 views

Threshold decryption in multi-key homomorphic encryption

I have a problem understanding the security of threshold decryption in multi-key homomorphic encryption (MKHE) with so called "noise flooding". In particular I think that it is not secure, so probably ...
1
vote
1answer
190 views

Fully Homomorphic Encryption - state of the art

What are the latest advances in fully homomorphic encryption? First of all, I am interested in cryptosystems based on LWE / RLWE and NTRU problems.
2
votes
1answer
90 views

Does the relationship between plaintext and ciphertext moduli affect the security of BGV/BV SwHE?

The SwHE schemes due to Brakerski and Vaikuntanathan (BV) and Brakerski-Gentry-Vaikuntanathan (BGV) have common concept in which the message bit is put in the least significant bit of the ciphertext. ...
1
vote
0answers
53 views

How many ring-LWE samples are required for the (Search) Ring Learning With Errors problem to have a unique solution?

Consider the LWE distribution $\{(\pmb{a}_{i},\left<\pmb{a}_{i} , \pmb{s}\right> + e_{i})\}$ where secret $\pmb{s} \in \mathbb{Z}_{q}^{n}$, randomness is $\pmb{a}_{i} \xleftarrow{\$} \mathbb{Z}_{...
1
vote
1answer
66 views

Choices of $q$ and $f$ for RLWE-based constructions

I understand that RLWE was introduced to avoid the quadratic overhead in the matrices that appear in plain LWE. However, I have a series of questions about this setting. First, Ring-LWE-based ...
2
votes
1answer
47 views

Reference for the Security Analysis of Ring-LWE

Can someone please share a link of any research paper or web-page analyzing the security of Ring-LWE? Essentially, how should I choose my parameters to get security equivalent to 128-bit or 256-bit?
2
votes
0answers
63 views

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 "...
1
vote
1answer
75 views

How are precision and security related in a Gaussian Noise Sampler for R-LWE?

My understanding is that the sampling precision in Gaussian Noise sampler is related to security. But not sure about why is that? I read that when the samples are floating-point numbers and precision ...
1
vote
0answers
145 views

How to solve a simple case of a RLWE problem

I've been reading up on the Ring Learning with Errors problem and the proposed attacks, in relation to homomorphic encryption. Some of the literature has been quite difficult to understand - what I ...
1
vote
0answers
176 views

Canonical embedding vs. plaintext slots in Ring-LWE

I'm working on the canonical embedding mentioned in [LPR10] and [LPR13]. What confuses me is that the difference and the relationship between the canonical embedding and the concept of ''plaintext ...
2
votes
1answer
61 views

Calculation of failure probability in basic Ring-LWE-DH key agreement

This is the basic unauthenticated Ring-LWE-based Diffie-Hellman key exchange, based on Peikert's Ring-LWE KEM: (from BCNS15) Alice and Bob have shared public polynomial $a$ randomly drawn from $R_q = ...
4
votes
1answer
192 views

Complete Attack on RLWE Key Exchange with reused keys, without signal leakage

I am studying a research paper "Complete Attack on RLWE Key Exchange with reused keys, without signal leakage" . On page number 21 to 28, there is toy example explaining the scheme. I am unable to ...
1
vote
0answers
31 views

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 ...
1
vote
0answers
63 views

How does the polynomial module impact the security of ring/lattices-based SIS problem?

Consider the following SIS problem: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $(R_q)^{r \times n}$=$\left(\mathbb{Z}_q[X]/(X^N+1)\right)^{r \times n}$ and $q$ a ...
1
vote
0answers
57 views

Probability of an RLWE sample

Let $R_q=\mathbb{Z}_q[x]/(x^n+1)$ as usual in the RLWE assumption. Suppoes that I choose a sample of the RLWE distribution, that is, I compute $(a,y=as+e)$ where $a$ is uniform in $R_q$ and $s,e\...
2
votes
0answers
154 views

Comparison of NTRU-based schemes and LWE-based schemes

What advantages and disadvantages can be distinguished in NTRU-based and LWE-based schemes relative to each other? In what cases which scheme gives advantage? UPD: I'm interesting in two things: 1)...
0
votes
1answer
130 views

Refreshing Procedure in FHEW: membership test

I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure. Especially, they ...
4
votes
1answer
168 views

Minimum distance between polynomials in ring-LWE

Let $R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle$ where $f(x)=x^n+1$, as in the ring-LWE problem. Let $a(x)$ be chosen uniformly at random from $R_q$. Question: Is there any theorem that lower bounds ...
4
votes
1answer
199 views

Adapting LWE Trapdoors for Ring-LWE

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE. Theorem 5.1: There is an ...
1
vote
0answers
52 views

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 $\...
1
vote
0answers
101 views

Effitiently sampling the error (noise) distribution in ring-LWE

In LPR12, page 4 is described a ring-LWE encryption in which we are working in a ring $R = \mathbb{Z}[x]/(x^n + 1)$ for a $n$ a power of 2. The public key is of the form $(a, b= a\cdot s + e)$ where $...
3
votes
1answer
200 views

What is the purpose of decomposing ciphertext into digits during relinearization in Brakerski Vaikuntanathan homomorphic encryption?

In Brakerski and Vaikuntanathan's homomorphic encryption scheme, the relinearization function turns a 3-element cipher back to a 2-element cipher by using a set of public homomorphism keys (https://...
0
votes
0answers
71 views

Discrete Gaussian Sampling in Authenticated key exchange from ideal lattices

I am implementing the key exchange scheme proposed by zhang et al. on Sage. In the implementation of the scheme, they have used the two distributions $\chi_{\alpha}, \chi_{\beta}$. How to choose $\...
2
votes
0answers
53 views

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)?...
1
vote
1answer
309 views

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