# 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.

151 questions
Filter by
Sorted by
Tagged with
1 vote
118 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[x]/(x^n+1)$, where $x^n+1$ is an irreducible polynomial and $n$ is a power of 2. So, this structure would not be a ...
1 vote
76 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 ...
• 11
170 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,135
247 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
89 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
48 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
115 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
59 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
39 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
82 views

124 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
149 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
196 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
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) \... 3 votes 1 answer 515 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 ... • 33 1 vote 0 answers 122 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 195 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 6 votes 2 answers 2k 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 ... • 435 1 vote 1 answer 877 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 342 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 106 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 339 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$ ...
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 ...