10
$\begingroup$

Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or not a equals b, without revealing any other information. Can they?

$\endgroup$
  • $\begingroup$ What do you mean by "any" in "any other information"? What is the knowledge allowed to be shared? $\endgroup$ – Loïc Teyssier Apr 17 '16 at 16:41
  • $\begingroup$ The knowledge allowed to be shared is truth of the statement a = b. $\endgroup$ – Randomblue Apr 17 '16 at 17:55
  • 1
    $\begingroup$ Alice picks a random number $x$ between 1 and 10 and sends $x + a \mod 10$. Bob gets this number (call it $y$) and responds with $y - b \mod 10$. Alice knows that $y = x$ iff $a = b$ and at this point Bob knows nothing. Now Alice can send Bob this information. $\endgroup$ – Yair Hayut Apr 17 '16 at 18:32
  • 4
    $\begingroup$ @YairHayut In the scheme you propose, Alice knows $b$ at the end. I think Randomblue wanted a scheme where Alice receives no information about $b$ apart from the fact that $b=a$ or $b\neq a$ and similarly Bob receives none about $a$ apart from the fact that $a=b$ or $a\neq b$. The question could have been worded more clearly, though. $\endgroup$ – Gro-Tsen Apr 17 '16 at 18:38
  • 3
    $\begingroup$ crossposted to crypto after less than 5 minutes, without mentioning that on either site ​ ​ $\endgroup$ – user5810 Apr 18 '16 at 2:43
6
$\begingroup$

In typical mathematician fashion, let me explain how to reduce your problem to a harder one ☺, namely homomorphic encryption. (Edit: I should have made it clear that the problem of constructing homomorphic encryption schemes, at least to the extent required here, is indeed solved.)

Assume Charlie is an "honest but curious" third party (i.e., Charlie can be trusted to perform computations honestly but should not be allowed to know $a$ or $b$): I hope it is not unreasonable to assume the existence of Charlie. Alice and Bob ask Charlie to set up a homomorphic encryption scheme and give them the public key. Alice and Bob each encrypt their integer using this public key, and share the (encrypted) result, but don't give it to Charlie. They then use the homomorphic properties of the scheme to compute the (encrypted) value of the "if $a=b$ then $1$ else $0$" function (as a boolean function, this does not require a large number of bit multiplications, so the homomorphic properties required are not too difficult to obtain). Both can perform the computation. They send the result to Charlie for decryption, and Charlie can return the result. Thus, at the end, Alice, Bob and Charlie each know whether $a=b$ but not what the numbers are except those they themselves chose.

Edit 2: as per Pace Nielsen's comment, I should have clarified that this kind of encryption is non-determinististic: there isn't just one cyphertext for each of the values from 1 to 10, there are a huge number, and neither Alice nor Bob can decrypt the other's value by simply trying out all possibilities.

Of course, this leaves a lot of questions unanswered, like whether we can arrange for Charlie not to know whether $a=b$, or do without Charlie altogether (probably something can be done with functional encryption or homomorphic encryption with a secret key that is split between Alice and Bob, but there are usually lots of honesty assumptions that might not be obvious). Perhaps more insidiously, I don't know how to make sure that Alice does not select a number outside the allowed range (a number that would essentially return "no" to any comparison with a number honestly chosen by Bob).

$\endgroup$
  • $\begingroup$ I don't see how this works. If the key is public, then all Alice has to do to figure out Bob's number is encrypt all ten numbers 1 to 10 with the public key, and see which of these crypt-texts matches Bob's. This would work if the list of possible numbers was much larger, but with only ten numbers it appears to not work. $\endgroup$ – Pace Nielsen Apr 18 '16 at 1:37
  • $\begingroup$ @PaceNielsen This kind of "encryption" is non-deterministic: there are a huge number of possible encryptions of each of the numbers from 1 to 10 or even just of a bit. So no, you can't reverse the encryption by trying all possible values. But you're right, I should have clarified this (and this is probably the reason I got a downvote on this answer). $\endgroup$ – Gro-Tsen Apr 18 '16 at 6:17
5
$\begingroup$

This partial answer is from an information theoretic perspective: This cannot be done with small number of rounds of talking. Suppose the players receive a number between 1 and $n$ and they want to know the answer with probability $1-\epsilon$. If the number of rounds in their conversation is smaller than $\log^*\min\{n, 1/\epsilon\}$, some extra information reveal must happen. This follows from [arXiv:1304.1217], though the reduction needs some explaining. Here $\log^*$ is the iterated logarithm function.

When an unbounded number of rounds is allowed, equality can be determined with probability 1 by revealing a very small amount of information (independent on $n$). Good thing about 0 information is it is 0 no matter how we measure it, but for non-zero information we need to specify how we measure it.

There is a fixed protocol P such that for any $(a,b)\in [n]\times[n]$ the parties learn whether $a=b$ with probability 1 and for any distribution $\mu$ on $[n]\times[n]$, if $(A,B)\sim \mu$,

$$ I(A;\Pi\,|\, B) + I(B;\Pi\,|\,A) < 4.5, $$

where $\Pi$ is a random variable denoting their conversation. This protocol is from ECCC:TR11-123, Proposition 3.21.

$\endgroup$
  • 1
    $\begingroup$ Just to clarify things (at least if I understand correctly), MertSaglam answers from the information-theoretic point of view (i.e., attackers are assumed to have unlimited computational power) whereas my answer was cryptographic (i.e., attackers can only do things that are computationally feasible). The problem is that OP's question is vague (I assumed, maybe wrongly, from the "cryptography" tag that a cryptographic answer was sought). $\endgroup$ – Gro-Tsen Apr 17 '16 at 20:22
  • $\begingroup$ Very good point, I was about to write a clarification comment below the question. $\endgroup$ – Mert Sağlam Apr 17 '16 at 20:24
  • $\begingroup$ Sorry about the ambiguity. The implicit assumption is attackers can only do things that are computationally feasible. $\endgroup$ – Randomblue Apr 17 '16 at 20:38
4
$\begingroup$

You are asking the socialist millionaire problem. There are several solutions to the problem, amongst them the one showed on the Wikipedia page, using the Diffie–Hellman-Merkle key exchange for secure multiparty computation.

The table describing it is a bit hard to copy into mathoverflow, but you can have a look at the protocol diagram:

$\endgroup$
  • 3
    $\begingroup$ The algorithm described on the wiki page doesn't seem to work if there are only ten possible (known) integers available. Once Alice sends Bob the number $h^a$, he'll know $a$ from the fact he knows $h$ and $p$ and can compute $h^x\pmod{p}$ for $x=1,...,10$. $\endgroup$ – Pace Nielsen Apr 18 '16 at 2:25
1
$\begingroup$

I believe this task can be solved without the need for an "honest but curious third party" so long as Alice and Bob commit to performing the following full protocol:

Alice and Bob share a large prime number $p > 5$ and compute $a^\prime = a^p\,\mathrm{mod}\,10$ and $b^\prime = b^p\,\mathrm{mod}\,10$, respectively. Their resulting numbers will be equal if and only if their original numbers were equal, i.e., $a^\prime = b^\prime$ if and only if $a = b$. Then they run Yao's secure multi-party protocol for the Millionaires' problem twice, to test first if $a^\prime \geq b^\prime$ and if $b^\prime \geq a^\prime$. (No other information is revealed through this protocol.) If the answer to both questions is yes, then $a^\prime = b^\prime$ and hence $a = b$. If the answer is no to one of these questions, then $a^\prime > b^\prime$ or $b^\prime > a^\prime$ and hence $a \neq b$. Because of the prime exponentiation, neither party can tell whether $a > b$ or $b > a$.

$\endgroup$
  • 4
    $\begingroup$ "Because of the prime exponentiation, neither party can tell whether $a>b$ or $b>a$." While this is true, it is not true that no additional information has been imparted. Alice and Bob do know whether $a'>b'$ or $b'>a'$, and this information does impart some information about $a$ and $b$. (For instance, if $a'$ is 8, and $b'>a'$, then Alice knows that Bob's number is the only $b$ which gives $b'$. This is easy to compute.) $\endgroup$ – Pace Nielsen Apr 18 '16 at 1:47
0
$\begingroup$

(EDIT: Since the sample space is so small Alice would just be able to retry 1..10 and crack this)

As a software developer this is how I would try solve the problem:

Alice and Bob each hash their numbers with something like scrypt; then they send each other the resultant hash.

They try and rehash their numbers using the scrypt check function; if the check passes then they have the same number.

Details:

Scrypt generates a random salt then hashes the number + the salt then reshashes that X times (X is configurable but == a lot) [Or something like that]

Alice will have generated a different salt than Bob. The hash from scrypt includes the random salt and number of hashing rounds

Alice using her number, bobs salt and number of rounds can re run the hash algorithm; if she gets the same resultant hash then the numbers (are very probably*) the same. Bob can do the same.

FYI this is how how passwords "should" be stored in a data base.

* There could be a hash collision, but that is very unlikely.

$\endgroup$
  • 1
    $\begingroup$ If Alice alone has the information to check any number against Bob's, then she can check all 10 numbers from 1 to 10 to find out Bob's. If I understood you correctly, this is the case in your proposed solution. $\endgroup$ – Peter Kravchuk Apr 18 '16 at 6:45
  • $\begingroup$ @PeterKravchuk That is true. You could slow her (or Eve if she is listening) down by using a larger number of rounds, but with a sample space of 10 that is not going to be very practical. $\endgroup$ – DarcyThomas Apr 18 '16 at 6:51
  • $\begingroup$ @PeterKravchuk Maybe if they use Diffie hellman to create the salt... And I think I am getting out of my pay grade. $\endgroup$ – DarcyThomas Apr 18 '16 at 7:00

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.