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

The relationship between root hermite factor and bit-security?

The root hermite factor corresponding to an bit-security level, such as 1.0045 corresponding to 128-bit security. What is the root hermite factor corresponding to 100-bit, 160-bit, 180-bit security? ...
3
votes
0answers
40 views

Is the scheme in LWE also valid in R-LWE?

One way of interpreting matrices in RLWE is that they are a subset of standard integer matrices that have special structure. For example, rather than using a random matrix $A\in\mathbb{Z}_q^{n\times n}...
3
votes
0answers
36 views

parameter estimating in lattice signature scheme

when reading [BDLOP18], I run the lwe-estimator with the recommended parameters in Table 2 , but the result of hermite factor is 1.007, this result is bigger than the recommended hermite factor 1.0035
3
votes
1answer
118 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
45 views

Equivalence between search-LWE and decision-LWE

Are there any constraints when it comes to proving that search-LWE and decision-LWE are equivalent? Should we assume that the module $q$ is prime when switching from one version to another? Please ...
1
vote
0answers
69 views

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$...
1
vote
1answer
49 views

Why RLWE is hard or even has a solution?

I was thinking about why and how the RLWE problem is hard at all. I know that it's hard because it can be reduced to the shortest vector problem, but I'm thinking about how does it even have a ...
3
votes
1answer
82 views

Functional and security model for SEAL

What's the functional and security model for SEAL? From this I get that it allows additions and multiplications to be performed on encrypted integers or real. But what are the limitation, like range,...
1
vote
1answer
49 views

Security level of FHE constructions for non-standard parameters

homomorphicencryption standards already provide recommended parameters and their corresponding security levels. However, I would like to calculate a security level for nonstandard parameter selection. ...
1
vote
1answer
59 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$. ...
11
votes
2answers
717 views

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 ...
0
votes
1answer
77 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!
4
votes
1answer
141 views

Prove that a small Ring-LWE secret is unique

I just want to know whether my proof is correct, which is about proving that if the Ring-LWE secret is small, then it is unique. Before giving my proof, here is a fact: Fact 1: $\Pr [\Vert r \Vert_\...
0
votes
0answers
50 views

Is my proof about uniqueness of ring-LWE secret correct?

Suppose that $n$ is a power of two, $q=3\pmod 8$, prime and $R=\mathbb{Z}[X]/(X^n+1)$. Denote $\Vert\cdot\Vert$ as the infinity norm in $R_q=R/qR$ on the coefficients of elements in $R_q$. The ...
2
votes
1answer
84 views

Proof that (ring-)LWE secret is unique

I read Regev's paper in 2005 about Learning with Errors and he mentioned that the secret of a LWE sample is unique but I have not seen a proof of this claim. Can someone point me to a paper proving ...
0
votes
1answer
60 views

Small modulus to noise ration in LWE implies better security

I don't quite understand why a smaller quotient between modulus $q$ and the noise's standard deviation implies better security against known attacks.
3
votes
1answer
97 views

Why define the dual of an ideal lattice with "Tr" rather than inner product?

In the paper [LPR12], I've learned that ideal lattices are ideals in algebraic number fields. However, I can't understand why we define the dual lattice of an ideal lattice with $\operatorname{Tr}$: $$...
2
votes
1answer
72 views

Parameters in RLWE

Let $n, q, \sigma$ be the polynomial degree($x^n+1$), coefficient modulo, and the standard derivation, respectively. I often see some parameters such as For RLWE, we can use the CRT to decompose the $...
2
votes
1answer
68 views

The error distribution in LWE

$\textbf{Continuous LWE}$ : $(\overrightarrow{a}, b)\in \mathbb{Z}_q^n\times \mathbb{T}$, where $\mathbb{T}=\mathbb{R}/\mathbb{Z}$, $b = \langle \overrightarrow{a},\overrightarrow{s}\rangle/q + e\mod ...
1
vote
0answers
30 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 ...
2
votes
0answers
45 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 ...
0
votes
1answer
82 views

Why is the error in RLWE "smaller" than LWE?

In LWE, the standard deviation satisfies $\alpha p > 2\sqrt{n}$, when we consider the discrete LWE in $\mathbb{Z}_p$, then the rounded Gaussian has standard deviation $\alpha p$. But in RLWE, the ...
0
votes
1answer
82 views

Joint distribution of RLWE samples

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. We draw samples $s_i \gets R_q$ uniformly at random. Additionally, we define the error distribution $\chi$ as a discrete ...
4
votes
2answers
328 views

Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n?

For RLWE (Ring Learning With Errors) scheme, we use $R_{q} = \mathbb{Z}_{q}[x]/(x^{n} +1) = \mathbb{Z}_{q}[x]/(\Phi_{2n}(x))$ where $n = 2^{d}$ for some $d$. Since there exists $2n$-th root of unity ...
2
votes
1answer
45 views

Choosing rings for PLWE

In [ELOS15], the authors give an attack on RLWE, and claim that "the hardness of Ring-LWE is... dependent on special properties of the number field" chosen; whereas, responding to prior ...
0
votes
0answers
132 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}, \...
1
vote
0answers
69 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
43 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 ...
0
votes
0answers
75 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 ...
1
vote
1answer
63 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
42 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
31 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 ...
2
votes
1answer
157 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 ...
1
vote
1answer
431 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 $\...
2
votes
2answers
291 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
39 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
35 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
61 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
67 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
90 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
53 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
53 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
44 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 ...
1
vote
0answers
79 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
165 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
48 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 ...
4
votes
1answer
137 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
470 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
67 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 ...