12
$\begingroup$

Obviously, it's possible to create a commitment scheme comm(r, S) by using a hash function H and computing H(S||r). This scheme is secure under the assumption that H is collision and preimage resistant, which (IMO) is a lighter cryptographic assumption than the discrete log assumption.

So I guess my question is, why are commitment schemes like Pedersen commitments used which do require the latter assumption? What efficiency or security benefits they bring? And are there still any benefits to using hash commitments?

$\endgroup$

2 Answers 2

8
$\begingroup$

The hash-based commitment scheme you are sketching is in fact not secure under collision resistance and preimage resistance of the hash function. For hiding, you need to assume that the hash function you are using behaves like a random oracle (i.e., whenever queried on a new value it returns a uniformly random value from the output domain of the hash function, and for every repeated query it answers consistently).

The random oracle assumption is an idealizing assumption which is considered to be a rather strong assumption compared to the discrete log assumption.

$\endgroup$
4
  • $\begingroup$ Interesting. Out of curiosity, is there a way to massage the hash-based scheme so that it doesn't depend on the RO assumption? And is there a good resource on commitment schemes in general? (I never learned about commitment schemes properly, so...) $\endgroup$ Jan 15, 2018 at 20:06
  • 2
    $\begingroup$ For example, you could have a look at these lecture notes by Yevgeniy Dodis. $\endgroup$
    – dade
    Jan 15, 2018 at 20:40
  • 1
    $\begingroup$ "you need to assume that the hash function you are using behaves like a random oracle" that's what hash functions assume though $\endgroup$ May 15, 2018 at 7:41
  • $\begingroup$ @IanMathWiz, c.f. also this, this, this and this. First link also notes that a Pedersen commitment value is structured not randomized, thus not suitable where structure could be exploited or random model is otherwise required. $\endgroup$ Jan 28, 2019 at 5:38
3
$\begingroup$

Useful lecture note [Lecture Notes Cryptographic Protocols, Version 1.8, February 4, 2023 Berry Schoenmakers]

  1. This commitment scheme by using a hash function is computationally hiding if the hash function be partial pre-image resistance. In the random oracle model, the scheme is therefor hiding as long as guessing a bit string of, say, $k+1$ bits is infeasible.
  2. This commitment scheme by using a hash function is binding and hiding, both computationally, but Pedersen's commitment scheme is information theoretically hiding.
    $commit(u,x)=g^{u}h^{x}$ where $u\in_{R}\mathbb{Z}_{n}$, $x$ is the committed value, $g$ is the generator of the cyclic group $\langle g \rangle$ of order a large prime $n$, $h\in_{R}\langle g \rangle\setminus\{1\}$ a random group element such that $\log_{g} h$ is not known to any party, neither the sender nor the receiver.
  3. Pedersen commitment scheme is homomorphic: the product of two commitments is a commitment to the sum of the commited value.
    $commit(u_{1},x_{1})\cdot_{\langle g \rangle}=commit(u_{2},x_{2})=commit(u_{1}+_{\mathbb{Z}_{n}}u_{2},x_{1}+_{\mathbb{Z}_{n}}x_{2})$
    In some applications, like zero knowledge proofs, these homomorphic properties are useful. Look at this response.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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