Let $A_1$ and $A_2$ two $m \times n$ matrices defining SIS problems.
Does there exist a zero knowledge proof that two short solutions are the same, i.e.
$$y_1 = A_1 x $$
$$y_2= A_2 x $$
$$ \Vert x \Vert < \beta$$
$\begingroup$
$\endgroup$
4
-
$\begingroup$ You could use a standard Socialist Millionaire's problem solution to prove that both parties share the same $x$. $\endgroup$– SEJPMJul 3, 2016 at 18:16
-
2$\begingroup$ Do you know that ZK proofs exist for every NP problem? Or are you looking for practical ones? $\endgroup$– fkraiemJul 3, 2016 at 18:16
-
$\begingroup$ @fkraiem : I mean practical ones. $\endgroup$– user27950Jul 3, 2016 at 18:55
-
$\begingroup$ @SEJPM I don't think that this is the question. A single party holds both matrices and wants to prove to someone else that they have the same solution. $\endgroup$– Yehuda LindellJul 4, 2016 at 4:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered Jul 4, 2016 at 5:20