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.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
82 views

Decision R-LWE parameters for spherical error with worst-case hardness

In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
5
votes
0answers
322 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
3
votes
0answers
216 views

Is the ring learning with errors problem still hard if the errors are drawn from some subspace?

Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear ...
2
votes
0answers
43 views

RLWE like problem

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. Let $s \gets R_q$ be a ...
2
votes
0answers
32 views

Why could the error term be sampled coefficient wise?

In SEAL homomorphic encryption library, it implements the BFV and CKKS. We know the error $e\in R_q$ which is a Guassian distribution. When sampling an error term $e = \sum_{i=0}^{n-1} e_ix^i$, it ...
2
votes
0answers
49 views

How does the rejection sampling lemma work in the proof of HVZK?

In this protocol, Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$? Q2: How does the rejection sampling lemma work? refer to ...
2
votes
0answers
56 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 ...
2
votes
0answers
72 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 "...
2
votes
0answers
177 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)...
2
votes
0answers
55 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
0answers
24 views

composition of RLWE distributions

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. Let $s,t \in R_q$ be ...
1
vote
0answers
47 views

Choosing the parameters $n$ and $q$ in RLWE cryptography

The usual RLWE cryptographic constructions that I have read uses the parameters $n$ to be a power of two and $q$ a prime such that $q\equiv 1 \mod (2n)$. Do I understand it correctly that the reason ...
1
vote
0answers
26 views

Secret key generation in the BGV scheme in HElib

This question is about secret key generation, based on section 4.7 in the design document: https://homenc.github.io/HElib/documentation/Design_Document/HElib-design.pdf It seems that if $m$ is not a ...
1
vote
1answer
43 views

What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus?

For $c\equiv a \pmod n$, in Barrett Reduction, $\mu = \lfloor{\frac{2^{2k}}{n} \rfloor}$ is precomputed, where $k = \lceil{\log_2{n}} \rceil$ and the bitlength of $a$ is assumed to be less than $2k$. ...
1
vote
1answer
66 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 ...
1
vote
0answers
43 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 ...
1
vote
0answers
104 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"...
1
vote
0answers
31 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
37 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 ...
1
vote
0answers
74 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
0answers
169 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
202 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 ...
1
vote
0answers
32 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
66 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
65 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\...
1
vote
0answers
55 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
109 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 $...
0
votes
0answers
51 views

Why doesn't HElib support floating point operations?

NB: what I meant is with implementation of the BGV-cryptosystem, not the CKKS cryptosystem which is designed with floating point arithmetic in mind. HElib as I understand it only supports fixed-point ...
0
votes
0answers
56 views

Is the error distribution in Learning with Errors (LWE), the discrete Gaussian distribution?

In $\mathbb{Z}$, the discrete Gaussian distribution is defined as $D_{Z,s}(x) = \frac{\rho_s(x)}{\rho_s(\mathbb{Z})}, x\in \mathbb{Z}$. In LWE, $(\overrightarrow{a}, b = \langle \overrightarrow{a}, \...
0
votes
0answers
33 views

How to fix the IND-CPA+ problem in CKKS?

In paper On the Security of Homomorphic Encryption on Approximate Numbers the author gave an attack on CKKS, then how to fix it?
0
votes
0answers
27 views

What distribution is required to ensure the security of the RLWE?

In LWE, the error should be sampled from a discrete Gaussian distribution. Then, in RLWE, the error is a polynomial in $\mathbb{Z}_q[x]/(x^N+1)$, it could be sampled coefficient wise. However, when we ...
0
votes
0answers
42 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 ...
0
votes
0answers
46 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
36 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
1answer
55 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!
0
votes
0answers
40 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?
0
votes
0answers
26 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 ...
0
votes
0answers
73 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 $\...
0
votes
0answers
56 views

Implementation of Post-quantum Authenticated Key Exchange from Ideal Lattices

I am implementing the Authenticated Key Exchange from Ideal Lattices on sage maths. On page number 3 the full key exchange scheme is presented. In this key exchange scheme, they are using the Hash ...