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

Protocols for secure computations

Andrew Chi-Chih Yao

Published Nov 3, 1982• 2,659 citations
Publisher

Abstract

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.

DOI
10.1109/sfcs.1982.88

Related papers

Secrecy without one-way functions

Dima Yu. Grigoriev, Vladimir Shpilrain

We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results” of a computation. For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our unconditionally secure (bit) commitment scheme for three parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a “dummy” (e.g., a computer) as the third party. We explain how our concept of a “dummy” is different from the well-known concept of a “trusted third party”. Based on a similar idea, we also offer an unconditionally secure k - n oblivious transfer protocol between two parties who use a “dummy”. We also suggest a protocol, without using a one-way function, for the so-called “mental poker”, i.e., a fair card dealing (and playing) over distance. Finally, we propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.

arXiv:1301.5069•journal of Groups complexity cryptology•Jan 1, 2013•5 citations

Cryptography and Secure Two-Party Computation

Gabriel Bender

millionaires, and the pair wishes to determine who has more money. However, neither person wishes to reveal his or her precise wealth to the other. [5] One approach to this problem (dubbed the ideal solution) is for Alice and Bob to find a third party that they both trust. Then Alice tells the third party how much money she has, and Bob follows suit. Once both Alice and Bob have both revealed the necessary information to him, the third party provides both of them with an answer to their question. However, the use of such a trusted third party is not always practical. Therefore, our goal is to simulate the presence of such a third party using cryptography. Secure two-party computation provides a generalization of this problem: Suppose we wish to compute the value of a function F (A, B) where A is an input provided by Alice and B is provided by Bob. Assume furthermore that Alice does not wish to disclose her input to Bob, and that likewise, Bob wishes to conceal his input from Alice. How can they compute F (A, B) together while observing these constraints?

•Jan 1, 2006•0 citations

Communication preserving protocols for secure function evaluation

Moni Naor, Kobbi Nissim B

A secure function evaluation protocol allows two parties to jointly compute a function f(x; y) of their inputs in a manner not leaking more information than necessary. A major result in this field is: "any function f that can be computed using polynomial resources can be computed securely using polynomial resources" (where `resources' refers to communication and computation). This result follows by a general transformation from any circuit for f to a secure protocol that evaluates f . Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of f . We propose a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of f . We start with an efficient (insecure) protocol for f and transform it into a secure protocol. In other words, "any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter". We show several simple applications of this new methodology resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem ", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation. 1.

ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•165 citations

Communication Complexity and Secure Function Evaluation

Moni Naor, Kobbi Nissim B

We suggest two new methodologies for the design of efficient secure protocols, that differ with respect to their underlying computational models. In one methodology we utilize the communication complexity tree (or branching for f and transform it into a secure protocol. In other words, "any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter". The second methodology uses the circuit computing f, enhanced with look-up tables as its underlying computational model. It is possible to simulate any RAM machine in this model with polylogarithmic blowup. Hence it is possible to start with a computation of f on a RAM machine and transform it into a secure protocol. We show many applications of these new methodologies resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.

arXiv:cs/0109011•Electronic colloquium on computational complexity•Sep 9, 2001•31 citations

Cryptography without one-way functions

Dima Yu. Grigoriev, Vladimir Shpilrain

We show that some problems in cryptography can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “P ̸ = NP ” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results ” of a computation. For example, when we compute the sum of k numbers, only the final result is known to (one of) the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. While it is fairly obvious that a secure (bit) commitment between two parties is

•Jan 1, 2011•0 citations

The match-making problem

Jeroen van de Graaf, van de

. This paper discusses a cryptographic protocol to evaluate an and-gate such that a party can keep his input bit secret from the other party. Such a protocol is of interest, because it can be generalized to any logical circuit for any number of participants. A formal statement of this generalization reads as follows: n participants want to compute together a function f(x1 ; x2 ; :::; xn) with x i being their inputs; nobody wants to reveal information about his input except what can be logically be deduced from the output. The paper contains no new results but provides an illustration of a sub-field of cryptography, and introduces several interesting protocols and protocol design techniques. 1 Introduction Suppose Alice and Bob meet for the first time. They want to find out whether they are interested in each other, so both engage in a cryptographic protocol transmitted in infra-red through their watches. The protocol has to be such that if both parties show interest they find out, bu...

Quarterly - Centrum voor Wiskunde en Informatica•Jun 1, 1995•0 citations
Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x1, x2, x3, . . . , xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x’s. Is it possible for them to compute the value of f , by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires’ problem corresponds to the case when m = 2 and f(x1, x2) = 1 if x1 < x2, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question “How many bits need to be exchanged for the computation”, and describe methods to prevent participants from cheating. Finally, we study the question “What cannot be accomplished with one-way functions”. Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.
We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results” of a computation. For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our unconditionally secure (bit) commitment scheme for three parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a “dummy” (e.g., a computer) as the third party. We explain how our concept of a “dummy” is different from the well-known concept of a “trusted third party”. Based on a similar idea, we also offer an unconditionally secure k - n oblivious transfer protocol between two parties who use a “dummy”. We also suggest a protocol, without using a one-way function, for the so-called “mental poker”, i.e., a fair card dealing (and playing) over distance. Finally, we propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.
millionaires, and the pair wishes to determine who has more money. However, neither person wishes to reveal his or her precise wealth to the other. [5] One approach to this problem (dubbed the ideal solution) is for Alice and Bob to find a third party that they both trust. Then Alice tells the third party how much money she has, and Bob follows suit. Once both Alice and Bob have both revealed the necessary information to him, the third party provides both of them with an answer to their question. However, the use of such a trusted third party is not always practical. Therefore, our goal is to simulate the presence of such a third party using cryptography. Secure two-party computation provides a generalization of this problem: Suppose we wish to compute the value of a function F (A, B) where A is an input provided by Alice and B is provided by Bob. Assume furthermore that Alice does not wish to disclose her input to Bob, and that likewise, Bob wishes to conceal his input from Alice. How can they compute F (A, B) together while observing these constraints?
A secure function evaluation protocol allows two parties to jointly compute a function f(x; y) of their inputs in a manner not leaking more information than necessary. A major result in this field is: "any function f that can be computed using polynomial resources can be computed securely using polynomial resources" (where `resources' refers to communication and computation). This result follows by a general transformation from any circuit for f to a secure protocol that evaluates f . Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of f . We propose a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of f . We start with an efficient (insecure) protocol for f and transform it into a secure protocol. In other words, "any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter". We show several simple applications of this new methodology resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem ", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation. 1.
We suggest two new methodologies for the design of efficient secure protocols, that differ with respect to their underlying computational models. In one methodology we utilize the communication complexity tree (or branching for f and transform it into a secure protocol. In other words, "any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter". The second methodology uses the circuit computing f, enhanced with look-up tables as its underlying computational model. It is possible to simulate any RAM machine in this model with polylogarithmic blowup. Hence it is possible to start with a computation of f on a RAM machine and transform it into a secure protocol. We show many applications of these new methodologies resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.
We show that some problems in cryptography can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “P ̸ = NP ” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results ” of a computation. For example, when we compute the sum of k numbers, only the final result is known to (one of) the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. While it is fairly obvious that a secure (bit) commitment between two parties is
. This paper discusses a cryptographic protocol to evaluate an and-gate such that a party can keep his input bit secret from the other party. Such a protocol is of interest, because it can be generalized to any logical circuit for any number of participants. A formal statement of this generalization reads as follows: n participants want to compute together a function f(x1 ; x2 ; :::; xn) with x i being their inputs; nobody wants to reveal information about his input except what can be logically be deduced from the output. The paper contains no new results but provides an illustration of a sub-field of cryptography, and introduces several interesting protocols and protocol design techniques. 1 Introduction Suppose Alice and Bob meet for the first time. They want to find out whether they are interested in each other, so both engage in a cryptographic protocol transmitted in infra-red through their watches. The protocol has to be such that if both parties show interest they find out, bu...