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
0
votes
0answers
9 views

Does the error distribution in LWE is 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}, \...
1
vote
1answer
33 views

Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?

Let $\rho_s(x) = e^{-\pi x^2/s^2}$ be the Gaussian measures, then the discrete Gaussian distribution on $\mathbb{Z}$ could be defined as $D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)...
0
votes
0answers
28 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
23 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 ...
1
vote
1answer
32 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
95 views

How is R-LWE related to lattice cryptography and homomorphic encryption?

Can someone tie everything together for me? I'm interested in H.E and I have some background in AES, DES, RSA and the like. While reading around I stumbled on Shai Halevi's course on lattice ...
7
votes
1answer
473 views

Is Ring-LWE now 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 ...
1
vote
2answers
248 views

Why does bootstrapping (R)LWE homomorphic encryption produce small noise?

Why does homomorphic evaluation of the decryption circuit produce a ciphertext with "fresh" or small noise? Rough description of bootstrapping homomorphic encryption: Suppose we have a ...
0
votes
1answer
35 views

Trapdoor committement using ring lattices involving three parties

Assume there are three parties say A, B, C. A commits to a message $m$ say $c(m)$ and sends tuple $(m,c(m))$ to B. B has to prove to C that he possesses commitment $c(m)$. There is no interaction ...
2
votes
0answers
29 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
41 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
48 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
83 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
38 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
50 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
40 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
31 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
35 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
36 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
122 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
118 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 ...
8
votes
1answer
424 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
62 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
202 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
36 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
91 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
162 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
38 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
28 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
34 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
86 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
104 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
215 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
78 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
256 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
201 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
94 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
56 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
76 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
48 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
66 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
77 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
154 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
190 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
193 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 ...