Let $\mathcal{R}_q = \mathbb{Z}_q/\langle x^n + 1 \rangle$, with $n$ a power of $2$. Suppose that we sample $\mathbf{r} \leftarrow \mathcal{R}_q^m$ uniformly at random with the property that $0 < ||\mathbf{r}|| \leq \beta$. Given $(\mathbf{A} \leftarrow \mathcal{R}_q^{n \times m}, \mathbf{s} = \mathbf{Ar})$, find $\mathbf{r}'$ such that $\mathbf{Ar'} = \mathbf{s}$ and $0 < ||\mathbf{r}'|| \leq \beta$. This is problem known as Search Module-LWE problem.

What I want to do is proving in zero knowledge that I have such an $\mathbf{r}'$ without revealing any information about it (assuming that the verifier has access to both $\mathbf{A}$ and $\mathbf{s}$). Is it possible to do that?

  • $\begingroup$ In theory it is possible in "polynomial-time" to do this (because the underlying formal language is in NP). Though it might be a bit tricky to come up with a protocol that is efficient enough for practical usage... $\endgroup$ – SEJPM Aug 7 '20 at 10:31
  • $\begingroup$ @SEJPM Yeah, I know. I just wanted to know if there is already some in the literature, because I have not been able to find one... $\endgroup$ – Bean Guy Aug 7 '20 at 10:34
  • $\begingroup$ I am not an expert. Do you need a proof of knowledge or just a proof? $\endgroup$ – asd Aug 28 '20 at 10:45
  • $\begingroup$ @asd A proof of knowledge, sure. $\endgroup$ – Bean Guy Aug 28 '20 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.