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.
149
questions
1
vote
1
answer
129
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 ...
- 1,105
2
votes
1
answer
232
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 ...
- 368
2
votes
1
answer
78
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 ...
- 678
0
votes
0
answers
40
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 ...
- 327
2
votes
1
answer
102
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 ...
- 21
0
votes
0
answers
52
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 ...
- 251
1
vote
0
answers
35
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 ...
- 327
1
vote
1
answer
67
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+...
- 11
3
votes
1
answer
207
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 ...
- 678
0
votes
1
answer
42
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 ...
- 327
0
votes
2
answers
118
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?
- 908
1
vote
1
answer
487
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?
- 908
0
votes
1
answer
212
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 ...
- 908
2
votes
0
answers
43
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 ...
- 33
2
votes
1
answer
58
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, ...
2
votes
1
answer
81
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 ...
- 43
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 ...
- 357
2
votes
0
answers
95
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 ...
- 363
2
votes
1
answer
47
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 ...
- 363
3
votes
1
answer
215
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 ...
- 41
1
vote
1
answer
65
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.
- 33
1
vote
1
answer
136
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 ...
- 21
0
votes
1
answer
237
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 ...
- 33
3
votes
1
answer
194
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 ...
- 51
1
vote
1
answer
132
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 ...
- 13
1
vote
0
answers
61
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 ...
- 23
2
votes
1
answer
327
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 ...
4
votes
1
answer
90
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 ...
- 65
1
vote
1
answer
83
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$ ...
- 13
1
vote
1
answer
201
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 ...
- 421
2
votes
1
answer
107
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.$$...
- 381
1
vote
1
answer
50
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 ...
- 11
2
votes
0
answers
108
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 ...
- 251
1
vote
1
answer
80
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 ...
- 251
2
votes
3
answers
265
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,...
- 33
3
votes
1
answer
115
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 ...
1
vote
0
answers
138
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?
- 251
0
votes
0
answers
167
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 ...
- 251
1
vote
2
answers
170
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) \...
- 33
2
votes
1
answer
423
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 ...
- 23
1
vote
0
answers
119
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 ...
- 251
0
votes
1
answer
181
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 ...
- 251
5
votes
2
answers
1k
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 ...
- 425
1
vote
1
answer
755
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 ...
- 65
1
vote
1
answer
323
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$ ...
- 251
1
vote
1
answer
95
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 ...
- 251
1
vote
2
answers
317
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$ ...
- 111
1
vote
1
answer
80
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 ...
- 381
2
votes
0
answers
54
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 ~~...
- 377
2
votes
1
answer
179
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{...
- 377