5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ My understanding is that SIS is plausibly hard-to-approximate, which would make the gap versions work for authentication. ​ ​ $\endgroup$
    – user991
    Jul 13, 2016 at 5:50

2 Answers 2

Reset to default
2
$\begingroup$

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!)

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What does your answer has to do with efficient zero knowledge protocols for lattices ? $\endgroup$
    – user27950
    Jul 13, 2016 at 4:45
  • $\begingroup$ 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. $\endgroup$
    – pg1989
    Jul 13, 2016 at 17:41
  • $\begingroup$ They are also very efficient, in general. $\endgroup$
    – pg1989
    Jul 13, 2016 at 17:42
  • $\begingroup$ 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.) $\endgroup$
    – K.G.
    Aug 13, 2016 at 12:43
  • $\begingroup$ 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? $\endgroup$
    – pg1989
    Aug 13, 2016 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.