To fix ideas, suppose you're sitting at a dinner table with some friends, among whom a pregnant couple. They know, but want to keep it a secret, whether their child will be a boy or a girl, which is why they use the gender-neutral 'it' when referring to the child. At some point during the conversation one of the partners uses a gender-specific pronoun. You are the only one who notices it, and at this point you are sure that you know the secret. Nobody else knows you know.
You tell the couple about what you heard them say, but they don't believe you. You want to convince them that you know the gender, but out of respect for their secret you don't want to tell it straight away so that everyone could hear it. Let's call the supposed procedure to convince them the 'protocol'.
Clarifications and restrictions
- 'Secret' here means the gender of the child.
- All communication is public. You can't whisper in their ears.
- The protocol should not confirm that you are correct. The couple does not know that you know the secret, and they don't want the protocol to give you feedback on whether or not your 'guess' (as they perceive it) is correct: if you were just pretending to know, giving feedback could leak the secret to you.
All you want is to convince them.
Question 1. Is it possible to convince them you know the secret, without leaking the secret to anybody else, and in such a way that if you were just pretending to know, you would obtain no information though the protocol?
There are two possible interpretations of 'convincing', leading to two different questions:
- Is it possible to just tell them what you think the secret is, but encrypt the message so that only they can read it? It seems that one would need to encrypt the secret using the secret itself, since all communication is public...
- Is it possible to convince them in the style of a Zero Knowledge Proof, meaning that, if you sound convincing, there is only a negligible probability that you're guessing?
Note that in 1. they may think you are just lucky to guess correctly (depending on how the protocol works).
Perhaps it becomes only possible if the secret is not binary:
Question 2. What if the secret can take more than 2 values, for example when it can be any real number?
Something I thought was to use a device that outputs for each input string another, unique, fixed and randomly chosen, string. You and the couple would then each enter the secret, and if the device outputs two times the same string, it means you are correct.
The problem with this is that, if you were not correct, you would know so, and because the secret can take only two values, it is leaked to you. And if the output is only shown to the couple, it is essentially no different from whispering the secret to them, i.e. the communication is no longer public.
This does however provide an acceptable solution if the secret can be any real number (or can take infinitely many values): it's virtually impossible to guess, and a wrong guess gives you essentially no information.