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.
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.
We present three simple and efficient protocol constructions to solve Yao's Millionaire Problem when the parties involved are non-colluding and semi-honest. The first construction uses a partially homomorphic Encryption Scheme and is a 4-round scheme using 2 encryptions, 2 homomorphic circuit evaluations (subtraction and XOR) and a single decryption. The second construction uses an untrusted third party and achieves a communication overhead linear in input bit-size with the help of an order preserving function.Moreover, the second construction does not require an apriori input bound and can work on inputs of different bit-sizes. The third construction does not use a third party and, even though, it has a quadratic communication overhead, it is a fairly simple construction.
Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.
The millionaires’ problem is the basis of secure multiparty computation and has many applications. Using a vectorization method and the Paillier encryption scheme, we first propose a secure two-party solution to the millionaires’ problem, which can determine x=y, x<y , or x>y in one execution. Subsequently, using the vectorization and secret splitting methods, we propose an information-theoretically secure protocol to solve the multiparty millionaires’ problem (a.k.a. secure sorting problem), and this protocol can resist collusion attacks. We analyze the accuracy and security of our protocols in the semihonest model and compare the computational and communication complexities between the proposed protocols and the existing ones.
The socialist millionaire problem seeks to determine the equality relationship between the inputs of two users while ensuring that these inputs remain undisclosed to each other and to potential attackers. Current quantum protocols encounter challenges related to practicality and efficiency in addressing this issue. To overcome these challenges, we propose a quantum secure protocol specifically designed to effectively solve the socialist millionaire problem. In this protocol, a semihonest third party (TP) generates and distributes single photons to the participants. After securely receiving the photons, the participants encode their secret data using local quantum operations. The encoded photons are then returned to TP, which extracts the result via quantum measurement. By employing a circular photon transmission mode, the protocol reduces resource redundancy and achieves higher qubit efficiency. Security analysis confirms the protocol’s robustness against external quantum attacks—such as intercept‐resend, measurement‐resend, and entangle‐measure attacks—as well as against the curiosity of semihonest participants. Finally, using accessible quantum components (single photons, Pauli gates, and Bell measurements), we simulate the protocol on IBM Qiskit to verify its feasibility.
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.
Cramer, Damgard, and Nielsen [CDN01] show how to construct an efficient secure multiparty computation scheme using a threshold homomorphic encryption scheme that has four properties i) a honest-verifier zero-knowledge proof of knowledge of encrypted values, ii) proving multiplications correct iii) threshold decryption and iv) trusted shared key setup. Naor and Nissim [NN01a] show how to construct secure multi-party protocols for a function f whose communication is proportional to the communication required to evaluate f without security, albeit at the cost of computation that might be exponential in the description of f . Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function f using communication that is independent of the circuit description of f and computation that is polynomial in | f |. This paper addresses the major drawback’s of Gentry’s approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim’s compiler. To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes. We directly construct (information theoretically) secure protocols for sharing the secret key for our threshold scheme (thereby removing the setup assumptions) and for jointly decrypting a bit. All of these constructions are constant round and we thoroughly analyze their complexity; they address requirements (iii) and (iv). The fact that the encryption scheme is fully homomorphic addresses requirement (ii). To address the need for an honest-verifier zero-knowledge proof of knowledge of encrypted values, we instead argue that a weaker solution suffices. We provide a 2-round blackbox protocol that allows us to prove knowledge of encrypted bits. Our protocol is not zeroknowledge, but it provably does not release any information about the bit being discussed, and this is sufficient to prove the correctness of a simulation in a method similar to Cramer et al. Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function f using communication that is independent of the circuit description of f .