New answers tagged lattice-crypto
1
The point $u$ here means that instead of sampling a point from the lattice $\Lambda$, you're sampling a point from the coset of the lattice $u + \Lambda$.
This is a "shifted copy" of the lattice (shifted by precisely $u$).
Generically though, you're looking for tail bounds of gaussian mass on lattices. You can find these a variety of places in the ...
4
A similar question could be asked about RSA --- why use 2048-bit RSA, and not 80-bit RSA?
The answer of course is due to cryptanalytic estimates. In particular, one estimates how difficult the underlying problem is (for factoring, it's roughly $\exp(O(\sqrt[3]{n}))$, and then sets the security parameter such that it takes $\approx 2^{80}$ bit operations to ...
1
You seem to have a few questions:
Why are Discrete Gaussians "not far" from the uniform distribution when you work mod the lattice?
This is worked out in the paper they are introduced in (Miccancio Regev 2004). See Lemma 4.1 in particular.
How to generate them?
It depends on whether you care about constant-time generation or not. Either way, there ...
1
A slightly different perspective on the matter is that often a lattice $\Lambda\subseteq\mathbb{Z}^n$ is used for its error-correction properties.
Lattices are infinite objects, but for efficiency we often assume they're periodic mod some integer (not necessarily prime, despite the choice of variable) $q$, which is known as being $q$-ary.
This gets us a ...
1
There seems to be no specific condition on $m$ and $n$ except $m,n \geq 1$.
The LWR assumption isn't that the problem is hard for any arbitrary $m, n$, it's there it's true for the specific $m, n$ pairs we use in practice. Obviously, for $m=n=1$, it's an easy problem; that's not particularly relevant, as we don't use $m=n=1$.
This is similar to the RSA ...
2
Well, these lattice schemes need to define a 'small vector' $\epsilon$ in such a way that the multiplication of two small vector elements $\epsilon_0 \times \epsilon_1$ is still small; that is, for a random element $A$, we still have $A \approx A + \epsilon_0 \times \epsilon_1$
One way to do this is to define a 'small vector' as one whose elements all have ...
2
Disclaimer: I'm not familiar with NTRU, and not in my comfort zon. Hence the many edits.
The problem asked can be summarized as: given $n$, $q$ coprime to prime $p$, and for $0\le i<n$ the coefficients $f_i\in\{-1,0,1\}$ of $F=\displaystyle\sum_{0\le i<n}f_i$, find the $n$ coefficients $q_i$ of $F_q$ and $p_i$ of $F_p$ such that, with polynomial ...
0
Kyber claims to be CCA secure. CCA schemes cannot be homomorphic (thinking through this may be a useful exercise).
It may be useful to try to work through this particular example with pen and paper by looking at algorithm 5 in the Kyber paper. Note that what is returned is some hash, which you should not expect to have homomorphic properties.
1
You're describing methods of solving LWE via reduction to SVP. In particular:
Sieving and Enumeration are methods of solving exact SVP
Basis reduction is a method of solving approximate SVP
There are additionally ways of solving LWE directly (the classic example is the Arora-Ge attack, which works when the noise distribution is too concentrated).
Daniele ...
5
The Gaussian function $\rho(x)=\exp(-\pi \| x \|^2)$ satisfies the property that if $x,y$ are orthogonal vectors, then $\rho(x+y)=\rho(x) \cdot \rho(y)$. This follows directly from the definition and the Pythagorean theorem. So, we can cancel out the contribution due to $c-c’$, which is orthogonal to every element in $\Lambda$, from both the numerator and ...
0
convert $v-u \cdot s$ to centered representation as described here seems to work
Top 50 recent answers are included
