Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Discrete Applied Mathematics

A fair and efficient solution to the socialist millionaires’ problem

Fabrice Boudot, Berry Schoenmakers, Jacques Traoré

Published Jul 1, 2001• 170 citations
Publisher
DOI
10.1016/s0166-218x(00)00342-5

Related papers

Design and Analysis of Two Efficient Socialist Millionaires’ Protocols for Privacy Protection

Xin Liu, Xiaofen Tu, Xiaofen Tu +1 more

Lecture notes in computer science•Jan 1, 2023•0 citations

A new quantum-inspired solution to blind millionaires’ problem

Yu Zhang, Long Zhang, Kejia Zhang +2 more

Quantum Information Processing•Jan 19, 2023•11 citations

Millionaires’ problem revisited

Amalan Joseph Antony, Kunwar Singh

Computers & Electrical Engineering•Jul 24, 2025•0 citations

Single-photon-based quantum secure protocol for the socialist millionaires’ problem

Min Hou, Yue Wu

The socialist millionaires' problem, emanating from the millionaires’ problem, allows two millionaires to determine whether they happen to be equally rich while remaining their riches undisclosed to each other. Most of the current quantum solutions to the socialist millionaires’ problem have lower efficiency and are theoretically feasible. In this paper, we introduce a practical quantum secure protocol for the socialist millionaires’ problem based on single photons, which can be easily implemented and manipulated with current technology. Our protocol necessitates the involvement of a semi-honest third party (TP) responsible for preparing the single-photon sequences and transmitting them to Alice who performs Identity or Hadamard operations on the received quantum sequences via her private inputs and the secret keys, producing new quantum sequences that are subsequently sent to Bob. Similarly, Bob encodes his private inputs into the received quantum sequences to produce new quantum sequences, which are then sent to TP. By conducting single-particle measurements on the quantum sequences received from Bob, TP can ascertain the equality of private inputs between Alice and Bob, and subsequently communicate the comparison result to them. To assess the feasibility, the proposed protocol is simulated on IBM Quantum Cloud Platform. Furthermore, security analysis demonstrates that our protocol can withstand attacks from outsiders, such as eavesdroppers, and from insider participants attempting to grab the private input of another participant.

Frontiers in Physics•Mar 6, 2024•20 citations

Fairness with an Honest Minority and a Rational Majority

Shien Jin Ong, David C. Parkes, Alon Rosen +1 more

Lecture notes in computer science•Jan 1, 2009•101 citations

An efficient solution to the socialist millionaires' problem

Maryam Hezaveh, Carlisle M. Adams

We present a two-round protocol to solve the socialist millionaire problem based on the homomorphic property of the Goldwasser-Micali (GM) cryptosystem. We require the proposed protocol to be secure against active and passive attacks. However, homomorphic encryption schemes are malleable by design [14][1]. To tackle this problem we apply an authenticated encryption scheme, called Encrypt-then-MAC, to our protocol [3]. We analyze the security of the proposed protocol, and we show that an active adversary, who has access to the ciphertext on the communication channel and the decryption oracle, cannot forge another ciphertext which leads him to guess the plaintext (IND-CCA2 security). Moreover, the active adversary cannot modify the ciphertext which leads to a desired modification of the plaintext to affect the outcome of the protocol (NM-CCA2 security). Note that our solution can be applied to other problems which are solvable with an exclusive- or homomorphic property.

Conference proceedings - Canadian Conference on Electrical and Computer Engineering•Apr 1, 2017•4 citations
The socialist millionaires' problem, emanating from the millionaires’ problem, allows two millionaires to determine whether they happen to be equally rich while remaining their riches undisclosed to each other. Most of the current quantum solutions to the socialist millionaires’ problem have lower efficiency and are theoretically feasible. In this paper, we introduce a practical quantum secure protocol for the socialist millionaires’ problem based on single photons, which can be easily implemented and manipulated with current technology. Our protocol necessitates the involvement of a semi-honest third party (TP) responsible for preparing the single-photon sequences and transmitting them to Alice who performs Identity or Hadamard operations on the received quantum sequences via her private inputs and the secret keys, producing new quantum sequences that are subsequently sent to Bob. Similarly, Bob encodes his private inputs into the received quantum sequences to produce new quantum sequences, which are then sent to TP. By conducting single-particle measurements on the quantum sequences received from Bob, TP can ascertain the equality of private inputs between Alice and Bob, and subsequently communicate the comparison result to them. To assess the feasibility, the proposed protocol is simulated on IBM Quantum Cloud Platform. Furthermore, security analysis demonstrates that our protocol can withstand attacks from outsiders, such as eavesdroppers, and from insider participants attempting to grab the private input of another participant.
We present a two-round protocol to solve the socialist millionaire problem based on the homomorphic property of the Goldwasser-Micali (GM) cryptosystem. We require the proposed protocol to be secure against active and passive attacks. However, homomorphic encryption schemes are malleable by design [14][1]. To tackle this problem we apply an authenticated encryption scheme, called Encrypt-then-MAC, to our protocol [3]. We analyze the security of the proposed protocol, and we show that an active adversary, who has access to the ciphertext on the communication channel and the decryption oracle, cannot forge another ciphertext which leads him to guess the plaintext (IND-CCA2 security). Moreover, the active adversary cannot modify the ciphertext which leads to a desired modification of the plaintext to affect the outcome of the protocol (NM-CCA2 security). Note that our solution can be applied to other problems which are solvable with an exclusive- or homomorphic property.