Questions tagged as ['ring-lwe']

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

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

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

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.

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

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

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

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?

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

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

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?

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

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]$ ...

Can you explain it in detail ?

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?

$\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

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