All Questions
Tagged with lattice-crypto ring-lwe
89 questions
2
votes
2
answers
33
views
Security of Ring-LWE and Module-LWE encryption scheme
Regev-05 encryption under plain LWE consists in using a public key $\mathsf{pk} = (\mathbf{A}, \mathbf{b} = \mathbf{A}^\top\mathbf{s}+\mathbf{e})$, where $\mathbf{A}\in \mathbb{Z}_q^{n\times m}$ is ...
- 509
2
votes
1
answer
36
views
Understanding Canonical-embedding vs Coefficient-embedding in Ideal Lattices: Relation to NTT?
I'm trying to understand the relationship between different representations of ideal lattices, particularly the canonical embedding and coefficient embedding. While studying these concepts, I noticed ...
- 85
0
votes
2
answers
55
views
Can the message space for Ajtai Hash be extened?
I have a question regarding the Ajtai hash function. Typically, the message space for this function is the binary space $\{0, 1\}^m$. However, I am considering extending the message space to $\{-1,0, ...
- 115
1
vote
1
answer
69
views
Is there an efficient algorithm to compute the inverse of a small-norm element in a special polynomial ring？
The paper "Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs" presents a corollary stating that in a polynomial ring $...
- 115
0
votes
1
answer
59
views
Why consider/formulate Shortest Vector Problem as a Promise Problem and not as a Decision Problem?
We know (search) approximate Shortest Vector Problem ($\mathsf{SVP}_{\gamma}$): Given an arbitrary basis $\mathbf{B}$ of some lattice $\mathcal{L}=\mathcal{L}(\mathbf{B})$, find a shortest non-zero ...
- 586
3
votes
0
answers
84
views
Why RLWE is typically implemented using unsigned integers?
Every RLWE implementation I know uses unsigned integers even when it needs to represent signed values. Why?
3
votes
1
answer
101
views
Choosing $x^n+1$ as an irreducible polynomial in $\mathbb{Z}[x]$ instead of $x^n-1$ for ring $\mathbb{Z}[x]/\langle f(x)\rangle$ of Ring-LWE
In the note of ["Ring-SIS and Ideal Lattices by Noah Stephens-Davidowitz (for Vinod Vaikuntanathan’s class", footnote 3], it has written:
3 The ring $\mathbb{Z}[x]/(x^n + 1)$, ideal ...
- 586
1
vote
1
answer
64
views
Gaussian width in lattice setting
In the lattice setting (like LWE, RLWE) , the Gaussian function is often defined as
$$
\rho_{\Sigma}(x) = e^{-\pi x^T\Sigma^{-1}x}
$$
The discrete Gaussian distribution $\mathcal{D}_{\Lambda, \Sigma}$ ...
- 11
3
votes
1
answer
308
views
Questions about LWE in NIST standards
LWE instances have the form $\vec{a}_i,b_i = \langle\vec{a}_i,\vec{s}\rangle+e_i\bmod q$ for some integer $q$ and for $i=1,\dots,m$.
My questions are about the NIST proposed standards. In the ...
- 1,025
1
vote
0
answers
39
views
What is the difference between PLWE (Polynomial Learning with Errors) and RLWE (Ring Learning with Errors)？ [closed]
Recently, I have been studying lattice-related concepts, and I want to understand the differences between PLWE and RLWE, such as how their security compares, as well as their structure and value ...
- 11
0
votes
0
answers
28
views
Issue building RLWE based program
I've successfully built a LWE based program now moving onto building a RLWE based python program using: https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/ as a ...
1
vote
0
answers
38
views
Understanding FHE bootstrapping: value of $q$ fed to lattice estimator
I am implementing OpenFHE. In the implementation I'm generating the modulus chain as shown in the example here. I am trying to run Lattice estimator for the same parameters in this example.
I wanted ...
- 19
0
votes
0
answers
26
views
Urgent help with R-LWE Parameters Choice
I am trying to understand CKKS bootstrap algorithm and wanted to understand how is p (plaintext modulo) and q (ciphertext modulo) related in determining the size of the modulus chain. Suppose my ring ...
- 19
-1
votes
1
answer
155
views
Urgent help with LWE Estimator
I am trying to estimate LWE parameters. I know of the GitHub library for LWE estimator but it has no instructions for installation and also provides no guidance for running simple examples. I have ...
- 19
0
votes
0
answers
24
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 (...
- 19
1
vote
1
answer
81
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 ...
- 33
1
vote
1
answer
68
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 ...
- 49
0
votes
0
answers
197
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.
- 51
2
votes
2
answers
114
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}_{\...
- 147
0
votes
1
answer
64
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 ...
- 15
2
votes
1
answer
241
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,614
2
votes
1
answer
111
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
94
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 ...
- 371
1
vote
0
answers
54
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 ...
- 371
1
vote
1
answer
120
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
395
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
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 ...
- 371
5
votes
1
answer
128
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, ...
- 113
1
vote
0
answers
49
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
3
votes
0
answers
199
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 ...
- 373
2
votes
1
answer
110
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.
- 43
3
votes
1
answer
296
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
2
votes
1
answer
241
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 ...
- 23
4
votes
1
answer
149
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 ...
- 85
2
votes
1
answer
126
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
2
votes
3
answers
423
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
147
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 ...
2
votes
2
answers
445
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) \...
- 43
4
votes
1
answer
734
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 ...
- 43
1
vote
0
answers
129
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
3
votes
1
answer
2k
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 ...
- 85
1
vote
1
answer
427
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
107
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
1
answer
182
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_{...
- 381
2
votes
1
answer
166
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 ...
- 505
2
votes
2
answers
673
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 ...
- 33
1
vote
0
answers
206
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?
...
- 51
3
votes
0
answers
152
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 ...
- 505
4
votes
1
answer
258
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_\...
- 135
0
votes
0
answers
70
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 ...
- 135