Cryptography
commitments universal-composability
Updated Thu, 23 Jun 2022 05:44:15 GMT

Is this a UC-secure commitment scheme in the ROM?

To prove UC-security (universally composable security) of a commitment scheme, we must show that a commitment scheme is extractable and equivocal.

That is, we must construct a simulator that is able to extract the commitment of an adversary corrupting the sender (extractability) and construct a simulator that is able to open anything for an adversary corrupting the receiver given a commitment (equivocal).

Consider this commitment scheme in the Random Oracle Model:

1. Commit phase: The sender computes \$c=\mathsf{RO}(M)\$ where \$\mathsf{RO}\$ is the random oracle and \$M\$ the message to commit. It sends \$c\$ to the receiver.
2. Opening phase: The sender sends \$M\$ to the receiver. The receiver checks if \$c=\mathsf{RO}(M)\$.

It seems to me that this protocol is UC-secure since the simulator has control of the random oracle. Thus, it can always know the message \$M\$ by looking at the calls to the random oracle. The simulator can also open any message \$M'\$ it wants by returning \$c\$ to future queries of \$M'\$ by the adversary corrupting the receiver.

My questions are:

1. Is this correct?
2. If so, what is the point of constructing UC-commitment schemes in the ROM like https://eprint.iacr.org/2014/908.pdf and https://link.springer.com/content/pdf/10.1007/978-3-540-24638-1_4.pdf since this protocol seems much more efficient than the others.

Thank you!

Solution

1. No, your construction is insecure, specifically it fails to be hiding. A receiver who has a guess of \$M\$ can simply check whether \$H(M)=c\$ since \$H\$ is public. You can see that your suggested simulation strategy fails when the adversary has already queried \$H\$ on \$M\$ before the simulator learns that the commitment should hold \$M\$. The argument to \$H\$ should have high entropy even conditioned on a correct guess of \$M\$. Change the construction to \$H(M\|r)\$ for long random \$r\$ and you have the standard folklore commitment in the random oracle model.

2. Naively using a random oracle in the UC model is kind of like cheating. You get a totally independent random oracle for each protocol instance. It's not a great model for a supposedly public object. Those papers you reference try to use a random oracle in a less "cheaty" way, so their protocols have to work harder. Also at least the first paper avoids having the simulator program the oracle's outputs (non-programmable random oracle model) which is often seen as more palatable.