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 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
of your number. Can you
figure out my guess before I reveal it? In principle, once you have
the commitment
, you could try all
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, .) 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
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.