13
$\begingroup$

Alice and Beth both receive a random integer from 1 through 10, inclusive. They only know the number that they are given.

The two of them want to come up with an algorithm to check that their sampled numbers are indeed different, but ensure that they reveal no information about their individual numbers (apart from the fact that they are different!).

Either find an algorithm that does such, or prove that no such algorithm exists.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ is there unlimited guesses? is this supposed to be efficient? can I simply make them each guess $\endgroup$
    – Jason V
    Commented Oct 24, 2019 at 13:40
  • $\begingroup$ until comopletion? $\endgroup$
    – Jason V
    Commented Oct 24, 2019 at 13:45
  • 1
    $\begingroup$ @JasonV Guess what exactly? They don't want to know each others numbers. They want to verify they are distinct. $\endgroup$
    – Jaap Scherphuis
    Commented Oct 24, 2019 at 13:46
  • 2
    $\begingroup$ There is a lot of in depth discussion on Crypto SE here, and it seems to be a rather difficult problem, at least if you want to make sure that neither Alice nor Beth can cheat. $\endgroup$
    – Jaap Scherphuis
    Commented Oct 24, 2019 at 14:36
  • 1
    $\begingroup$ And more generally, what techniques are allowed? Should this be thought of in the abstract cryptographic sense, like "Alice and Beth can send each other messages, but that's all"? $\endgroup$
    – Deusovi ♦
    Commented Oct 24, 2019 at 20:41

12 Answers 12

Reset to default
15
$\begingroup$

Any commutative hash function will do.  Using RSA makes this relatively easy, I think.

So Alice and Beth both establish their secret primes, and, in a twist, keep everything secret.  $ % Make EA, EB, DA and DB look like functions; i.e., *not* italic: \def\EA{\operatorname{EA}} \def\EB{\operatorname{EB}} \def\DA{\operatorname{DA}} \def\DB{\operatorname{DB}} $ Then they have:

  1. Privately available $\EA(x)$ and $\EB(x)$, which encrypt, and
  2. Privately available $\DA(x)$ and $\DB(x)$, which decrypt (not used).

So $f_1(f_2(x))=f_2(f_1(x))$, where $f_1$ and $f_2$ are any two of $\EA$, $\EB$, $\DA$ and $\DB$.

Now suppose Alice's number is $a$ and Beth's is $b$.  Then Alice publishes $\EA(a)$ and Beth uses that to publish $\EB(\EA(a))$.

Similarly, Beth publishes $\EB(b)$ and Alice uses that to publish $\EA(\EB(b))$.

These two are equal if and only if $a=b$, but no information leaks if they are different.

A simple hash that could be used is to pick a secret number $y$ and share a number $z$ (e.g., 1000000) and then work out $2^{a+y} \mod z$.

Improve this answer
$\endgroup$
19
  • 3
    $\begingroup$ This works, at least if Alice and Beth trust each other to not lie. If there were an advantage to knowing that their numbers are the same while keeping the other in the dark about that fact, then all bets are off. Alice could publish EA(a) correctly, but lie when publishing EA(EB(b)) by giving a different result. Beth would think their numbers are different, but Alice could (assuming Beth did not also lie) still find out whether the numbers matched by checking the real value of EA(EB(b)). Of course, Beth would have an incentive to lie too, so the whole scheme then falls apart. $\endgroup$
    – Jaap Scherphuis
    Commented Oct 24, 2019 at 15:03
  • 12
    $\begingroup$ I have to point out that there is no Bob in this puzzle. $\endgroup$
    – Arnaud Mortier
    Commented Oct 24, 2019 at 19:56
  • 2
    $\begingroup$ @SteveV Permutations generally do not commute, and you need commutativity for this method to work. I thought for a moment you could use bitwise XOR with a private key, but it really also needs to be a one-way function so that it cannot be undone, i.e. knowing one plaintext/encryption pair (e.g. EA(a) and EB(EA(a)) ) should not allow the decryption of another number (e.g. EB(b) ). $\endgroup$
    – Jaap Scherphuis
    Commented Oct 24, 2019 at 21:33
  • 2
    $\begingroup$ @DrXorile Is that hash function commutative? $\endgroup$
    – Jaap Scherphuis
    Commented Oct 25, 2019 at 6:42
  • 1
    $\begingroup$ @Spoonless That is why even though RSA is used, the (normally public) encryption keys are kept private as well. $\endgroup$
    – Jaap Scherphuis
    Commented Oct 25, 2019 at 14:38
12
$\begingroup$

There are 10 rooms labelled 1-10. Put Alice in her room, and ask Beth to go through the door with her number on it. When this is done, turn the lights back on - if the two girls are in the same room, they have the same number. If not, they don't, and no-one is any the wiser other than that.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This seems along the lines of 'third party'--as coordinating this becomes difficult with just Alice and Beth, and as the number of rooms becomes large. $\endgroup$
    – Nahmid
    Commented Oct 24, 2019 at 15:22
  • 1
    $\begingroup$ @nahmid not really, they can coordinate everything by themselves (thinking cell phones here), so the room numbers act like a hash function that only reveals information when both secrets are equal. $\endgroup$
    – Bass
    Commented Oct 24, 2019 at 15:59
  • $\begingroup$ I can't tell if the question specify Alice and Beth are not supposed to reveal their number in case they are the same? If not this is a good way to test $\endgroup$
    – Alex
    Commented Oct 24, 2019 at 21:06
  • $\begingroup$ @Alex if the rooms were organised in a circle, and the numbers were not on the doors - but the 3rd party "knew" where door 1, door 2, was etc, they girls would be none the wiser even if they were in the same room. $\endgroup$
    – Moo-Juice
    Commented Oct 25, 2019 at 8:55
  • 1
    $\begingroup$ @Moo-Juice If Alice knows her own number and she knows that Beth has the same number, she will always know the number Beth has, because it is the same as her own. So any algorithm will indirectly reveal the other ones number, if they have the same number - by logical deduction. $\endgroup$
    – Falco
    Commented Oct 25, 2019 at 13:45
8
$\begingroup$

Alice takes 1 cardboard box, 10 envelopes, 9 matching coins or disk, and 1 coin/disk of the same size/shape/weight, with a different colour or pattern. This difference may be disclosed in advance - see the final step.

Alice places 1 coin in each of the envelopes and seals them all (keeping track of the "different" coin) then stacks the envelopes inside the cardboard box, with the "different" coin at the position indicated by her number - i.e. on top for 1, at the bottom for 10, and so on. The cardboard box is used to prevent Beth from being able to observe the order that Alice stacks the envelopes in.

Beth and Alice then swap places. Beth retrieves the envelope that matches her number from the stack - the cardboard box again preventing Alice from observing which envelope is taken. The box is shaken vigorously to scramble the untaken envelopes, and returned to Alice.

Under observation of both, either Beth's envelope (if the difference is known) or all envelopes (in a random order) are opened. If Beth's coin is not the odd one out, they have different numbers.

(While Alice could mark the envelopes to learn about Beth's number, Beth can see the envelopes to certify that this has not happened. Similarly, Beth could open additional envelopes to find Alice's number - but Alice can certify whether or not the returned envelopes have been tampered with)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nicely done! I wasn't able to visualize how this process might work, but it's good that you could :) $\endgroup$
    – Avi
    Commented Oct 25, 2019 at 13:16
  • $\begingroup$ @Avi Essentially, I tried to deduce a method by which Alice could indicate True / False, for all 10 numbers, which would destroy the other 9 options when Beth selected any of them, while also preventing Alice from knowing which item was taken. $\endgroup$
    – Chronocidal
    Commented Oct 25, 2019 at 14:54
  • $\begingroup$ (1) Upvoted because this takes the concept of JMP’s answer and makes it logistically practical and somewhat scalable (although it may be impractical for $N$ greater than, say, $100$).  (2) I don’t see why you need coins or disks.  ISTM that all you need is $N-1$ blank pieces of paper and one piece of paper that says “yes”.  It might be possible for Alice to cheat by making the blank sheets non-identical.  Allowing Beth to produce (and/or inspect) the $N$ pieces of paper may suffice as a countermeasure. … (Cont’d) $\endgroup$
    – Peregrine Rook
    Commented Oct 26, 2019 at 18:16
  • $\begingroup$ (Cont’d) ... (3) I don’t see why you need the box — just have the participants turn their back when they are handling the envelopes. $\endgroup$
    – Peregrine Rook
    Commented Oct 26, 2019 at 18:16
  • $\begingroup$ @PeregrineRook While the primary purpose of the box is to preserve anonymity (in both directions — Alice can't see which envelope Beth takes, but she can tell if Beth starts opening or messing with multiple envelopes), its secondary purpose is to be shaken after Beth's selection, to scramble/randomise the unselected envelopes and destroy the information about Alice's number in the scenario that they are different. Turning backs is “Trust…”; adding the box is “… but verify.” $\endgroup$
    – Chronocidal
    Commented Dec 30, 2022 at 13:41
3
$\begingroup$

Alice takes a basic calculator (a simple one that doesn't show history) and covers up the screen with something (paper, non-transparent tape, etc). Alice types in her number and hits the divide key. Beth takes the calculator, types in her number and hits the equals key. They take the cover off the screen and if the screen shows any number other than 1, they have different numbers.

Improve this answer
$\endgroup$
6
  • 6
    $\begingroup$ I like this, but they are supposed to reveal no information about their individual numbers. If the calculator shows anything else than 1 it could very well reveal their numbers. $\endgroup$
    – Wolff
    Commented Oct 24, 2019 at 17:40
  • $\begingroup$ @Wolff With a trick we can get this to work? While reading the answer from the calculator, first cover it with a paper and slowly move the paper downward, to a point you see some pixels. You will be able to see if the answer has more than 1 digit. Secondly, while still covering the answer, only read the first rightmost digit. From these you can tell if the answer is not a '1' but unable to tell the answer. Much like when you play cards from casino. I mean this might not be an algorithm but kinda works $\endgroup$
    – Alex
    Commented Oct 24, 2019 at 22:03
  • $\begingroup$ @Alex, there might be a trick. But if Alice has 1 and Beth has 10 the calculator could show 0.1 so you'll have to move the paper until you see the period and then they both know what the other had. $\endgroup$
    – Wolff
    Commented Oct 24, 2019 at 22:36
  • 2
    $\begingroup$ Most calculator have a "ans" key. So instead of a division, use a soustraction. then type "ans/ans". So if the numbers are the same it will show "ERROR" and if they are differents, it will show 1. This also work with calculators that show the calcul. $\endgroup$
    – GAB
    Commented Oct 25, 2019 at 8:15
  • 3
    $\begingroup$ @GAB even without an ans key, they could just type blind: zero divded by ( a - b ) and look at the result. If it shows 0 they had different number, if it shows ERROR they had the same $\endgroup$
    – Falco
    Commented Oct 25, 2019 at 13:58
2
$\begingroup$

Possibly a modification of @JMP's answer:

Alice and Beth write a following Python script (or an equivalent in other language) and run it on a computer:


 # getpass prompts the user to enter a string (a password) without echoing
 from getpass import getpass
 a = getpass("Alice: ")
 b = getpass("Beth: ")
 try:
     print(int(a) != int(b))  # prints True if their numbers are different, False otherwise
 except:
     # to avoid echoing in case of something mistyped, e.g. '8a' instead of '8'
     print("Non-number string entered")
Then Alice inputs her numbers, and then Beth inputs her one (of course, they do it while the other girl does not see the keyboard). By the output, they both can see the result (even not having to reveal their numbers to each other when they are the same (comment by @Alex to @JMP's answer) - but this requirement seems useless, since they obviously would know the numbers of each other if they know that the numbers are the same).

The advantage of this answer over JMP's one is

that this solution works with any range of possible numbers (e.g. if it would be 1 to 1 000 000 000, it's difficult to even build a billion rooms (and much more difficult is not to get lost inside them)).

Improve this answer
$\endgroup$
1
  • $\begingroup$ If Beth is a clever hacker, she can find the value of a in the program's memory. $\endgroup$
    – aschepler
    Commented Oct 26, 2019 at 16:39
1
$\begingroup$

Assuming Alice and Beth can be assigned the same number, then no such algorithm exists, since the algorithm would sometimes reveal that the numbers are not distinct, which means revealing their numbers to each other.

(If Alice and Beth cannot be assigned the same number, then that needs to be specified)

Improve this answer
$\endgroup$
1
  • $\begingroup$ From the question "but ensure that they reveal no information about their individual numbers (apart from the fact that they are different!)." - so the information different/same may be revealed (this is the goal of the algorithm) but nothing else. - So if they have the same number, the information can be revealed. $\endgroup$
    – Falco
    Commented Oct 25, 2019 at 13:55
0
$\begingroup$

If you use truncating division, either $\frac{a}{b}$ or $\frac{b}{a}$ will be $0$, provided that $a\neq{}b$. Therefore, let Alice and Beth hand over their numbers to a trusted black box (which will never reveal their information), that will simply return to Alice and Beth the value $\frac{a}{b}\cdot{}\frac{b}{a}$. If the values are the same, this will return $1$, otherwise $0$. Establishing a trusted black box is the hard part here.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ You can't use a third party, otherwise the problem becomes trivial. Just have A and B tell their numbers to the third party individually and let the third party tell them whether they are different or not... $\endgroup$
    – Alexander Geldhof
    Commented Oct 24, 2019 at 14:30
  • $\begingroup$ @AlexanderGeldhof Good point. Looks like this won't work, then :( $\endgroup$
    – Avi
    Commented Oct 24, 2019 at 14:31
  • $\begingroup$ @avi See my answer, in which the "trusted black box" is literally a cardboard box, used to transmit only the information of "same" or "different" $\endgroup$
    – Chronocidal
    Commented Oct 25, 2019 at 13:11
0
$\begingroup$

Basing this off rfajardo's answer,

Write a computer program that takes 2 input parameters one after another (performs clear screen after each input given) and then returns a boolean true or false depending on the result of the (a==b) operation.

An additional buffer flush can be performed once the result is displayed, to prevent either person from reading the given inputs (assuming they are adept enough to retrieve data from the buffer).

Sure, the computer acts as a 3rd party here but it cannot disclose information if you close out loopholes.

If the result of (a==b) is True, the numbers match. If the result is False, they don't.

Improve this answer
$\endgroup$
0
$\begingroup$

Open 2 minecraft clients. In the seed section of the map input Alice's and Berth's numbers.

If the maps have the same structure then they have the same number.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ Problem: After doing this, Alice can open another minecraft client, and try entering keys until she finds one with the same structure as the one from Beth's key. $\endgroup$
    – ralphmerridew
    Commented Oct 25, 2019 at 12:30
  • $\begingroup$ Right, but then any algorithm with endless time can be broken right? Also I think this same answer can be applied to the polarisation algorithm I read below $\endgroup$
    – Patryk Kotarski
    Commented Oct 25, 2019 at 15:31
0
$\begingroup$

Both define a conversion from their numbers to a rotation of a polarisation filter.

Then they adjust a polarisation filter to that rotation, so that if their numbers are equal, the direction of polarisation of both filters is the same.

Now Alice sends a string of random 0/1 as polarised light (single quantums). When sending a 1 the polarised light has to be aligned with her filter, when sending a 0 it has to be orthogonal. Only if Bobs filter is aligned exactly as Alices, he will receive the exact same string when looking through his filter, seeing 1 as light on and 0 as light off. If it is misaligned, he will receive a randomized string. Now Bob sends a shifted sequence of the same string. If Alice receives, what she sent, their numbers are equal. Now they can repeat the same into the other direction, so Bob knows the result, too.

This is based on some methods of post quantum key exchange I've read about and should guarantee, that no Information leaks and it is at least close to "just sending messages" and doesn't require a 3rd party.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Wouldn't a misaligned filter result in results which correlate imperfectly to the original data, not independently random results? So if Alice sees that 80% of the bits returned match what she sent, she can calculate the approximate angle between the two polarizers. $\endgroup$
    – aschepler
    Commented Oct 26, 2019 at 16:45
  • $\begingroup$ @aschepler Yes, you are right - hashing the message should fix it though. $\endgroup$
    – Matzurai
    Commented Oct 28, 2019 at 7:02
  • $\begingroup$ Hashing at what point? I'm not seeing how that could prevent a calculation of angle. $\endgroup$
    – aschepler
    Commented Oct 28, 2019 at 12:34
  • $\begingroup$ @aschepler the returning message. Alice sends 10011001 - Bob receives 10111001, now he hashes that and sends back the hash. Alice can compare the hash result of her sent message with what Bob got out of it. If it is a mismatch, she wouldn't know, how much of difference there is. $\endgroup$
    – Matzurai
    Commented Oct 29, 2019 at 12:49
0
$\begingroup$

Based on the answer by @rfajardo and the comment by @Falco:

  1. Take a calculator and cover the screen
  2. Alice enters her number and hits -
  3. Beth enters her number and hits = and 1/x
  4. Alice hits / or * followed by any number except 0 and then = , making sure that Beth does not see the input
  5. Beth does the same, without Alice seeing it
  6. Uncover the screen

If the screen shows Error (on my mobile phone) or 0 (on my RPN calculator), the numbers were equal. Any other result means that the numbers were different, but they can not tell which numbers it were.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Even easier by just entering 0 / ( a - b ) $\endgroup$
    – Falco
    Commented Oct 25, 2019 at 14:43
  • $\begingroup$ @Falco that is right $\endgroup$
    – Raoul Kessels
    Commented Oct 25, 2019 at 14:45
0
$\begingroup$

Request to show up at a designated place at the time of your number. Leave at 5 minutes past your number's time and only arrive within 5 minutes before. If they both show up, they have the same number. This assumes both parties are in good faith but all of the algorithms inherently assume that as well. (This is clearly not the most time efficient way, but it was fun to imagine)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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