# It is possible to prove this in zero knowledge?

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?

• 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... – SEJPM Aug 7 '20 at 10:31
• @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... – Bean Guy Aug 7 '20 at 10:34
• I am not an expert. Do you need a proof of knowledge or just a proof? – asd Aug 28 '20 at 10:45
• @asd A proof of knowledge, sure. – Bean Guy Aug 28 '20 at 12:37