1
$\begingroup$

In the slides to my information security class it is stated without explanation that a encryption-based commitment scheme defined as follows is broken:

  • Commit: P outputs c = Enck(m)
  • Reveal: P sends k to V. V decrypts c and learns m = Deck(c)

Similarly, a hash-based commitment scheme (using cryptographic hash function H) defined as follows is also stated to be broken:

  • Commit: P outputs c = H(m)
  • Reveal: P sends m to V. V verifies that c = H(m).

Why are these schemes broken with respect to hiding and binding?


The only reasons I can think of that these schemes might be broken are the following:

  • In the encryption-based scheme, the encryption might reveal something about the length of the message, breaking the principle of hiding. However, this could be addressed by padding the messages to a fixed length.
  • In the hash-based scheme, two hashes might collide, breaking the principle of binding.

Are there any other reasons these schemes are not valid commitment schemes?

$\endgroup$
  • 3
    $\begingroup$ Note that there's nothing wrong with a hash based commitment scheme; the question just implemented it wrong (on purpose). The correct way is to choose a fixed length nonce $n$, and the commitment is $H(n || m)$; to open, you reveal $n$ and $m$ $\endgroup$ – poncho Jul 27 at 13:32
4
$\begingroup$

The second construction is trivially not hiding. It is easy to verify a guess $m'$ just by recomputing $H(m')$ and comparing the result with the commitment.

The first construction is a bit trickier. If it is a CPA secure encryption scheme, then it is certainly hiding. However it may not be binding.

It is easy to construct secure encryption schemes, where different keys decrypt the same ciphertext to two different messages. In fact most symmetric encryption schemes without authentication definitely fall into this category. As do public key encryption schemes such as ElGamal encryption.

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