Rock, Paper, Scissors and Other Ways to Commit Now and Reveal Later

Have you ever played rock, paper, scissors? I bet you have. Well, let’s put the tin lid on it: how would you play through the phone? One thing is clear: the first one to reveal his choice loses for sure. If you shout “rock”, the other will say “paper” and you will lose again and again. The question is: how do you get both of you to commit to a value without revealing it to the other party?

In real life, paper envelopes and boxes are used to stick to a value without revealing it. For example, a judge of a jury writes his verdict on a piece of paper and puts it in a sealed envelope. When the envelopes are opened, you can no longer back out. Can cryptography create an even more secure envelope or digital box? What a question, of course! Let’s see how we can play rock, paper, scissors over the phone thanks to cryptography.

Creating Commitment Schemes Through Cryptographic Protocols

In cryptography, a commitment scheme allows one to stick to a value that will remain hidden until the moment it must be revealed and there will be no going back. Using the box analogy: you keep your message in a locked box and give the box to someone else. Without the key, they cannot read your message. Even you cannot change it, because the box is in their possession. When you give them the key, they will open the box and then, yes, they could read the message. As you can see from this simple example, a commitment scheme consists of two phases:

1. The commitment phase: you keep the message under lock in a box and send the box.
2. The disclosure phase: the receiver of the box opens it with your key and reads the message

Mathematically, this scheme can be represented as follows:

c = C (r, m)

In other words, commitment c is the result of applying a public C function to a random value r and a message m. When the sender subsequently discloses the values of r and m, the receiver can recalculate c and, if it matches the original, will know that there has been no cheating.

To consider it safe, any commitment scheme must satisfy the following two requirements:

1. Secrecy (or concealment): at the end of the first phase, the receiver does not obtain any information about the committed value. This requirement must be met even if the recipient is cheating. Concealment protects the interests of the sender.
2. Unambiguous (or linked): given the message committed in the first phase, the receiver will find the same value in the second phase after the legal “opening” of the commitment. This requirement must be met even if the sender is cheating. Linking protects the interests of the receiver.

A simple way to perform this scheme digitally is by using cryptographically secure hash functions as a C-commitment function. Imagine that our good old friends Alice and Bob want to play rock, paper, scissors on the phone. They can send each other the following information using the generic H hash functionand a random value r_A, as shown in the picture:

At the end of the protocol, Bob needs to verify that the value of the h_A hash sent by Alice is equal to the H ( r_A  || “rock” ) value calculated by himself. If both values match, he knows that Alice has not cheated. The result of this protocol is that Alice loses the game because paper wraps rock.

Let’s follow the above protocol from Alice’s perspective. She first commits to the “rock” value by sending Bob the h_A hash value. For his part, Bob will not yet be able to determine that Alice has committed to that value, as Bob doesn’t know the random r_A value used and Bob is unable to reverse the hash function. The fact that Bob cannot determine which value has been committed is the “secret” (or “hidden”) property of the commitment scheme.

As soon as Bob sends his own “paper” value to Alice, she knows that she has lost, but she is unable to cheat, since for tricking Bob she would have to invent a different value for the random r_A value, let’s say r_A’, that meets H( r_A’ || “scissors” ) = H( r_A || “rock” ). But this fraud would imply that Alice can find collisions in the hash function, which is considered (computationally) impossible (technically, the hash function is required to be resistant to the second preview). This is the “unambiguous” (or “linking”) property of the commitment scheme: that Alice cannot change her mind after the disclosure phase.

The use of hashes as a commitment function is the simplest way to implement a commitment scheme. However, in real applications, the commitment may be required to exhibit some special properties, such as homomorphism, which require more sophisticated mathematical functions, based on variants of Diffie-Hellman, ElGamal or Schnorr. One of the best known examples is Pedersen commitment, which is very simple and has the following property, which is very useful in many situations: if you have committed two messages m₁ and m₂  m1 to the c₁ and c₂ values, respectively, then the product of the two commitments, c₁ × c₂, is equal to the commitment of the sum of the m₁ + m₂ messages.

Applications of Commitment Schemes

Commitment schemes are experiencing new applications thanks to the recent development of new cryptographic protocols:

• Just as we started the article by playing rock, paper, scissors over the phone, we could use versions of the commitment schemes for any other game of chance played remotely: from flipping a coin to playing mental poker and others.
• Another application of the commitment schemes together with the Zero-Knowledge Proof is the construction of zero knowledge databases, in which queries can be made that only reveal whether a property consulted is true or not, such as whether a person is of age or has a sufficient balance in his account, but without revealing either his age or his balance. In this application a special scheme called mercurial commitment is used.
• The commitment schemes are also a key part of a verifiable secrecy sharing scheme: the distribution of secrecy among several individuals is accompanied by commitments of the parts of the secret held by each. The commitments do not reveal anything that could help a dishonest party, but after the commitments of the parties have been revealed, each individual can verify whether the parties are correct.
• Commitment schemes are also being used in optimal and credible auctions, where the bidder must commit to the value of a bid without the possibility of backing out.
• Polyswarm uses commitment schemes along with smart contracts at Ethereum. Polyswarm is a decentralised threat intelligence marketplace where threat detection is encouraged by putting money into the game – NCT. Different manufacturers’ engines can bet money based on trust in their own detections. They commit their verdict by calculating the Keccak hash on the sample of potential malware along with a random number. This hash represents their commitment on the artefact. After an engine has been pronounced, there is no turning back. Once the commitment window has been closed, during which the engines could make their predictions, they reveal their original verdict and their random number. Those who made correct evaluations are rewarded, while those who failed in their prediction lose their bets. In this way, Polyswarm rewards honest market participation, encouraging quality and unique malware detection.

Online auctions, Internet gambling, smart contract signing, secure database searches, secure multiparty computing, Zero-Knowledge Proof, … there are many applications that require information to be securely hidden until it can be revealed. As interest in public computing environments, such as blockchain, grows, commitment schemes will continue to provide confidence and encourage new secure technologies to flourish.