Commitment scheme

In cryptography, a commitment scheme is a way for someone to tell people something, and then later reveal what they said.[1] Someone would do this to make sure they can prove who they are. Someone may also do this to make sure that someone does not cheat at a game. This is like putting a letter in an envelope and giving it to someone. You can tell the other person what the letter says. The other person can then open the envelope and know that you wrote the letter.

This is done by using a one-way function to change a string (a name for a list of letters) into a hash. This is called the commit phase. The person can then tell people the hash. Later, if someone needs to prove that they were the one who made the commitment, then they can tell people the string they used. This is called the reveal phase. Other people can then make sure that the string was used to make the commitment.

Examples

[change | change source]

Two people want to flip a coin to decide something. If they are not in the same room, it would be easy to cheat. Person 1 could guess a side, and Person 2 can lie about which side the coin landed. Person 2 can do this because he knows Person 1's guess.

A fix could be using a commitment. Person 1 gives Person 2 a commitment to his guess. Then, Person 2 reveals what side the coin landed on. After, Person 1 can reveal what his commitment was. Person 2 can then make sure that Person 1 is not lying.

References

[change | change source]
  1. Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools, (draft available from author's site). Cambridge University Press. ISBN 0-521-79172-3. (see also http://www.wisdom.weizmann.ac.il/~oded/foc-book.html)