4
$\begingroup$

I want to implement non-interactive Bit Commitment scheme for messages of arbitrary length.

And I am curious, what is the reason of using Pedersen Commitment scheme over Salted Hash (in other words HMAC).

Example is coin flipping protocol from Wikipedia:

  1. Alice "calls" the coin flip but only tells Bob a commitment to her call,
  2. Bob flips the coin and reports the result,
  3. Alice reveals what she committed to,
  4. Bob verifies that Alice's call matches her commitment,
  5. If Alice's revelation matches the coin result Bob reported, Alice wins

With HMAC Alice calculates a hash of her call at step 1 and reports it to Bob, keeps key (salt) in secret. During reveal step (3) she reveals a key.

With Pedersen Commitment scheme she reports her commitment at step 1, then reveals her call at step 3 with additional data, related to scheme.

$\endgroup$
4
$\begingroup$

In many applications, especially in zero-knowledge proofs, we need commitment schemes that are additively homomorphic. Pedersen commitment schemes do have this property, hash-based commitment schemes don't.

If we do Pedersen commitments on elliptic curves for performance reasons, where we fix two points $P$ and $Q$ on a curve, we can define:

$\text{commit}(s,r) := sP + rQ$

Or, in the more general form if we fix points $P_1, \ldots, P_n$, $Q$ on the curve, we can commit to multiple values $s_1, \ldots, s_n$ at once:

$\text{commit}(s_1, s_2, ..., s_n, r) := s_1P_1 + s_2P_2 + ... + s_nP_n + rQ$

This Pedersen commitment scheme is additively homomorphic. Indeed, in the $\text{commit}(s,r)$ case for just one value, we can commit to the addition of two values $s_1$ and $s_2$:

$\text{commit}(s_1 + s_2, r_1 + r_2) = (s_1 + s_2)P + (r_1 + r_2)Q$

which is equal to

$(s_1P + r_1Q) + (s_2P + r_2Q) = \text{commit}(s_1, r_1) + \text{commit}(s_2, r_2)$

It also holds true for the simultaneous commitment of $n$ values $s_1, \ldots, s_n$.

Hash-based schemes where

$\text{commit}(s,r) := H(s)P + rQ$

are not additively homomorphic, because:

$\text{commit}(s_1+s_2, r_1+r_2) \ne H(s_1 || s_2)P + (r_1+r_2)Q$

See also:

$\endgroup$
5
$\begingroup$

In this case, there probably is no difference.

The Pedersen Commitment scheme is often used in cryptographic protocols because:

  1. It allows zero-knowledge proof to prove some properties of the committed value.
  2. It is perfectly hiding, which can be important in proving the security of the protocol.

Hash based commitment schemes do not have the above two properties. However, they may be more efficient and are preferable in certain scenarios.

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