Join Log in
Score:0
avatar Crypto

Detect if two numbers are equal without disclosing further information

ma flag
Matteo Monti

Consider the following scenario. Alice picks a number A; Bob picks a number B. Both A and B belong to a relatively small set X (by small I mean that X can be easily looped through: for intuition sake, imagine X to be the size of a deck of cards). I would like Alice and Bob to engage in a protocol that tells both if A = B. If A != B, then Alice should have no further information about B, and Bob should have no further information about A.

I wonder if this is possible? If X was very large, and assuming without loss of generality that A is prime, Alice could pick an arbitrary P prime larger than the largest value in X and send A * P to Bob. Bob could then try and factor A * P by B: if it works, then A = B. However, this obviously assumes that it is unfeasible for Bob to try all elements of X. If X is small, this assumption immediately falls.

62
1 + 1
Perseids avatar
na flag
Perseids
This is called the [socialist millionaires' problem](https://en.wikipedia.org/wiki/Socialist_millionaire_problem) by the way.
0
Reply
Score:3
poncho avatar Crypto
my flag
poncho

Yes, it is quite possible.

The obvious approach would be to have Alice and Bob perform a Balanced Password Authenticated Key Exchange (PAKE) protocol, with $A$ and $B$ being their 'passwords'. If they come up with the same shared secret, $A=B$, and if they come up with $A \ne B$ and they don't learn anything else about $A$ and $B$

There are a number of PAKE protocols out there; see the wikipedia article for some of the more common ones.

One such way (which is simplified CPACE) to compare the values $a$ known to Alice and $b$ known to Bob would be to select unrelated values $G$ and $N$ (I wrote this assuming elliptic curves; it can be directly translated to a modp group, except that the subtraction becomes a moduluar inversion) and:

  • Alice selects a random value $r$ and computes $C = r G + a N$; she sends $C$

  • Bob selects a random value $s$ and computes $D = s G + b N$; he sends $D$

  • Alice computes $S = r (D - a N)$; Bob computes $T = s (C - b N)$; if $a=b$, then $S=T$; otherwise they're unrelated.

Alice and Bob can either send $S$ and $T$ to each other (if they trust the other side to be honest), or alternatively use those to generate encryption keys and do a simple verification protocol.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.