Zero Knowledge for Low Entropy Witness

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?

• Well, you just specified an extractor. So you proved that just sending the statement is a proof of knowledge. The thing is that if you have an NP relation where the witnesses are of constant length (or even of logarithmic length) then the corresponding language is in P. – Maeher Mar 20 '19 at 16:03
• @Maeher, Say that the problem in hand is a ZKPoK and not just a ZK – DaWNFoRCe Mar 21 '19 at 11:37
• Just sending the statement is a ZKPoK. The extractor is trivial. I'm guessing that this is a bit of an XY problem and you actually looking for something else, which you assumed a proof system as envisioned in your question would solve. – Maeher Mar 21 '19 at 12:55
• @Maeher. Sorry if the question is too basic but I still dont see what you mean. If with an extractor you mean that I can extract knowledge, yeah, I would be able to extract knowledge, but I need a Zero Knowledge proof of Knowledge for a low entropy witness.. – DaWNFoRCe Mar 22 '19 at 13:44
• You said that you need a ZKPoK for statements of the form $g^w$ for $w$ with low entropy. And a ZKPoK for that is trivial, as I explained. The fact that an extractor exists means that it is a PoK. The fact that it's trivially simulateable means that it is ZK. – Maeher Mar 22 '19 at 13:59

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.

• It is my understanding that for the Pedersen commitments, in this scheme the prover would also need to publish t, right? – DaWNFoRCe Mar 20 '19 at 17:16
• @DaWNFoRCe: $t$ is the commitment that the prover makes; of course the verifier knows that... – poncho Mar 20 '19 at 17:36
• Thanks so much for the answer. I have a question though, if the prover send s, u, v and t, Then what statement is using the verifier to proof knowledge of x. ? From my point of view it would seem that P is just proving that he knows some x. – DaWNFoRCe Mar 22 '19 at 14:59
• My statement would still be, for instance y = g^x. Then instead of committing to t = g^x * h^r, I only commit to t = h^r. Then my verification step would be s * ( y * t) ^{H(s)}, am I right?. – DaWNFoRCe Mar 22 '19 at 15:47
• @DaWNFoRCe: if you publish $g^x$ (and $g$), and $x$ is low entropy, the verifier can find $x$. That's why you publish $g^x h^r$; the proof shows that you had a specific $x$ (and $r$) in mind when publishing the commitment (or you know the discrete log of $h$ wrt $g$) – poncho Mar 23 '19 at 21:58

$$\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.

• Should this be understood as it is impossible to have a ZKoPK for a low entropy witness using Dlog? – DaWNFoRCe Mar 22 '19 at 13:50
• No, it means that it's trivial. (And quite pointless.) – Maeher Mar 22 '19 at 13:57