Consider the following problem: Alice knows a secret number. She wants to verify whether Bob knows it as well. The simple solution would be for Bob to simply tell Alice the secret number. What if someone (Eve) were listening in on their conversation, and it would be bad if they were to get to know the secret (number)? In such a scenario, what is the scheme that Alice and Bob can follow, that can accomplish the above verification task, even if Eve knew the scheme that they would follow?
First, let’s get a bit more specific about the scheme. Consider it a test that Alice poses to Bob. If Bob has the secret (he is a true Bob), then Alice should decide that he passes the test. If Bob doesn’t have the secret (he is a false Bob), he should fail the test almost always. There is an infinitesimal chance that he passes the test, even if he doesn’t have the secret. We have to accept this, without even specifying what the test is. Why is this so? Given any test that Bob will pass if he has the right number, Bob starts off with guessing the number. With a small probability, his guess is correct, and he has the secret. After that, he can pass any test legitimately. Hence, the scheme tries to do two things: Minimise the probability that a false Bob passes, and minimise the amount of information leaked to Eve.
Let’s consider what happens with a simplistic scheme, in which Bob simply tells Alice the number that he has. If it matches, then Bob passes. Since Eve is aware of the scheme, once the true Bob tells Alice the number, Eve also immediately knows the number. Here, the scheme leaks too much information to Eve. We can quantify the amount of information leaked, by using some information theory. Say that the secret number is written out as a sequence of bits. Now, the information in the secret is simply the number of bits in the secret. If the secret is ‘n’ bits long, then in this scheme, Eve knows all ‘n’ bits of the secret. Hence the scheme fails in maintaining the secret.
Consider a second scheme that works as follows: Alice chooses a random set of ‘k’ bits from ‘n’, and tells Bob the indices of the bits. For example, if n is 1000, and k is 5, the Alice might choose bits 1, 101, 335, 342, and 783. Now, Bob has to respond correctly with the bit values at these indices. A false Bob will succeed with probability 1/(2^5) = 1/32. Also, the scheme gives out 5 bits of information to Eve. Increasing the value of ‘k’ decreases the probability of a false Bob passing the test, but it also increases the amount of information that Eve obtains.
Let’s denote the probability that a false Bob succeeds as P(F), and the amount of information in bits that Eve obtains as I(E). Now, the quantities I(F) = -log2(P(F)), and I(E) are equal in both the above schemes. In the first, they are equal to n, and in the second, equal to k. Can we come up with a scheme wherein I(F) > I(E)?