# 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
Commented Jul 13, 2016 at 5:50

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
Commented Jul 13, 2016 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. Commented Jul 13, 2016 at 17:41
• They are also very efficient, in general. Commented Jul 13, 2016 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.
Commented Aug 13, 2016 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? Commented Aug 13, 2016 at 16:56