What are the pros/cons of using symmetric crypto vs. hash in a commitment scheme?

Question

In a commitment scheme, are there any differences on using a symmetric cipher versus using a hash?

If at the "opening", I have to reveal $r$ (a random number concatenated with the messaged at the time of hashing) and $m$ (the message), why not reveal the key used for encryption for everybody to decipher the message and so confirm it?

It seems to me that both binding and hiding properties of the commitment would be preserved? Is this so?

Any pros/cons of using one over the other that I'm unable to see?

Answer 1

My preference would be to use hash for this purpose. Cons of using symmetric cipher include:

• Symmetric cipher keys are shorter than hashes (128-256 bits), where as hashes are longer (160-512 bits).
• When considering the length of symmetric cipher output, it is commonly short (like 128 bits). This length is often inadequate to protect against birthday attack and other attacks applicable.
• In most uses of symmetric keys, related key attacks are of lesser consideration. However, in this scheme, malicious party could try to use related key attack to find key matching slightly altered message and/or different r. The strongest known related key attacks against AES are $2^{189.7}$ (AES-192) and $2^{99.5}$ (AES-256). These attack complexities are from Wikipedia.

I'm not aware of significant benefit symmetric cipher would provide in this context, except that AES is faster to execute on (many) of recent processors than hashes of the SHA family.

Answer 2

Here is how I interpret your proposed scheme:

• For Alice to commit to a value $M$, she selects a random $r$ and a random $k$. She then computes and publishes the value $C = Encrypt_k( r | M )$

• For Alice to reveal the commitment, she publishes the values $k$, $r$ and $M$. Bob verifies that $Encrypt_k( r | M ) = C$

Assuming that $Encrypt$ is a strong encryption function, Bob gets no information (apart from the length, which might not be a big deal) about $M$ from $C$.

However, what Alice could do is select another key $k'$, and compute $Decrypt_{k'}(C) = (r' | M')$. During the reveal phase, Alice might reveal $k'$, $r'$ and $M'$, and Bob will verify that it all checks out.

You may complain that Alice has little control over the contents of $M'$; however, it still remains that Alice committed to one value, and then substituted a different value when she revealed it; that should be impossible.

However, it is likely possible to fix this; for example, by having Alice include $r$ when she commits, and make it long enough that there are unlikely to be two keys where $C$ decrypts to the same $r$ value.

And, you could hide the message length by having Alice always pad $M$ out to the longest possible value.

So, it would appear to work; however it question remains: what advantage would this have over the simple hash-based commitment scheme?

Answer 3

Yes. $\:$ If one uses a secure symmetric cipher properly, then the commitment scheme will be unconditionally binding, length-revealing, otherwise computationally hiding, and produce commitments whose length is grows linearly with the length of the message. $\:$ If one uses a collision-resistant
hash properly, then the commitment scheme will be unconditionally hiding, computationally binding,
and produce commitments whose length is independent of the message's length.


"If at the 'opening', I have to reveal $r$ (a random number concatenated with the
messaged at the time of hashing) and $m$ (the message), why not reveal the key
used for encryption for everybody to decipher the message and so confirm it?"

As elaborated on in poncho's answer, the second option would not be binding.
In order to use the symmetric cipher properly for commitment,
one would also need to commit to the key in a way that is actually binding.
Additionally, the first option would not be using the hash properly, and if
there is any collision-resistant hash then there is a collision-resistant hash
such that the first option would not even computationally hide all-but-length.