Questions tagged as ['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

The parameter of a lattice signature scheme DAZ19 with tight reduction can be choosed to make the underlying hardness problem intractable. How to estimate the parameter of a lattice signature scheme ESLL19 with lossy reduction? is there any relation between the reduction and parameter?

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

In Is Diffie-Hellman less secure when A and B select the same random number? , the possibility of Diffie-Hellman key exchange producing identical peer keys and the vulnerability of it against passive attackes was brought up, again - as a duplicate.

But is there a equivalent in *-LWE family of lattice-based key exchanges? My question being, without considering CCA-hardening such as Fujisaki-Okamoto t ...

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 am wondering why the modulus $q$ in the LWE problem has to be polynomial in $n$.

Another question is whether one can take it to be an arbitrary integer instead of a prime number.

Assume I have a matrix $A \in \mathbb{Z}^{m \times n}$, $m > n$, which forms a basis of a lattice. Given a vector target vector $t = Ax + e$, $t,e \in \mathbb{Z}^m$,$x \in \mathbb{Z}^n$, I want to find the (approximate) closest vector in the lattice $\mathcal{L}(A)$ to $t$.

I wanted to use Babai's nearest plane algorithm, in particular the NTL implementation NTL::NearVector to solve this problem (a ...

The Ajtai one way function is defined by

$$f_A(x)= Ax \; mod\; q $$ where the x $\in \{0,1\}^m$ and A $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ is one way function ( Ajtai 96)

While the Regev One way function(Regev 05) is defined over x $\in \mathbb{Z_q}^k$ and $e \in \mathscr{E}^m$ and A $\in \mathbb{Z_q}^{m \times k}$ .The one way function is defined as

$$g_A(x,e) =Ax +e \; mod\; q \; (LWE) $$

I recently reviewed biometric authentication with deep learning model, and I found, in cryptography, the fuzzy extractor,FE (or secure sketch,SS, plus strong extractor) have solve this problem good enough based on error-correcting codes, is there any research from this point to combine them? For deep learning model, it is natural to give a good representing for the input biometric object(e.g. face image ...

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.

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