1
$\begingroup$

Suppose I construct a Pedersen commitment as $g^m h^r$. I could pick the randomness in a "pseudo-random" fashion, such that $r = H(m)$. My questions are as follows:

  1. Given that $H$ is collision-resistant, does the security properties of the Pedersen commitment still hold? (i.e. is it still hiding and binding?)
  2. Is there a way to construct a Sigma protocol which would prove in Zero-knowledge that a) I know $m$ and b) The commitment randomness is picked such that $r=H(m)$?

Edit: I do not require some specific hash function. Any pseudo-random function would serve my purposes.

$\endgroup$
  • $\begingroup$ The commitment is now deterministic while being publicly computable. Therefore it's trivial not hiding. $\endgroup$ – Maeher Mar 5 at 8:32
3
$\begingroup$

This is no longer a secure commitment. Note that there should not be any way to efficiently verify if a given commitment value $c$ is to a message $m$. However, once you derive the randomness in this way, an attacker could try to guess $m$ and verify if this guess is correct by checking if $g^m\cdot h^{H(m)} = c$. Thus, this is not a secure commitment scheme.

| improve this answer | |
$\endgroup$
1
$\begingroup$

Given that $H$ is collision-resistant, does the security properties of the Pedersen commitment still hold? (i.e. is it still hiding and binding?)

Hiding. No, the resulting commitment scheme cannot possibly be hiding anymore, because the commitment function $m \rightarrow g^mh^{H(m)}$ is a deterministic function. Recall that by definition, a commitment scheme is hiding if no polytime adversary can distinguish commitments on two messages $(m_0,m_1)$ of his choice; that is, the adversary $A$ chooses $(m_0,m_1)$ and receives a commitment $c$ which commits to one of the $m_i$ picked at random. $A$ wins if he guesses $i$ correctly. This is trivial: $A$ simply checks whether $c = g^{m_i}h^{H(m_i)}$ for $i=0,1$, and answers the $i$ that matches.

Binding. Yes, the commitment will still be binding under the discrete logarithm assumption. The same proof as for the standard Pedersen commitment works; note that the proof never uses anything specific about the structure of the randomness $r$. In particular, the commitment remains binding independently of any property of $H$ ($H$ could be the all zero function or the identity).

Some form of hiding. Even though the commitment is clearly not hiding, your intuition is correct in the sense that $m \rightarrow g^mh^{H(m)}$ provides some form of "hiding" if

  • $m$ is a high entropy message, and
  • $H$ is a sufficiently good hash function.

In fact, the same idea as the one underlying your construction forms the basis of an important field of research which aims at constructing the best possible deterministic encryption. The fundamental approach for building strong deterministic encryption scheme is the same as yours: encrypt $m$ with random coins $H(m)$. The core questions studied in the papers on deterministic encryption are:

  1. What security notion can be achieved this way? Clearly the resulting scheme cannot be IND-CPA, the same way that your scheme cannot be hiding
  2. What properties should $H$ satisfy to achieve the "best possible" security notion?

Deterministic encryption was introduced here; one of the main motivation is that it allows searching in databases of ciphertexts, so you can build encrypted databases which still allow for keyword search. Their approach follows the method you suggest. The security notion they achieve is privacy for high min-entropy plaintexts (see the paper for the exact definition), which is a form of one-wayness (it is hard to recover a high entropy message $m$ from an encryption of $m$). This is the notion that your construction should achieve as well, if the underlying hash is strong enough.

As for the security that $H$ should satisfy, proving privacy for high min-entropy plaintexts under any standard property of $H$ remain a long-standing and very hard open problem. What was proven in the paper above is that $\mathsf{Enc}(m, H(m))$ satisfies privacy when $H$ is modeled as a random oracle.

Is there a way to construct a Sigma protocol which would prove in Zero-knowledge that a) I know $m$ and b) The commitment randomness is picked such that $r = H(m)$?

Sure, you can prove any NP statement in zero-knowledge via generic methods. However, a Sigma protocol for this statement would be extremely inefficient, unless $H$ is a very simple algebraic function (e.g. a polynomial over $\mathbb{Z}_p$, if the group is of order $p$). If $H$ treats its input as a bitstring, the resulting scheme will be very complex - although there have been some attempts at making exactly this kind of schemes more efficient, see here.

| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.