next up previous
Next: Not concealing Up: Contents Previous: Salting the password file

Application of one-way functions to commitment

I write a secret on a piece of paper, seal it in an envelope, and hold the envelope in front of your eyes. At this point,

concealing:
You don't yet know what is written on the paper, and
binding:
I cannot change what I have written on the envelope without you noticing.

At some later point, I hand you the envelope and you can determine my secret.

The above scenario is the model for a commitment protocol, a basic element in cryptographic applications. It arises in a surprising variety of settings. The first stage of the protocol is the commit stage. The second stage, in which I make it possible for you to learn the secret, is called decommitment (this is a terrible choice of term). Between the first and second stage, typically you make some kind of decision and announce your decision to me. The concealing property of the commitment protocol ensures that you cannot base your decision on my secret, and the binding property of the protocol ensures that I cannot change my secret based on your announced decision.

How can commitment be implemented digitally? That is, how can the same functionality be achieved if you and I are on opposite sides of the earth, and are connected by the Internet? Perhaps the method that most readily comes to mind involves encryption. For the commit stage, I choose a random key, encrypt my secret with that key, and send you the cyphertext. For the decommit stage, I send you the key, allowing you to decrypt the cyphertext.

The problem with this approach to implementing commitment is that at least some encryption schemes are not binding. That is, they don't reliably prevent me from changing my secret once I hear your decision. The problem is that the choice of key gives me an extra little control over what you get when you decrypt. I can choose which key to give you depending on your decision. This problem is particularly troublesome if the encryption scheme is the one-time pad: even after I've sent you the cyphertext, I am not bound to any particular secret, since by an appropriate choice of the key I provide you I can make the cyphertext decrypt to whatever I want.

This example demonstrates that when we use encryption to implement commitment, there is a conflict between the two goals of commitment, the concealing property and the binding property. Use of a perfectly secure encryption scheme ensures that the concealing property holds and the binding property does not hold. However, there are encryption schemes that can be used (in conjunction with another trick) to achieve both properties.

In this handout, our solution will be to do without keys, thereby avoiding the additional freedom provided to me by the choice of keys. A one-way function is a way to conceal without keys. A basic (and, as we will see, flawed) implementation of commitment using a one-way function f is as follows. (Remember that we agree on the protocol in advance, including the choice of one-way function.)

This implementation seems to realize both properties of commitment. Since f is a one-way function, knowing the value c does not enable you to determine s. Since I have already sent you the value of f(s), I cannot later change my mind and send you an alleged secret that differs from s.

In fact, both these inferences are fallacious, and under some circumstances the above protocol is neither concealing nor binding. However, by making some slight changes we can achieve both these properties.




next up previous
Next: Not concealing Up: Contents Previous: Salting the password file

Lisa Eckstein
Thu Nov 21 01:20:27 EST 1996