Hot answers tagged

11

They're actually sampling $5n$ elements from $\Psi_{16}$. Perhaps Protocol 2 on page 5 shows this most clearly, where $\textbf{s}, \textbf{e} \stackrel{\$}{\leftarrow} \Psi_{16}^n$ and $\textbf{s}', \textbf{e}', \textbf{e}'' \stackrel{\$}{\leftarrow} \Psi_{16}^n$ are sampled (on line 3 on Alice' side, and line 1 on Bob's). This probably also answers part of ...


7

Yes, LPN is (essentially by definition) equivalent to the hardness of decoding a random linear code over $\mathbb{F}_2$. No, there is no known reductions between LPN and LWE. It is usually believed that LPN is (in some sense) "harder to break" than LWE, simply because we know much less attacks on LPN. It seems to have less structure that could be exploited ...


6

Let $R$ be the ring $\mathbb{Z}_p[X]/(X^n+1)$, where $n$ is a power of 2. The Ring-LWE assumption says that for any randomly chosen, fixed $s\in R$, the distribution of $$((a_1,a_1s+e_1),\ldots,(a_k,a_ks+e_k))$$ is indistinguishable from the distribution $$((a_1,u_1),\ldots,(a_k,u_k)),$$ where $a_i,u_i$ are uniformly random in $R$ and $e_i$ are chosen from ...


5

I'm assuming $n$ is a power of $2$ and that $q$ is an odd prime larger than $n$. I'm discarding the trivial case $s_1 = s_2$. If you consider everything $\mod q$, then it is most likely over the choice of $a$ that there exists $s_1 \neq s_2$ such that $\|a s_1 - a s_2\| = \sqrt{n}$. Indeed, $a$ is invertible in $R_q$ with probability about $1 - n/q$. Take $...


5

The previous (galvatron's) answer gave two good reasons why Ring-LWE is more efficient. They explain why the running time of LWE schemes is worse than of Ring-LWE ones. (The n^2 vs n equations is more of an efficiency issue because in both cases, this part of the key is expanded from a 256-bit seed using an XOF. So it just takes a lot longer to expand an ...


5

As mentioned in the comments, there is still a lot of active research being done in the area of algorithms for solving Learning With Errors, as clearly it's an important topic for estimating the security of LWE-based cryptography. Therefore it's probably already not a good idea to rely on papers from more than 5 years ago if you want your parameter choices ...


5

Denote by $X$ the random variable which is the sum over all $S$. As mentioned, this is a Gaussian of standard deviation at most $\sqrt{m}r$ with $r = \alpha q$. Hence, by properties of the (sub-)Gaussian distribution you have that $$\operatorname{Pr}\left[|X| > t\right]\leq 2\exp\left(\frac{-\pi t^2}{r^2m}\right)$$ so, for $t = \frac{q}{2}$ you have $$...


5

The probability of error is negligible "as a function of $n$", meaning that the probability of error will decrease (quickly) as $n$ grows. Increasing $n$ should solve your issue.


5

There is a simple trick (known in the LWE literature as the Hermite normal form of the problem) that takes an existing LPN problem and transforms it into a problem in which the secret has the same Bernoulli distribution as the error. This trick is proved in Lemma 2 of Applebaum et al. for a more general case, or on the (Ring-)LPN attacks of Kirchner (Section ...


4

I believe it is also used in other lattice based schemes that use standard LWE. For example, the Frodo paper. They used a $seed_A$ and a Gen($\cdot$) function to compute $A$. Then Alice sends $seed_A$ instead of $A$ for the actually exchange. Gen($\cdot$) is a prior-agreed pseudorandom function that extracts and extends the seed.


4

The number of rows in matrix $\textbf{A}$ shows the number of LWE samples and $m=1$ means the adversary has access only to one sample. This would be a naive adversary model and would not be suitable for assessing the true hardness of the Problem. To consider a more powerful adversary model, a (seemingly) stronger definition is to assume that the adversary ...


4

This lemma is used to conclude that a sample from $\mathcal{D}_{\mathbb{Z}^n,\alpha q}$ is (with overwhelming probability) less than or equal to $\alpha q \sqrt{n}$. Now, because all values $\textbf{s}_{\textbf{A}},\textbf{s}_{\textbf{B}},\textbf{e}'_{\textbf{A}},\textbf{e}'_{\textbf{B}}$ are sampled from $\mathcal{D}_{\mathbb{Z}^n,\alpha q}$ , so $\textbf{...


4

I asked the question to the author directly. To answer the first question, authors of NewHope estimate their security very conservatively, whereas the estimator takes many other things into account. Specifically, here is the answer I got from the author. Hi, Id' suggest to use their claimed security. To explain the differences: The estimate you ...


3

It is easy to reduce this problem to LWE, since adding any element to a uniformly random value gives a uniformly random distribution. For example, here, $(A',b')$ is distributed the same as if $A'$ was drawn uniformly randomly, and $R$ set as $A'-A$. You're now in the setting of the LWE assumption and can replace $b'$ by a uniformly random value without ...


3

If you don't mind relying on random oracles, the simplest approach is to apply a generic transformation such as Fujisaki-Okamoto to the (Ring-)LWE based scheme you start from. See for example Peikert's PQCrypto'14 paper for a concrete instantiation, and the TCC 2016 paper of Targhi and Unruh for a proof of security of this type of transform in the quantum ...


3

Lemma 3 in this paper gives a better explanation regarding to your question 1 and 2. For a simple answer for question 3, because we have equally divided region, this gives us even change on $k_i$ and $k_j$ be even or odd number, thus the output of function $E$ is uniform random.


3

(It seems that the proof can be salvaged.) Let $\text{RLWE}$ denote the standard ring-LWE problem where the secret $s$ is drawn uniformly at random from $R$. Thus, the $\text{RLWE}$ assumption is: $$(a,as+e)\approx(a,r):a,r,s\leftarrow R, e\leftarrow\chi,$$ where $\approx$ denotes computational indistinguishability. $\text{RLWE}$ assumption implies ...


2

Answer of your question is in page $7$. Lemma2: For odd $q$, let $v=w+e\in Z_q$ for $w,e\in Z_q$ such that $2e\pm 1\in E \pmod q$. Let $\bar v=dbl(v)$ then $rec(2w,\langle \bar v\rangle _{2q,2})=\lfloor \bar v \rceil _{2q,2}$.


2

$q$ is the number of samples and $S$ is the set of indices such that $\sum_{i\in S}x_i = (1,0,...,0)$. In your example, we have $q=3$ and $S=\{1,3\}$. The first bit of the secret $s$ is equals to $\sum_{i\in S}b_i \mod 2$, but with probability $1/2+2^{-\Theta(n)}$ not $1$, because the noises are also considered in this summation. So we need to repeat this ...


2

He needs to add something uniformly random to the second coordinate, to get a distribution that is uniformly random. (The idea is that if he guesses the correct key, his rerandomization turns real instances into real instances. If he guesses the wrong key, his rerandomization should turn real instances into random instances.) If $p$ is a prime, then ...


2

The LWE assumption tells you that $(\mathbf{a},\mathbf{a}\mathbf{s}+e)$ looks random for a hidden random vector $\mathbf{s}$, a random vector $\mathbf{a}$ and small error $e$. Invoking the LWE assumption k times, you get that $(\mathbf{a},\mathbf{a}\mathbf{s}_1+e_1,\mathbf{a}\mathbf{s}_2+e_2,\ldots,\mathbf{a}\mathbf{s}_k+e_k)$ is indistinguishable from $(\...


2

Neither of the alternatives in your question is completely correct. The distribution $\Psi_{\beta}$ is as defined by equation (7) in Section 2 of your reference: $$\Psi_{\beta}(r) = \sum_{k = -\infty}^{\infty} \frac{1}{\beta}\,\exp\left(-\pi \left(\frac{r - k}{\beta}\right)^2\right),$$ for $r \in [0, 1)$. So $\beta$ is not the standard deviation of a normal ...


2

It seems to me this argument works: According to Ryan O'Donnell's notes here here, $\tau$ is typically strictly smaller than $1/2$. Even in that case, if the secret $s$ is uniform this is enough to make $a\cdot s$ uniform, assuming the components of $a$ are independently chosen with a biased Bernoulli distribution. Even though each term $a_i \cdot s_i$ in ...


2

Yes. This problem is roughly equivalent to LWE. If you have an oracle to solve $LWE_{n, q, m, \sigma}$, then you can solve an instance $(A, b := As + e)$ of your problem just by sampling a Gaussian $e_1$ and add it to $b_1$, that is, defining $b' := b + (e_1, 0, 0, ..., 0)$. Of course, $(A, b')$ is a legitimate instance of $LWE_{n, q, m, \sigma}$ and can ...


2

LPN is code-based problem, not a lattice problem. These are quite similar, but are defined with respect to different notions of "distance" (Hamming vs $\ell_p$-norm). In general while there are broad parallels between the worlds of lattices and codes, these parallels are not exact. A particular example is the hardness of computing the "smallest element" of ...


2

For Q1, $m = O(n\log q)$ is the size required for the leftover hash lemma to kick in and $Ax$ to be statistically close to uniform (I believe). See questions like this one. For Q2, the answer is yes. The hardness of LWE is essentially independent of the dimension $m$, as you can generate new LWE samples from a fixed collection of samples with only a mild ...


2

As hinted by @kelalaka in the comments, note that $q$ is odd, and $\gcd(2,q)=1.$ Therefore within $Z_q$ we have that $2e\neq 0,$ if and only if $e \neq 0,$ so the noise is never masked.


Only top voted, non community-wiki answers of a minimum length are eligible