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
1 answer
38 views

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 ...
user avatar
1 vote
0 answers
14 views

SIMD mode for RGSW encryption?

I know schemes like BFV, BGV, and CKKS supports SIMD operations where the plaintext is vector of values instead of polynomial. I am wondering if RGSW/TFHE kind of schemes can also support SIMD ...
user avatar
  • 229
0 votes
1 answer
39 views

How to hide result of FHE?

Lets say we are given BFV encryption of x, let this encryption is represented as E(x). In FHE, the client can decrypt and get ...
user avatar
  • 229
1 vote
2 answers
97 views

LWE with a binary matrix A

In LWE, we know that given reasonable public parameter $A\in \mathbb{Z}_q^{n\times \lambda}$, secret $s\in \mathbb{Z}_q^{\lambda}$ and noise $e\in \mathcal{X}^{n}$, random $r\in \mathbb{Z}_q^{n}$, $(A,...
user avatar
3 votes
1 answer
61 views

How to solve LWE/RLWE under partial information about $s$

For LWE/RLWE, it's difficult to find $s$ from $\left(A, b = As + e\right)$. But if the partial information of $s$ is leakaged, such as partial $s$ or parity of $s$, how easy would it become to solve ...
user avatar
1 vote
0 answers
45 views

Where there is special Modulus in Microsoft Seal?

As explained in their example here, Microsoft Seal uses a special modulus that is used for all key material like relinearization key. I wanted to ask why special modulus is used?
user avatar
  • 229
0 votes
0 answers
37 views

Why use cyclotomic polynomials for RLWE?

This paper On Ideal Lattices and Learning with Errors Over Rings proposed RLWE which is Ring and hence efficient version of LWE problem. My question is that they considered cyclotomic polynomials for ...
user avatar
  • 229
1 vote
2 answers
53 views

Why use negacyclic convolutions for polynomial multiplication instead of regular convolutions?

When multiplying polynomials from $\mathbb{Z}_q[X] / (X^n-1) $, the discrete NTT is used because: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \...
user avatar
2 votes
1 answer
142 views

RLWE Explanation

In RLWE, we often choose the following polynomial ring, where q is a prime, and n is a power of 2, e.g. $2^k$ $$\mathbb Z_q[X]/(X^n + 1)$$ We know that ${X^{2^k}} + 1$ is an irreducible polynomial ...
user avatar
0 votes
0 answers
31 views

Reference Implementation of RLWE-Based schemes?

Now RLWE-based Encryption scheme is so popular because of its post-quantum property and application in Homomorphic Encryption. I am trying to get more familar with RLWE-based Encryption by ...
user avatar
  • 47
1 vote
0 answers
70 views

Why there is so high computational cost of multiplication in Microsoft Seal?

I was doing some Microsoft Seal testing on my macbook pro (i7) and got following results Coefficient mod $q = 100$ bits and Polynomial degree $n= 8192$ Ciphertext-Plaintext multiplication takes 0.211 ...
user avatar
  • 229
0 votes
0 answers
27 views

What is minimum size of polynomial modulus in Seal implementation of BFV?

Is there a way to get flexible parameters in Seal for batching? The issue is that for polynomial mod $n=4096$, the function I am computing has a multiplicative depth of $3~4$, to handle noise growth I ...
user avatar
  • 229
0 votes
1 answer
62 views

How to understand noise growth in BFV?

I am trying to understand the noise growth due to multiplication in BFV encryption. As explained in section 4 and equation 3 of this paper: https://eprint.iacr.org/2012/144.pdf. I couldn't follow what ...
user avatar
  • 229
4 votes
2 answers
411 views

Difference between FFT and NTT

What are the main differences between the Fast Fourier Transform (FFT) and the Number Theoretical Transform (NTT)? Why do we use the NTT and not the FFT in cryptographic applications? Which one is a ...
user avatar
  • 365
1 vote
1 answer
110 views

How lattices and LWE are connected?

I am a last-year master student in pure mathematics and I am working on my thesis. I am working on a connection between lattice-based encryption and Ring LWE and between Ring LWE and Homomorphic ...
user avatar
1 vote
1 answer
114 views

What are limits of Modulus Switching in BFV encryption?

I want to understand the limits of modulus switching in BFV. Lets assume $q$ represents ciphertext modulus and $t$ represents plaintext modulus. $q$ is set to a $60$ bit value and $t$ is set to $20$ ...
user avatar
  • 229
1 vote
1 answer
46 views

What is Relationship between ciphertext quotient and polynomial degree in RLWE?

In Ring Learning with Errors problem, the size of the ciphertext quotient $q$ decides the size of the polynomial degree $n$ or vice versa. In other words, rlwe problem is hard only when the polynomial ...
user avatar
  • 229
1 vote
2 answers
108 views

Why RLWE is lighter than LWE and why we can pick $a_i$ as a permutation of $a_1$ in RLWE but not LWE?

In LWE, we have $$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$ for a secret key $s\in \{0,1\}^n$ and $a_1\in \mathbb{Z}_q^n$ This is an encryption of a number $\mu_1$. If we want to encrypt $n$ ...
user avatar
0 votes
0 answers
81 views

Are there (fully) homomorphic libraries that implement BFV with bootstrapping?

All libs that I could find like SEAL and LattiGo do not implement BFV bootstrapping. LattiGo for example implements bootstrapping for CKKS, which I heard is not true bootstrapping because you end up ...
user avatar
1 vote
1 answer
51 views

RLWE with invertible elements

Let $R = \mathcal{O}_K$ be the ring of ingtegers of $K$, where $K$ is an algebraic number field, and $q$ a modulus. Let $\chi$ be some error distribution used to sample an element $e$. A primal RLWE ...
user avatar
  • 349
2 votes
0 answers
34 views

Centrality of Gaussian distribution for LWE error

Consider the LWE problem. Let $A$ be an $m \times n$ matrix, $x$ is an $n \times 1$ vector, $u$ is a $m \times 1$ vector, and $e$ is sampled from a Gaussian distribution. We are given either $Ax + e ~~...
user avatar
2 votes
1 answer
100 views

LWE and extended trapdoor claw free functions

Let $q \geq 2$ be a prime integer. Consider two functions, given by: $$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$ $$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$ where we have: \begin{...
user avatar
2 votes
1 answer
60 views

The significance of duals in RLWE

In an algebraic number field, an ideal $I$ in the ring of integers $\mathcal{O}_K$ has dual $I^\vee = \{x\in\mathcal{O}_K\text{ : }T_{K/\mathbb{Q}}(xy)\in\mathbb{Z}\text{ for all }y\in I\}$, where $T_{...
user avatar
  • 349
2 votes
1 answer
75 views

How is it legal to use a rounded Gaussian for LWE?

As far as I understood, in Regev's initial paper, the error distribution was first constructed as follows: Then rounded in the following way: Using this distribution, the reduction in the theorem ...
user avatar
  • 365
2 votes
1 answer
81 views

LWE and pseudorandom functions

Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there?
user avatar
2 votes
2 answers
93 views

LWE - Encrypting/Decrypting messages bigger than 1 bit

I'd like to know if LWE (and its variants: RLWE and MLWE) can cipher messages bigger than 1 bit. Is it possible? I didn't find any reference yet. Could you explain it to me or give some good ...
user avatar
1 vote
0 answers
73 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? ...
user avatar
3 votes
0 answers
47 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
user avatar
3 votes
0 answers
68 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}...
user avatar
1 vote
0 answers
70 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 ...
user avatar
  • 365
1 vote
0 answers
76 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$...
user avatar
1 vote
1 answer
60 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 ...
user avatar
  • 51
3 votes
1 answer
98 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,...
user avatar
  • 125k
2 votes
1 answer
72 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. ...
user avatar
  • 229
4 votes
1 answer
173 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_\...
user avatar
0 votes
0 answers
58 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 ...
user avatar
2 votes
1 answer
117 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 ...
user avatar
0 votes
1 answer
96 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.
user avatar
  • 365
3 votes
1 answer
133 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}$: $$...
user avatar
1 vote
1 answer
108 views

How is the Chinese remainder theorem used in this proof?

Can you explain it in detail ?
user avatar
  • 409
2 votes
1 answer
117 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 $...
user avatar
  • 409
2 votes
1 answer
103 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 ...
user avatar
  • 409
1 vote
0 answers
36 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 ...
user avatar
2 votes
0 answers
47 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 ...
user avatar
0 votes
1 answer
117 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 ...
user avatar
  • 409
0 votes
1 answer
92 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 ...
user avatar
4 votes
2 answers
371 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 ...
user avatar
2 votes
1 answer
56 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 ...
user avatar
  • 349
1 vote
0 answers
57 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 ...
user avatar
  • 21
0 votes
0 answers
118 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 ...
user avatar
  • 21