Skip to main content

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
0 answers
11 views

Is there any bound on the size of ring dimension for Torus FHE?

I see that all implementations of TFHE in opensource supports 2^10 to 2^12 size of ring dimensions. Is there any specific reason (crypto) behind choosing the value or can we choose higher dimensions (...
Green Amber's user avatar
1 vote
1 answer
49 views

lattice RLWE encryption and decryption process

I am here trying to solve an issue that I face a lot during solving RLWE. The issue is that I am not able to retrieve the original message after the decryption process. I use the following encryption ...
A. H's user avatar
  • 31
1 vote
1 answer
54 views

Literature on Batching in FHE

From what I understand, the folklore way to batch Ring-LWE style cipher texts is to use the Chinese remainder theorem. I am wondering if there are any different approaches/optimizations to this style ...
woah's user avatar
  • 27
0 votes
1 answer
93 views

Plaintext modulus choice for Fully Homomorphic Encryption

For SIMD fully homomorphic encryption scheme like BFV/BGV, and the underlying R-LWE problem parameterized by $n, p, q, \alpha$ (respectively the dimension, the plaintext modulus, the ciphertext ...
ProfCornDog's user avatar
0 votes
0 answers
195 views

Is the cryptography scheme over lattice still secure? [duplicate]

In https://eprint.iacr.org/2024/555, the author proposed a quantum algorithm to solve LWE problem. How serious is its impact on the existing scheme over lattice.
guangyu liao's user avatar
2 votes
2 answers
105 views

Probabilistic proof of multiplying two elements from non-prime finite field

I was reading this paper, and there, they use the ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$ for all their operations. And that looks like a construction of finite field $\mathbb{F}_{\...
the thinker's user avatar
0 votes
1 answer
66 views

Is using the polynomials ring $\mathbb{Z}_{2}[x]/(x^8+1)$ in RLWE secure against brute force attack?

Given the ring $R_2=\mathbb{Z}_{2}[x]/(x^8+1)$, initiate a public key encryption based on RLWE $(A,b=As+e)$ where all the parameters are selected as polynomials over the given ring. Under the ...
Anas Ahmad's user avatar
0 votes
1 answer
58 views

The proof of Claim 5.2 in the "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography"

When I'm reading this paper "On lattices, learning with errors, random linear codes, and cryptography" by O. Regev. I have trouble understanding the proof of claim 5.2. "Hence, it is ...
Solaris's user avatar
  • 15
2 votes
1 answer
245 views

Ring Learning With Errors : why is it called ring and referred it as Ring LWE

I am curious about the structure of the quotient ring in Ring LWE. So $R=\mathbb Z_q[x]/(x^n+1)$, where q is prime, $x^n+1$ is an irreducible polynomial and $n$ is a power of 2. So, this structure ...
user479610's user avatar
1 vote
0 answers
81 views

Digit Extraction for HE Bootstrapping

I was wondering if someone could explain the Digit Extraction from HElib in simple words: Apply a homomorphic (non-linear) digit-extraction procedure, computing $r$ ciphertexts that contain the ...
kindi's user avatar
  • 11
2 votes
1 answer
198 views

Do we know that LWE is harder than Ring LWE?

The plain, normal-form, decisional LWE problem over $\mathbb{Z}/q\mathbb{Z}$ is: given a uniformly random $n\times n$ matrix $A$ and vector $b\in \mathbb{Z}/q\mathbb{Z}^n$, decide if $b=As+e$ for ...
Sam Jaques's user avatar
  • 1,202
2 votes
1 answer
271 views

Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?

Specifically, I want an algebra group $G$ (or ring $R$) features: Given elements $g,h\in G$ (or $R$ ), computing $g\cdot h \in G$ (or $R$ ) is easy. Given an element $g \in G$ (or $R$ ), finding the ...
X.H. Yue's user avatar
  • 392
2 votes
1 answer
96 views

Arithmetic in Cyclotomic Number Rings with Shoup's Number Theory Library (NTL)

I wish to do arithmetic on elements in an integer subring of a cyclotomic number field, i.e, in $\mathcal{O}_K = \mathbb{Z}(\zeta) \cong \mathbb{Z}[X] / <\phi_m(x)>$ where $\zeta$ is a root of ...
Rohit Khera's user avatar
0 votes
0 answers
69 views

[About choosing params in BGV like ciphertexts]

I am new to lattice-based cryptography, so sorry that this question might seems stupid May I ask that how can I choose the BGV parameter of ciphertext with plain text in mod 128, and error in ...
js wang's user avatar
  • 361
2 votes
1 answer
148 views

Ring learning with errors KEX and probabilistic encryption

I came across Prof. Bill Buchanan's video "Lattice Crypto: Ring LWE with Key Exchange" explaining the RLWE-KEX. I understood everything he explained until the last part, where he is talking ...
A. H's user avatar
  • 31
0 votes
0 answers
68 views

Understanding noise budget calculation in seal

I am trying to understand theory behind noise budget operation implemented in seal Let the ciphertext be defined as $$ c0=A \in Rq \\c1= As+v+delta*m \in Rq $$ They first calculate noise ...
LWE-13's user avatar
  • 251
1 vote
0 answers
47 views

[About parameters effect LWE and SIS to be computation or perfect secure]

Hello I am new to lattice cryptography I am reading the paper More Efficient Commitments from Structured Lattice Assumptions They define bound B in page 3 Then In figure 1 in page 9 Can ...
js wang's user avatar
  • 361
1 vote
1 answer
100 views

Can you instantiate Ring-LWE with coefficients from a prime-power field?

Generally, we instantiate Ring-LWE with the polynomial ring $R = \mathbb{F}_q\ /\ (X^N+1)$ for prime $q$ and some power-of-two $N$. Can we instead do Ring-LWE over the ring $R = \mathbb{F}_q\ /\ (X^N+...
S. M.'s user avatar
  • 11
3 votes
1 answer
328 views

KYBER.CPAPKE: IND-CCA Security of Lyubashevsky, Peikert, Regev (LPR) Encryption

The NIST Kyber KEM spec. defines an encryption scheme, KYBER.CPAPKE, that's a variant of the so called Lyubashevsky, Peikert, Regev ("LPR") encryption scheme [1]. While LPR encryption is ...
Rohit Khera's user avatar
0 votes
1 answer
45 views

About learning with error rings with only constant coefficient

I am new to RLWE, would like to ask whether what I am thinking make sense Suppose I have a message e.g.: x=5 And I have a lattice based encryption scheme, e.g.: BGV could I encrypt x with BGV by ...
js wang's user avatar
  • 361
0 votes
2 answers
174 views

Is $0/1$ error ok in LWE? [closed]

Can the error in LWE or ringLWE schemes be from $\{0,1\}$? If not why and what is the best attack in this case?
Turbo's user avatar
  • 930
1 vote
1 answer
509 views

Challenges like RSA factoring challenge

RSA factoring challenge is a famous one and is still not completely solved. Are there similar challenges for Discrete log over $\mathbb Z_p^*$? Discrete log over Elliptic curves? LWE? LPN?
Turbo's user avatar
  • 930
0 votes
1 answer
272 views

What if LWE is not as secure as we think?

LWE schemes are currently being deployed. LWE has no quantum polynomial time algorithms as far as we know. Despite this what is the consequence if LWE can be broken on a classical computer? Do we ...
Turbo's user avatar
  • 930
2 votes
0 answers
47 views

worst case to average case reduction in non-cyclotomic Ring LWE

I understand that we need 2-to-power cyclotomic ring to show that the solving decision RLWE is as hard as solving search RLWE. Is there any chance to prove it without 'cyclotomic' property? For ...
GH HONG's user avatar
  • 33
5 votes
1 answer
101 views

Ring LWE distribution definitions

This may be a stupid question but I've been stuck on parsing these definitions for a while. I am reading the paper "On Ideal Lattices and Learning with Errors Over Rings" by Lyubashevsky, ...
cryptolearner's user avatar
2 votes
1 answer
108 views

Security of RLWE encryptions of secret keys

Under which conditions is it secure to publish an encryption of the secret key $s$ under itself in terms of an $RLWE_s(s)$ ciphertext? Because for some schemes this is (repeatedly) used in ...
opag's user avatar
  • 63
1 vote
0 answers
47 views

Tensor and power bases for SIS?

What is there to say about using a power basis or a tensor basis or some combination of them for the RSIS problem in lattice cryptography? Restricting to dimension 3 for illustration, usually the ...
Joseph Johnston's user avatar
2 votes
0 answers
157 views

Attacks on Ring-LWE exploiting structure of ideal lattice?

Currently every LWE-based cryptographic schemes analyze their security using lattice estimators and lattice estimators analyze the security of standard LWE even though the actual scheme is based on ...
Lee Seungwoo's user avatar
2 votes
1 answer
52 views

For what 'rounding constant' exists in Round5?(NIST PQC Round 2 Algorithm)

I am reading a paper Round5. This public key encryption scheme is based on Ring-LWR but I found it is a little bit different from typical LWR-based PKE scheme. In the key generation algorithm of ...
Lee Seungwoo's user avatar
4 votes
1 answer
362 views

Understanding RLWE Encryption

LWE Encryption Scheme by Regev is inefficient due to its public key sizes in $O(n^2)$. This led to the variant problem RLWE, defined in this paper : Let $n$ be a power of two, and q a prime ...
rerouille's user avatar
1 vote
1 answer
91 views

How & where is concepts of Good basis and bad basis used in Crystal kyber?

I've read the documentation of Crystal Kyber, but nowhere it is mentioned about good basis and bad basis. Please explain how and where is the good basis and bad basis is used in crystal kyber.
Sujan SM's user avatar
1 vote
1 answer
195 views

Why predicting an error in Crystal Kyber is considered to be hard?

Hi I have started studying on crystal kyber recently. Gained some knowledge regarding its algorithm and how it works. My doubt is why it is tough for attacker to extract secret vector from pk itself ...
Rakmo's user avatar
  • 21
0 votes
1 answer
433 views

How is MLWE used for key generation in Kyber?

I've been reading about Crystal kyber, and i read that the in the key generation process, the public key pk is computed using secret key s in such a way that the ...
Sujan SM's user avatar
3 votes
1 answer
247 views

Hardness of LWE

I was reading "TFHE Deep Dive" from Ilaria Chillotti, and I am a bit confused over the sample given in 31:08 In the above toy sample, isn't it possible to directly eliminate noise by ...
xade93's user avatar
  • 51
2 votes
1 answer
201 views

Choice of Polynomial Quotient Ring

In (lattice-based) cryptography, the quotient ring $\mathbb{Z}[X]/(X^n+1)$ where $n = 2^e$ is a power of 2 is used in various cryptographic schemes (e.g., CRYSTALS-Kyber). It is my understanding that ...
muukong's user avatar
  • 23
1 vote
0 answers
64 views

Why the error in LWE is sampled from the normal distribution?

$$a_1*s+m_1+e_1 = b_1\\\cdots\\ a_n*s+m_n+e_n = b_n$$ The LWE problem is related to finding the solution $s$ to this system, when the $e$ are sampled from the normal distribution. Why the normal ...
Rafaelo's user avatar
  • 23
2 votes
1 answer
410 views

What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?

I am trying to understand the post quantum based signature scheme Dilithium. I know what the hard problems are in the scheme, but I am having trouble in understanding the utilization of short integer ...
Muhammad Awais's user avatar
4 votes
1 answer
113 views

Closest Vector Problem in RLWE

I am interested in a polynomial form of the lattice problem Closest Vector Problem (C.V.P), or in other words if C.V.P. can be ''transferred'' to Ring-LWE. My idea about this question is that a ...
Kate Jns's user avatar
1 vote
1 answer
105 views

Expectation of the size of algebraic norm in power of two cyclotomic field

Let $\mathcal R$ be the ring of integers of a power of two cyclotomic field. That is, $\mathcal R = \mathbb Z[x] /\langle x^{2^k}+1\rangle $ for some integer $k$. We denote $\mathcal R / q \mathcal R$ ...
Ring-LWE's user avatar
1 vote
1 answer
237 views

LWE encryption error

in learning with error encryption scheme (e.g. in Kyber scheme). there are two vectors: $u = r^t A + e_2$ and $v= r^t * pk + e_3 + \lfloor \frac{q}{2}\rceil m$ such that $pk = As +e_1$. my question ...
Don Freecs's user avatar
2 votes
1 answer
117 views

Statistical Distance and Learning with Rounding

Given an integer $b$ modulo a prime $q$, one can define a `rounding’ function $\lfloor b\rceil_p$ for a prime $p$, $p<q$, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$...
a196884's user avatar
  • 381
1 vote
1 answer
73 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 ...
WillowFinch's user avatar
2 votes
0 answers
114 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 ...
LWE-13's user avatar
  • 251
1 vote
1 answer
83 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 ...
LWE-13's user avatar
  • 251
2 votes
3 answers
363 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,...
user102777's user avatar
3 votes
1 answer
137 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 ...
frost.crystal's user avatar
1 vote
0 answers
166 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?
LWE-13's user avatar
  • 251
0 votes
0 answers
240 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 ...
LWE-13's user avatar
  • 251
2 votes
2 answers
337 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) \...
warforgad's user avatar
4 votes
1 answer
632 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 ...
fuo55631's user avatar