New answers tagged

2

It depends on the exact domain of the hash function and the quality of the SIS solution, i.e., its norm (and the choice of norm itself). Suppose the hash domain is $\{-d, \ldots, d\}^m$, i.e., vectors of $\ell_\infty$ norm at most $d$. Then any nonzero vector in Ajtai's lattice having Euclidean norm at most $d$ collides with the all-zeros input. (Actually, ...


0

It is much easier to determine the structure of the lattice when it is given by basis of short, nearly orthogonal vectors. For example, what does the set of lattice points in $$\Lambda = \mathbb{Z}(-3,4) + \mathbb{Z}(5,-7)$$ look like? What about $$\Lambda = \mathbb{Z}(1,0) + \mathbb{Z}(0,1)?$$ For both, it is $\mathbb{Z}^{2}$, but this was much easier to ...


2

Your best bet at the moment are probably the lattice-based key exchange described in the "Post-quantum key exchange – a new hope" paper. You can also find different implementations. C code can be found on Peter Schwabe's homepage. For signatures, if you want to use lattices, you will end-up with BLISS or BLISS-B both of which are implemented by various ...


2

Let $\left\{\vec{b}_1,\ldots,\vec{b}_n\right\}$ ba a lattice basis and $\left\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_n\right\}$ be its Gram-Schmidt orthogonolization. Here are some reasons: It helps computing a reduced basis (an equivalent basis with shorter vectors) using LLL or BKZ algorithm, The span of $\{\vec{b}_1,\ldots,\vec{b}_i\}$ is equal to the ...


2

Let ${\bf A}$ be a $n\times m$ matrix with $n|m$ and rank $n$. Write down ${\bf A}$ as $m/n$ blocks of $m\times m$ matrices as follows: $${\bf A}=\left[{\bf A}_1|\cdots|{\bf A}_{m/n}\right].$$ If ${\bf x}\in\Lambda({\bf A})$, then $${\bf 0}={\bf A}{\bf x} = \sum_{i=1}^{m/n}{\bf A}_i{\bf x}_i,\pmod{q}$$ where ${\bf x} = \left[{\bf x}_1^T|\cdots|{\bf ...



Top 50 recent answers are included