next up previous
Next: Not binding Up: Application of one-way functions Previous: Application of one-way functions

Not concealing

The reason the straightforward implementation is not concealing is related to the dictionary attack discussed in the context of password security. Very often the set of possible secrets is a relatively small set. Once you have received c=f(s) from me, you can try all possible secrets, applying f to each one and checking whether the corresponding output matches c. In this way, you can learn something about the secret before the decommit stage.

Suppose, for example, you know in advance that my secret is either 0 or 1. This is a frequent case in applications and is called ``bit commitment'' because I am committing to a single bit. If I were to send you c=f(s), you could simply calculate f(0) and f(1) and see which one yields c as a result.

More generally, as in the case of passwords, even if the range of possible secrets is large, you might have some knowledge about the choice of secrets I am likely to make. If there is a small subset of possible secrets that you suspect I might select among, you can try each of these likely candidates. Of course, your suspicion might be incorrect: I might have chosen none of these. However, if there is a nonnegligible chance that your suspicion is accurate, we should consider the security to be undermined.

For example, consider a number-guessing game. Let us assume that any number from 1 to tex2html_wrap_inline851 is allowed. I commit to my guess, then you reveal your number, and then I reveal my guess. I win if my guess is within tex2html_wrap_inline853 of your number. Can you figure out my guess before I reveal it? In principle, once you have the commitment tex2html_wrap_inline855 , you could try all tex2html_wrap_inline851 possible numbers, applying f to each one and comparing the result to c. You might feel disinclined to do all that work. However, if you knew that I might have a preference for guessing the birthdates of friends, you could with little work have a reasonable shot at determining my guess. In some applications even a reasonable shot gives you a substantial advantage.

In a sense, the problem is that there is not enough unpredictability in my secret. To remedy the problem, more randomness is needed in the protocol. Here is the improved protocol.

Before I decommit, you have no idea what nonce I chose. Since there are so many possibilities for the nonce and therefore so many possibilities for the combined number k, you cannot try all possibilities: it would take you too long. Thus this modified protocol seems to be secure against the kind of attack we have considered.

By what formula should the numbers s and k be combined? The precise method of combining is not so important as long as both parties, you and I, agree in advance on the method so there is no confusion (intended or otherwise) as to my secret once you know k. For purposes of this class, an easy and reasonably effective way of combining is as follows. Suppose the secret is guaranteed to be a nonnegative number less than T. (In the bit-commitment example, T=2 and in the number-guessing example, tex2html_wrap_inline905 .) The value of T is agreed upon in advance; it is considered part of the protocol and is therefore known to all parties. One can combine the nonce r with the secret s using the formula

displaymath913

It follows from elementary number theory that because s is nonnegative and less than T, the remainder when k is divided by T is s. That is, s is the mod T standard name of k.


next up previous
Next: Not binding Up: Application of one-way functions Previous: Application of one-way functions

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