Tag Info

New answers tagged

2

Sure you can do. There are many lattice attacks, using your second assumption, to ECDSA (which also applied to DSA). For instance see Smart and Howgrave-Graham and Shparlinski and Nguyen. All the lattice attacks base on finding small solutions (for the ephemeral key $k$ and the private key $a$) to the signing equation $sk-ra\equiv H(m)\pmod q.$ If you have ...


0

A vector u mod a matrix B is ​ u ± Bv . ​ ​ ​ We are modding an element of the vector space's additive group by the range of the restriction of B to vectors whose entries are all integers. The parallelepiped given by B's columns is a fundamental domain for the range of that restriction. ⌊⃗c×B−1⌉ is probably rounding each entry of c×B−1 to the nearest ...


1

The basic idea is to take random (Gaussian) integer combinations of the given LWE samples, and add a little "smoothing" noise. This will result in new samples which are statistically close to LWE samples with the same secret, but with a somewhat wider error distribution (by a factor of $\tilde{O}(n)$ for typical parameters). This is essentially Regev's ...


3

(I am one of the authors of the paper you're asking about. The isomorphism $\varphi$ you wrote is the intended one.) The key observation is that a Gaussian $D_r$ of parameter $r$ over $\mathbb{C}$ is "spherical," i.e., it is the sum of independent Gaussians (both of parameter $r$) for the real and imaginary components, and so is invariant under rotations ...


4

When decrypting in lattice-based cryptosystems, one computes a value $v \in \mathbb{Z}_q$ that is guaranteed to be congruent to a "small" integer $e \in \mathbb{Z}$, where $e$ encodes the message (e.g., as the parity of $e$ modulo 2). By using the integer representatives between $-q/2$ and $q/2$, one can recover the small integer $e$ (and thereby recover ...


1

My understanding is that the coefficients of polynomials used in lattice crypto are often sampled from a discrete Gaussian distribution. A Gaussian is centered at 0, which would explain why the elements are represented as elements from the set $\{\frac{−(q−1)}{2},…,\frac{(q−1)}{2}\}$, as you mentioned.



Top 50 recent answers are included