3
$\begingroup$

Here is the simplified problem:

  1. Alice chooses from a small set of possible values.
  2. Bob guesses which value Alice picked.
  3. Alice reveals what value she picked.

Alice's choice must stay secret initially, until after Bob has made his guess. However, to make sure Alice does not cheat, her choice must be verifiable once it is revealed.

My idea would be to publish a salted hash of the choice at first and publish the salt along with the choice. As far as I understand, there are two possible attacks on this:

  • Bob could try to find the secret choice using the hash: the salt should make up for the small set of valid choices, so this should be equal to a normal a preimage attack.
  • Alice could pick two values and search for two salts so that each pair will generate the same hash. Due to the small number of choices, this should be similar to a birthday attack.

From what I can tell, both attacks do not yet pose a realistic risk to e.g. SHA 512. Would this be a valid approach? Did I miss anything? Is there a better solution?

$\endgroup$
7
$\begingroup$

This is the premise of a commitment scheme. The dramatis personae in this setting are the prover, Peggy, who wishes to prove foreknowledge of a message $m$ to a verifier, Victor, but only later reveal $m$, at which point Victor can verify that Peggy didn't change her mind in the meantime.

For a message $m$, Peggy can commit to $m$ by choosing randomization $r$ and computing a commitment $c = C_r(m) \in \mathcal C$ which she gives to Victor while keeping $m$ and $r$ secret. Later, when Peggy wants to reveal the message, she gives Victor $m$ and $r$, so that Victor can verify $c = C_r(m)$. The commitment $C_r(m)$ should have two properties: it should reveal essentially no information about $m$ to anyone who doesn't know $r$, but it should be essentially impossible to to find $m' \ne m$ and $r'$ such that $C_r(m) = C_{r'}(m')$ and thereby break a commitment.

The first property is hiding, and can be formalized by putting a bound on the advantage of any (possibly cost-limited) adversary $D(c)$ to distinguish the commitment $C_r(m)$ of any message $m$ for uniform random $r$, from a uniform random commitment $c \in \mathcal C$: $\left|\Pr[D(C_r(m))] - \Pr[D(c)]\right|$. If the distribution of $C_r(m)$ is exactly the same as the distribution of $c$, then this advantage is exactly zero, and the commitment scheme is said to be information-theoretically hiding; otherwise it is computationally hiding.

The second property is binding, and can be formalized by putting a bound on the probability of any (possibly cost-limited) adversary $F()$ to find $(r, m, r', m')$ with $m' \ne m$ such that $C_r(m) = C_{r'}(m')$. (If it looks odd to see no parameters in $F$, that's because we usually instantiate it with a random oracle $H$ or a common reference string $\sigma$ and ask that of $F(H)$ or $F(\sigma)$.) If there is exactly one message possible for every commitment, then this probability is exactly zero, and the commitment scheme is said to be information-theoretically binding; otherwise it is computationally binding.

Standard examples:

  • Hash commitments. $C_r(m) = H(r \mathbin\| m)$, or $C_r(m) = \operatorname{HMAC-}\!H_r(m)$, where $H$ is a uniform random function chosen in advance so that Peggy and Victor have no influence over it, modeled as a random oracle in proofs, and implemented by a preimage- and collision-resistant hash $H$ like SHAKE128.

    • Hash commitments are only computationally hiding, but a distinguisher on this can be translated into a preimage attack on $H$, so if $H$ is preimage-resistant then a hash commitment is hiding; conversely a preimage attack on $H$ may enable an adversary to learn a secret commitment value.

    • Hash commitments are only computationally binding, but breaking a commitment on this can be translated into a collision attack on $H$, so if $H$ is collision-resistant then a hash commitment is binding; conversely a collision attack on $H$ may enable an adversary to break a commitment. Consequently, for example, MD5 and HMAC-MD5 are unsuitable for $H$ even though HMAC-MD5 still seems to be a good PRF.

    People sometimes use hash commitments on Twitter because it's convenient and everyone knows how to compute SHA-256 to verify them.

  • Pedersen commitments. $C_r(m) = g^r h^m$, where $g$ and $h$ are elements of a prime-order group $G$ in which discrete logarithms are hard—elements chosen uniformly at random in advance so that Peggy and Victor have no influence over them, modeled as a common reference string in proofs, and implemented by protocols like FIPS 186-4, Appendix A.2.3 using hash functions like SHAKE128. Here, unlike hash commitments, messages are not bit strings but elements of $\mathbb Z/\ell\mathbb Z$ where $\ell$ is the order of the group $G$.

    • Pedersen commitments are information-theoretically hiding, because $r \mapsto g^r h^m$ is a bijection with inverse $c \mapsto \log_g (c/h^m)$, so the distribution of $g^r h^m$ for uniform $r$ is uniform in $G$.

    • Pedersen commitments are computationally binding, because anyone who can compute discrete logarithms in $G$ can find $x = \log_g h$ so that $g^r h^m = g^{r + x m}$ and thereby can break commitments with arbitrary messages $m'$ by choosing $r' = r + x (m - m')$. More specifically: if a Pedersen commitment breaker $F(g, h)$ can find $(r, m, r', m')$ with $m \ne m'$ such that $g^r h^m = g^{r'} g^{m'}$, then $\log_g h = \frac{r' - r}{m - m'}$, so anyone who can break a commitment in this scheme can compute discrete logs in $G$.

    Pedersen commitments are also homomorphic: if $c_0 = C_{r_0}(m_0)$ and $c_1 = C_{r_1}(m_1)$, then $c_0 c_1 = C_{r_0 + r_1}(m_0 + m_1)$, and as such are convenient for fancy cryptography in zero-knowledge proof systems. People sometimes use Pedersen commitments to (accidentally?) put back doors in electronic voting, in an attempt to prove that votes shuffled for anonymity were not forged in the process. Pedersen commitments have a back door if Peggy can choose the elements $g$ and $h$: if Peggy chooses them to have a known relation $h = g^x$, then she can forge commitments as above and commit unrestricted vote fraud.

  • Elgamal commitments. $C_r(m) = (g^r, h^r m)$, where $g$ and $h$ are elements of a prime-order group $G$ in which discrete logarithms are hard—elements chosen uniformly at random as a common reference string, etc., like Pedersen commitments.

    • Elgamal commitments are computationally hiding, because anyone who can compute discrete logarithms in $G$ can, given a commitment $(u, v)$, recover $r = \log_g u$ and $m = v/h^r$. More specifically: an Elgamal commitment distinguisher can be turned into a decisional Diffie–Hellman attack on $G$, so Elgamal commitments are computationally hiding if DDH is hard, although conceivably DDH could be easy while DLOG is hard in $G$.

    • Elgamal commitments are information-theoretically binding, because there is exactly one possible message for each commitment.

    Elgamal commitments are also homomorphic: if $c_0 = C_{r_0}(m_0) = (u_0, v_0)$ and $c_1 = C_{r_1}(m_1) = (u_1, v_1)$, then the elementwise product $c_0 c_1 = (u_0 u_1, v_0 v_1)$ is $C_{r_0 + r_1}(m_0 m_1)$. I don't know who uses Elgamal commitments in practice. Elgamal commitments have a back door if Victor can choose $g$ and $h$: if Victor can choose them to have a known relation $h = g^x$, then from a commitment $(u, v) = (g^r, h^r m) = (g^r, g^{x r} m)$, Victor can recover $m$ by $v/u^x = g^{x r} m / (g^r)^x = m$.

$\endgroup$
  • $\begingroup$ does SHA-1 suitable for hash commitments? $\endgroup$ – kelalaka Aug 25 at 19:01
  • $\begingroup$ No. You need collision resistance. $\endgroup$ – Squeamish Ossifrage Aug 25 at 21:59

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.