5
$\begingroup$

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:

  1. 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...
  2. 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?

Attempt/example

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.

$\endgroup$
  • 1
    $\begingroup$ If there are only 2 values, then it's impossible to tell the difference between someone who knows the secret, and someone who guessed correctly. $\endgroup$ – vadim123 Feb 10 '18 at 23:02
  • $\begingroup$ Hmm yes... Then again, part of the question is whether it's even possible to (publicly) make a guess. $\endgroup$ – punctured dusk Feb 10 '18 at 23:07
2
$\begingroup$

Since you allowed for the use of a fictional device, I will assume that practicability is not a major concern, however all of what I will suggest can in theory be done on a sheet of paper as well.

  1. The couple generates a public/private key pair for any asymmetric encryption scheme, with a security of $k$ bits, say.
  2. You generate $k-1$ bits of random data and append your guess to this data as the $k$-th bit. You encrypt this $k$ bit string with their public key and transmit this encrypted data to them.
  3. They decrypt your guess but do not answer in any way to it.

If we assume that the asymmetric encryption scheme is secure, then noone at the table will be able to recover the $k$-th bit of your message. The only information you received was their public key, and they sent you that even before you made your guess, so you will not gain any information from this.

$\endgroup$
2
$\begingroup$

There is a problem in cryptology, called Socialist millionaires. Here the definition from the wikipedia;

In cryptography, the socialist millionaire problem is one in which two millionaires want to determine if their wealth is equal without disclosing any information about their riches to each other. It is a variant of the Millionaire's Problem whereby two millionaires wish to compare their riches to determine who has the most wealth without disclosing any information about their riches to each other.

You can use a solution to this problem to compare your input without revealing your knowledge to the other side and the third parties.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.