New answers tagged

0

For all units $u$, ​ $(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)$ ​ is a factorization of $c$, and ​ $a^{-1} \hspace{-0.06 in}\cdot \hspace{-0.04 in}(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)$ ​ and ​ $\left(\hspace{-0.04 in}\left(\hspace{-...


2

The lattice basis $L$ generates every point that is a solution to the congruence $a^{i-1} x_1 - x_i \equiv 0 \pmod{m}$. By definition, the reduced basis $B = \mathsf{LLL}(L)$ also generates the same solutions; it just has shorter vectors. Now suppose we have a set of outputs $\mathbf{y} = y_i$ of the generator, which correspond to the most significant bits ...


0

The statement "I know an $x$ so that $Ax = 0\,\text{mod}\,q$ and $\Vert x\Vert < \beta$" is plainly in NP, so any zkSNARK can give you such a proof, e.g. this paper. Though, this is an argument of knowledge (not a proof of knowledge) but there seems to be little practical difference between the two. If you dislike non-falsifiable assumptions, you could ...


1

Lattice Reductions in Lattice Crypto Well to start off, lattice reductions are of interest in the context of lattice crypto because, as already stated in other answers, they allow us to find short vectors in a lattice, which relates to SVP (finding the shortest vector in a lattice). We care about solving SVP because it is believed that there may be a ...


2

This paper Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications is a good place to start researching. The paper appeared at PKC 2013 so have been peer-reviewed. In addition, there is an upcoming paper at CRYPTO 2016 which looks very related How to prove knowledge of small secrets.


3

The $n$th cyclotomic polynomial $\Phi_n\in\mathbb Z[x]$ is irreducible in $\mathbb F_q[x]$ if and only if $q$ is a generator of $(\mathbb Z/n)^\times$ (proof). Hence, unfortunately, the polynomial $x^n+1$ is never irreducible modulo $q$ if $n>4$ is a power of two: The group $(\mathbb Z/n)^\times$ is not cyclic in that case. Thus it may indeed happen that ...


2

This depends on the factorization of $X^n+1$ modulo $\mathbb{F}_q$. If you have $X^n+1 = \prod_i f_i(X)^{e_i}$ with $f_i$ irreducible and $e_i>0$, then $K = \prod_i \mathbb{F}_q[X]/(f_i^{e_i})$ and $K^\times = \prod_i (\mathbb{F}_q[X]/(f_i^{e_i}))^\times$. An element of $\mathbb{F}_q[X]/(f_i^{e_i})$ is invertible, iff it is invertible modulo $f_i[X]$. ...


0

Most lattice based encryption and/or key-exchange algorithms are based on the LWE or Ring-LWE problems. Typically, their security is shown using a reduction to an average-case instance of the (Ring-)LWE problem. As pg1989 commented, Regev proved a very important hardness theorem for LWE in 2005. Essentially it's a quantum, polynomial-time reduction using an ...



Top 50 recent answers are included