Zero-Knowledge Matchmaker

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

This Demonstration illustrates a zero-knowledge protocol for matchmaking. Alice and Bob indicate whether they like each other and then apply the matching protocol. Under this protocol, the only information revealed is whether there is a match, nothing more. In particular, if the liking is not mutual, it is not revealed who disliked whom.

Contributed by: Tom Verhoeff (June 2014)
(Eindhoven University of Technology, 2014)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The protocol used in this Demonstration is a variant of [1]. It involves five cards of two types: one type has two half-disks; the other type has a circular line (annular segment).

One half-disk card is neutral. Alice and Bob each have two cards, one of each type. Alice and Bob secretly encode their own choices by forming an "arrow" pointing at the other for "like" and pointing away from the other for "not like." They then hide their encoding, assemble the five pieces into a complete disk, randomly spin it, and reveal the result.

By the design of the protocol, only two kinds of results are possible, modulo rotation: there are either three consecutive half-disk cards and two consecutive line cards, or not. In the latter case, there are exactly two consecutive half-disk cards, with the remaining half-disk card appearing between the two isolated line cards. The result with three consecutive half-disk cards corresponds to a match (Alice and Bob like each other).

By design of the card shapes, the pattern with three consecutive half-disks looks like a smiley, and the other looks sort of like a surprised face.

In this Demonstration, Alice and Bob make their choices through their respective setter bars. The match slider steps through the secure matching process: hiding the card faces, assembling the five cards into a disk, zooming in, spinning the disk to obfuscate the choices, and revealing the result. The "peek" checkbox can be used to peek under the hood and see more clearly what is happening.

Reference

[1] B. den Boer, "More Efficient Match-Making and Satisfiability: The Five Card Trick," Advances in Cryptology—EUROCRYPT ’89 (Lecture Notes in Computer Science), Vol. 434, 1990 pp. 208–217. doi:10.1007/3-540-46885-4_ 23.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send