In cryptography, a commitment scheme or a bit commitment scheme is a method of sending hidden information such that it is verifiable in spite of possible later bias from either the sender or the receiver. Commitment is related to digital timestamping and zero knowledge proof and finds application in electronic cash, electronic voting and online games. The German Lorenz cipher machine Cryptography or cryptology is a field of mathematics and computer science concerned with information security and related issues, particularly encryption and authentication. ... Digital timestamping is the process of securely keeping track of the creation and modification time of a document. ... In cryptography, a zero-knowledge proof is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the verity of the statement. ... Electronic money (or digital money) refers to cash and transactions using electronic means, encompassing the use of computer networks (such as the Internet) and digital stored value systems. ... Electronic voting machine used in all Brazilian elections and plebiscites. ... A terrorist from the online game Counter-Strike: Source Online games refer to video games that are played over some form of network, most commonly the Internet. ...

An example of when this is necessary: Suppose two people, Alice and Bob, have opposed interests; and they decide to resolve their dilemma via coin flipping. If Alice flips the coin, then both Alice and Bob can see the coin and are committed to live by its judgment -- no problem has yet occurred. Modifying the example, suppose that Bob cannot witness the outcome -- perhaps he is blind; or perhaps he is on the other side of a telephone. Alice is not necessarily trustworthy; so perhaps Alice will lie about what side actually came up. Coin flipping or coin tossing is the practice of throwing a coin in the air to resolve a dispute between two parties or otherwise choose between two alternatives. ...

A commitment scheme allows Alice to commit to one option without telling Bob about it. Then Bob can call the coin-toss without knowing what Alice committed to; and finally, both Bob and Alice can know both the outcome of the coin toss and the outcome of Bob's knowledge without dispute.

A very simple commitment scheme can be provided by simply involving a trusted third party to hold the hidden knowledge in a sort of escrow. As an example, a secure computer might be entrusted with Alice's message under a username and password, with some sort of timestamp or no-edit policy. Then Alice could provide the username to Bob, Bob could provide his guess to Alice, and after all that, Alice could provide the password to Bob as well. Escrow is a legal arrangement whereby a thing (often money, but sometimes other property such as art, a deed of title, or software source code) is delivered to a third party (called an escrow agent) to be held in trust pending a contingency or the fulfillment of a condition or...

A useful way to visualize a commitment scheme is to think of Alice as putting the message in a box, securing the box with a lock to which only she has the key, and giving the box to Bob. The challenge, of course, is to find mathematical constructions that capture the behavior of the box, lock and key.

A simple commitment scheme is the following: if b is the commitment, Alice generates a large random number r and gives to Bob a hash of b concatenated with r. To open her commitment, Alice reveals b and r thus letting Bob recalculate the hash and compare it with the hash given him earlier to make sure Alice didn't cheat. In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...

A commitment scheme can either be perfectly binding (it is impossible for Alice to alter her commitment after she has made it, even if she has unbounded computational resources) or perfectly concealing (it is impossible for Bob to find out the commitment without Alice revealing it, even if he has unbounded computational resources) but not both.

A perfectly binding scheme

Alice chooses a group of prime order p, with generator g. In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ...

Alice randomly picks a secret value x from 0 to p − 1 to commit to and calculates c = g^x and publishes c. The discrete logarithm problem dictates that from c, it is computationally infeasible to compute x, so under this assumption, Bob cannot compute x. On the other hand, Alice cannot compute a x' <> x, such that g^x' = c, so the scheme is binding. In abstract algebra and its applications, the discrete logarithms are defined in group theory in analogy to ordinary logarithms. ...

This scheme isn't perfectly concealing as someone could find the commitment if he manages to solve the discrete logarithm problem. In abstract algebra and its applications, the discrete logarithms are defined in group theory in analogy to ordinary logarithms. ...