# Questions tagged as ['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.
Score: 1
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?

root hermite factor: 1.0045 ? ? ? bit-security : 128 100 160 180

Score: 3
parameter estimating in lattice signature scheme

when reading [BDLOP18], I run the lwe-estimator with the recommended parameters in Table 2 , but the result of hermite factor is 1.007, this result is bigger than the recommended hermite factor 1.0035

Score: 3
Is the scheme in LWE also valid in R-LWE?

One way of interpreting matrices in RLWE is that they are a subset of standard integer matrices that have special structure. For example, rather than using a random matrix $$A\in\mathbb{Z}_q^{n\times n}$$ (as we might in LWE-based constructions), we can replace this a matrix with a matrix where the first column (or row) is random, and the rest have a cyclic rotation structure:

$$\begin{pmatrix} a_1 & ...$$

Score: 1
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 give a good reference where proof exists.

Score: 1
Ring-LWE definition

I'm trying to understand the structure of Rings used in Ring-LWE based on Chris Peikert's Decade of Lattice Based Cryptography paper. The paper says that $$R := \mathbb{Z}[x]\big /\langle f(x) \rangle$$ and clearly for this to make sense, $$f(x) \in \mathbb{Z}[x]$$. But then $$R_q$$ is defined as $$R_q := R\big / qR \stackrel{?}{=} \mathbb{Z}_q[x]\big / \langle f(x) \rangle$$

So my question is which rin ...

Score: 1
Why RLWE is hard or even has a solution?

I was thinking about why and how the RLWE problem is hard at all. I know that it's hard because it can be reduced to the shortest vector problem, but I'm thinking about how does it even have a solution.

The problem is basically:

$$a_{i}(x)$$ be a set of random but known polynomials from $$F_q [ x ] / Φ ( x )$$ with coefficients from all of $$F_q$$.

$$e_i ( x )$$ be a set of small random and unknown p ...

Score: 3
Functional and security model for SEAL

What's the functional and security model for SEAL?

From this I get that it

allows additions and multiplications to be performed on encrypted integers or real.

But what are the limitation, like range, precision, on inputs and outputs? What operations can be performed? Is there some limitation beyond range/precision?

What is the security model an application designer using SEAL as a black box should assum ...

Score: 1
Security level of FHE constructions for non-standard parameters

homomorphicencryption standards already provide recommended parameters and their corresponding security levels. However, I would like to calculate a security level for nonstandard parameter selection.

Is there an simple way to calculate the security level?

Score: 4
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_\infty \leq \beta: r\xleftarrow{\\\} R_q]\leq \left(\dfrac{2\beta+1}{q}\right)^n$$, where $$R_q=\mathbb{Z}_q[X]/(X^n+1)$$, where $$n$$ is a power of two, $$q$$ is a prime and $$\beta$$ is some positive real number ...

Score: 0
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 coefficients are assumed to be in $$[-\frac{q-1}{2},\frac{q-1}{2}]$$. I'll just cite some facts that I will use in my proof:

1. $$X^n+1$$ factors into two irreducible factors modulo $$q$$, where each factor is of de ...
Score: 2
Proof that (ring-)LWE secret is unique

I read Regev's paper in 2005 about Learning with Errors and he mentioned that the secret of a LWE sample is unique but I have not seen a proof of this claim. Can someone point me to a paper proving this claim? Also, for the ring-LWE case, in particular for power of two cyclotomics, is the secret always unique?

Score: 0
Small modulus to noise ration in LWE implies better security

I don't quite understand why a smaller quotient between modulus $$q$$ and the noise's standard deviation implies better security against known attacks.

Score: 3
Why define the dual of an ideal lattice with "Tr" rather than inner product?

In the paper [LPR12], I've learned that ideal lattices are ideals in algebraic number fields. However, I can't understand why we define the dual lattice of an ideal lattice with $$\operatorname{Tr}$$: $${L}^{\vee}=\{x \in K: \operatorname{Tr}(x {L}) \subseteq \mathbb{Z}\}$$

In detail, I mean, for any algebraic number field $$K$$, there's an embedding that embed it into space $$H$$. For $$K=\mathbb Q[\zeta] ...$$

Score: 1
How is the Chinese remainder theorem used in this proof？

Can you explain it in detail ?

Score: 2
Parameters in RLWE

Let $$n, q, \sigma$$ be the polynomial degree($$x^n+1$$), coefficient modulo, and the standard derivation, respectively. I often see some parameters such as

For RLWE, we can use the CRT to decompose the $$\text{RLWE}_{q}$$ to some $$\text{RLWE}_{q_i}$$ for $$1\leq i\leq l$$, where $$q = q_1 q_2\cdots q_l$$, then when we consider the security of RLWE, we should take $$\log q$$ or $$\log q_i$$ to be considered?

Score: 2
The error distribution in LWE

$$\textbf{Continuous LWE}$$ : $$(\overrightarrow{a}, b)\in \mathbb{Z}_q^n\times \mathbb{T}$$, where $$\mathbb{T}=\mathbb{R}/\mathbb{Z}$$, $$b = \langle \overrightarrow{a},\overrightarrow{s}\rangle/q + e\mod 1$$, where the error $$e$$ is sampled from $$\Psi_\alpha(x) := \sum_{k=-\infty}^{\infty}\frac{1}{\alpha}\cdot exp(-\pi(\frac{x-k}{\alpha})^2), x\in [0,1)$$ over the torus $$\mathbb{T}$$. The density function

Score: 1
composition of RLWE distributions

Assume we have the polynomial space $$R_q$$ defined as $$R_q = Z_q/(X^n + 1)$$. Additionally, we define the error distribution $$\chi$$ as a discrete centred Gaussian bounded by $$B$$. Let $$s,t \in R_q$$ be randomly selected secrets. Let $$r_0=as+e_0$$ where $$a \gets R_q$$ is selected uniformly at random and $$e_0 \gets \chi$$ is sampled from the noise distribution. We know that given $$a$$, the distribution of