# ZK Proof for SIS

Let $$A x = 0 \bmod q$$ with $$\Vert x \Vert < \beta$$ as part of a lattice SIS problem. Does there exist an efficient zero knowledge proof of knowledge for such a solution?

My idea is to use it for an authentication protocol. But all ZK protocols I've seen so far are promise or gap problems. Due to this gap, I cannot see how to build an authentication protocol. Because an attacker which has a solution $$x$$ with $$x > \beta$$ but $$x$$ inside the gap could also convince the verifier.

• My understanding is that SIS is plausibly hard-to-approximate, which would make the gap versions work for authentication. ​ ​ – user991 Jul 13 '16 at 5:50

## 2 Answers

If you are interested in lattice-based (..and non-interactive..) zero knowledge, the state-of-the-art is from a 2008 paper (yes, 2008..) found here: https://web.eecs.umich.edu/~cpeikert/pubs/latticeNISZK.pdf

Getting NIZK from lattices is a major open problem. (As far as we know, you might have to go all the way up to multilinear maps and IND obfuscation for P/poly to get a "lattice-like" form of NIZK.)

If you need more than the SZKs from that paper, you must use a non-SIS, non-LWE solution (or, you could go for the big bucks and build NIZK from LWE yourself!)

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 start with a generic ZKP for your SIS statement (built from e.g. this nice recent paper), then compile it into a proof of knowledge using a standard transform.

• What does your answer has to do with efficient zero knowledge protocols for lattices ? – user27950 Jul 13 '16 at 4:45
• Do you understand what a zero-knowledge proof is? They are generic tools that can be used to prove many different kinds of statements in zero knowledge, including statements about lattices. – pg1989 Jul 13 '16 at 17:41
• They are also very efficient, in general. – pg1989 Jul 13 '16 at 17:42
• Often, you are interested in lattice-based cryptography because you want to avoid d.log.- or factoring-based cryptography (probably because of quantum computers). In that case, arguments of knowledge relying on d.log-based cryptography may not be what you want. (There are exceptions, I know.) – K.G. Aug 13 '16 at 12:43
• The OP asked for "an efficient zero knowledge proof of knowledge for [a solution to SIS]", not specifying which hardness assumptions are valid building blocks for the ZKPOK, right? Did I misunderstand the question here? – pg1989 Aug 13 '16 at 16:56