Zero Knowledge for Low Entropy Witness

Question

For any PPT prover ($p$) and verifier ($v$), imagine I have a low entropy witness, say smaller than $2^8$. Now, let us say I have a dlog statement in the form of $y = g^w$. Theory says I could use a sigma protocol such that $p$ can prove to $v$ that it knows $w$. I could also make use of the fiat shamir transform to make it non-interactive.

This is not the case when the entropy of the witness is low as in this example. In both cases I could simply enumerate the $256$ possible witness and use the response and commitment to check to which one it might correspond i.e:

For a commitment:

$t = g^v$

A challenge $c$ and a response:

$r = t + c \times x$

It is obvious to see that if I have $r, \space c$ and $t$ I can recover $x$. The same happens if we were to use Pedersen commitments instead.

I assume this is a common problem for all dlog based ZKPoK, but I am not sure, nor I do not know what should I use instead.

The one liner in this case is: How can I prove Knowledge when the witness entropy is that low?

Answer 1

Pedersen commitments would appear to address your problem.

A Pedersen commitment is a value $t = g^w h^r$ (for the witness value $w$ and a random value $r$); someone cannot recover $w$ from that value (actually, even a computationally unbounded adversary cannot do that). This is true even if $w$ is of low entropy.

And, it is straight-forward to come up with a proof of knowledge that someone knows a $(w, r)$ that make up $t$, such as:

• Prover selects random $x, y$, and computes $s = g^x h^y$, $u = x + w \cdot H(s)$, $v = y + r \cdot H(s)$
• Prover publishes $s, u, v$
• Verifier accepts if $g^u h^v = s t^{H(s)}$

where $H$ is a hash function into the appropriate range.

This is a simple extension of a Schnorr proof.

Answer 2

$\newcommand{\NP}{\mathsf{NP}}\newcommand{\lang}{\mathcal{L}}\newcommand{\rel}{\mathcal{R}}\newcommand{\bin}{\{0,1\}}$ Let $\lang\subseteq\bin^*$ be any $\NP$ language with a corresponding $\NP$ relation $\rel$. Now assume that every statement in $\lang$ has a short witness, i.e. a witness of constant (as in your question) or at most logarithmic length. I.e. it holds that $$ \forall\,x \in \lang\ \exists\,w\in\bin^{\log(|x|) }. (x,w)\in\rel $$

By definition of an $\NP$ language, it is possible to check whether $(x,w)\in\rel$ in polynomial time for any pair $(x,w)$. Say it takes at most time $p(|x|)$ to decide. It thus follows that¹ we can give a polynomial time algorithm for deciding $\lang$ as follows: \begin{align} &\underline{\mathcal{A}(x)\hspace{6em}}\\ &\text{for } w\in\bin^{\log(|x|)}\\ &\quad \text{if } (x,w)\in\rel \\ &\quad\quad \text{return } 1\\ &\text{return } 0 \end{align}

It is easy to see that this algorithm is deterministic, always decides correctly and runs in time at most $$2^{log(|x|)}\cdot p(|x|) = |x|\cdot p(|x|)$$ and therefore in polynomial time. We can thus conclude that any such language is in fact in $\mathsf{P}$.

And for any language there exists a trivial proof system, that consists of just sending nothing. The verifier can simply verify the statement themselves. Note that this proof system is trivially sound (as the prover cannot influence the verifier's decision at all), as well as trivially zero knowledge, since the simulator just needs to "simulate" the empty interaction.

Now you specifically asked about proofs of knowledge. It is easy to see that this is in fact also formally fulfilled here, as the algorithm $\mathcal{A}$ needs to be modified only slightly to extract $w$ from $x$ alone.

\begin{align} &\underline{\mathsf{Ext}(x)\hspace{6em}}\\ &\text{for } w\in\bin^{\log(|x|)}\\ &\quad \text{if } (x,w)\in\rel \\ &\quad\quad \text{return } w\\ &\text{return } \bot \end{align}

---

¹As you in fact observed correctly.