Everyone has a list of 4 choices. A pair must match and be publicly known if 2 people have mutual preference. In case its a one sided affair, no one should get any information about the choices.
I try to give a \(\textbf{linear}\) time secure solution to this problem without any central server support.
Lets say there are only Alice, Bob and 3rd party and everyone is allowed only one preference.
\(A\) generates random \(r_1\), \(B\) generates random \(r_2\). Public keys of both are known to everyone.
Stage 1 : \(A\) posts \(m_1 = P_B(r_1)\), \(B\) posts \(m_2=P_A(r_2)\) on some transparent bulletin.
Stage 2 : \(A\) posts \(k_1 = r_1 \oplus {P_A}^{-1} (m_2)\), \(B\) posts \(k_2= r_2 \oplus {P_A}^{-1} (m_1)\) on some transparent bulletin.
\(k1=k2 \implies\) match. Its easy to see in all other cases the knowledge is gibberish to make sense for anyone.
I assume there is no extra redundancy in encryption algorithm, particularly \(P^{-1}(key) (P(x))\) is the \(x\) if key is right and garbage otherwise that gives no information to decoder. For instance if \(g\) is a generator of a prime field, private keys be \(x,y\) and public keys be \(g^x, g^y\) of \(A,B\) then \(P_A(m) = m \oplus hash(g^{xy})\) and \(P^{-1}_A (m) = m \oplus hash(g^{xy})\) works when messages are between \(A,B\).
I describe the protocol from \(A\)’s perspective. Everyone follows the same protocol.
Stage 1:
Everyone generates 4 random numbers for 4 choices. Say \(A\) likes \({B, C, D, E}\). \(A\) posts \(P_B(r_{AB}), P_C(r_{AC}), P_D(r_{AD}), P_E(r_{AE})\) on some transparent bulletin.Call them \(m_{A1}, m_{A2}, m_{A3}, m_{A4}\).
Stage 2:
Everyone generates 4 random numbers for 4 choices say \(x_1,x_2,x_3,x_4\). Say \(A\) likes \({B, C, D, E}\).
\(K_B = m_{B1} m_{B2} m_{B3} m_{B4} x_1\), i.e. their concat. Similarly for \(K_C, K_D\)…
\(A\) posts the following, here on \(S()\) is the SHA or any hash func \(r_{AB} \oplus {P_A}^{-1} (m_{B1}) \oplus S^2(K_B) , r_{AB} \oplus {P_A}^{-1} (m_{B2}) \oplus S^2(K_B), r_{AB} \oplus {P_A}^{-1} (m_{B3}) \oplus S^2(K_B), r_{AB} \oplus {P_A}^{-1} (m_{B4}) \oplus S^2(K_B), S^3 (K_B)\) on some transparent bulletin. Call them \(kA1, kA2, kA3, kA4, CertA\).
Similarly \(A\) posts \(kC1, kC2, kC3, kC4, kD1, kD2, kD3, kD4, kE1, kE2, kE3, kE4\). and the corresponding \(Certs\).
Stage 3:
Until now, no one can deduce any private information from the public information. After this stage matches will be known.
\(A\) posts \(S(K_B), S(K_C), S(K_D), S(K_E)\) on the bulletin.
Note that these are certificates that \(A\) needs to give because \(S^3 ()\) have been given before. These act as certificates of truth.
Now the \(S^2(K_B)\) can be taken out from the xors by everyone. If someone has same value, its a match!
As a further step, matched couples can give additional proof of truth by revealing certain \(K_i (s)\). Like if \(A, B\) match \(K_B\) can be revealed to \(B\). This ensures no one can cheat!
No Central processing or control is required for the protocol. It is completely transparent and can be implemented in a serverless manner. Hence is a zero trust protocol. Central bulletin can be hosted by pclub or anyone.
There is a case when an adversary sends partial hearts, he may send upto 16 partial hearts. Each has max probability of 0.25 match. Expectation is bounded by 4. Moreover this behavior can be detected if a match happens, because the adversary wont be able to produce a valid certificate of truth in the end.
Moreover it is easy to see that if your aim is to match with a particular person or maximize the number of matches, any rational player gets no advantage by not following the protocol. Hence the protocol is also optimal in that sense.
Another attack possible is that someone withholds the correct information about the match after it has occurred, i.e. both had one another in their preferences but someone doesn’t want the other person to know after match has occurred. However this will be the case with any protocol. If \(A,B\) have information \(I_1, I_2\) such that no private information is leaked and let \(I_1', I_2'\) be the extra information that is required to be known to deduce the match. Then whoever has to publish last can always deduce the match without giving information. However it may be the case that this is detectable. It will be interesting to see if some modification can be done to make this detectable.
Disclaimer: For educational purposes only, no responsibility held.
It would be interesting to write proofs about security guarantees if and when I get time.