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

How to correctly multiply homomorphically two RLWE-Based encrypted numbers

Assume that I have two ciphertexts,$c_1=(u_{0},v_{0})$ and $c_2=(u_{1},v_{1})$, encrypted by RLWE scheme and I wanted to do only one homomorphic multiplication, i.e., $c_1*c_2$. What is the correct ...
Anas Ahmad's user avatar
1 vote
1 answer
72 views

If a linear combination of a discrete gaussian is another one then how LWE samples are indistinguishable from Uniform?

I was reading "Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography" by Nicholas Genise, Daniele Micciancio, Chris Peikert and Michael Walter. In section 1.2 it ...
Barals's user avatar
  • 131
2 votes
2 answers
32 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 ...
vxek's user avatar
  • 509
2 votes
1 answer
33 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 ...
a15600712's user avatar
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, ...
user109993's user avatar
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 $...
user109993's user avatar
2 votes
1 answer
68 views

Do we have any attack for (R)LWE with small public key, secret and error?

Suppose we have an (R)LWE setup $(a, a\cdot s + e)$ in the ring $R = Z[x]/(x^n + 1)$ with $n$ a power of two, $R_q$ is the ring modulo a prime $q$ and $R_p$ is a ring modulo a prime $p$ with $q >&...
Barals's user avatar
  • 131
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 ...
user1035648's user avatar
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?
Guerlando OCs's user avatar
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 ...
user1035648's user avatar
2 votes
0 answers
52 views

Why Isn't My Ring-LWE Decryption Working with Noise?

I'm developing a Ring-LWE encryption system for my study, but I’m facing some issues. Here is the logic I’m using: ...
김민성's user avatar
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}$ ...
Robert's user avatar
  • 11
3 votes
1 answer
307 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 ...
Turbo's user avatar
  • 1,025
0 votes
0 answers
77 views

What is the message inflation ratio in ring-LWE?

I've been learning and implementing standard ring-LWE over $R_t = \mathbb{Z}_t[x]/(x^N+1)$ [1]. In my implementation [2] the inflation ratio is ~192 (it takes 192 bytes to encrypt 1 byte). My ...
Jackson Walters's user avatar
1 vote
1 answer
82 views

Noncommutative generalizations of NTRU

I recently learned and implemented NTRU Encrypt successfully in Python/SageMath. The key players are the polynomial rings $R = \mathbb{Z}[x]/(x^N-1)$ and reduction $R_p = \mathbb{Z}_p[x]/(x^N-1)$. One ...
Jackson Walters's user avatar
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 ...
Lexie's user avatar
  • 11
0 votes
0 answers
46 views

Help with Hybrid Homomorphic Encryption

I read in this paper here that symmetric ciphers like AES is not a good choice for Hybrid Homomorphic Encryption due to large multiplicative depth. I want to understand more about this statement. How ...
Green Amber's user avatar
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 ...
ringlearningwemmet's user avatar
0 votes
0 answers
33 views

Help with TFHE multiplication

I am trying to understand TFHE and realise that TFHE supports three types of ciphertexts: LWE : supports additive homomorphism and multiplication with constants RLWE : compact version of LWE RGSW : ...
Green Amber's user avatar
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 ...
Green Amber's user avatar
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 ...
Green Amber's user avatar
-1 votes
1 answer
154 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 ...
Green Amber's user avatar
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 (...
Green Amber's user avatar
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 ...
A. H's user avatar
  • 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 ...
woah's user avatar
  • 49
0 votes
1 answer
170 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
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.
guangyu liao's user avatar
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}_{\...
the thinker's user avatar
1 vote
1 answer
87 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
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 ...
Solaris's user avatar
  • 15
2 votes
1 answer
316 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
82 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
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 ...
Sam Jaques's user avatar
  • 1,614
2 votes
1 answer
294 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
  • 456
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 ...
Rohit Khera's user avatar
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 ...
js wang's user avatar
  • 371
2 votes
1 answer
190 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
  • 33
0 votes
0 answers
82 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
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 ...
js wang's user avatar
  • 371
1 vote
1 answer
119 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
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 ...
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
  • 371
0 votes
2 answers
236 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
  • 1,025
1 vote
1 answer
533 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
  • 1,025
0 votes
1 answer
300 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
  • 1,025
2 votes
0 answers
48 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
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, ...
cryptolearner's user avatar
2 votes
1 answer
129 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
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 ...
Joseph Johnston's user avatar
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 ...
Lee Seungwoo's user avatar