Multiparty Computation

home

learn

research

build

resources

about us

How to Generate and Exchange Secrets 1986 Andrew C. Yao

“The "fairness" requirement means that a cheater should not be able to obtain the desired output while denying the other party to find the proper output. The problem of exchanging secrets has this requirement as its main concern.”

Editor's Overview

Introduction

How To Generate and Exchange Secrets is a 1986 extended abstract by Yao that is, strangely, well-known for something not written in it. Yao's garbled circuit, one of the two most basic general constructions for creating multiparty computation protocols, was actually first mentioned in an oral presentation given about the paper as an example of how to satisfy the specifications Yao laid out. Ironically, it is in the description of the other basic construction, the GMW method, that we can actually find the first major publication of Yao's garbled circuit method.

We give a formal construction of the protocol after the Goals and Results section.

Goals and Results

Because Yao never completed released a completed version of this paper, there is actually very little that was accomplished per se in this paper. The released abstract deals entirely with definitions for what a protocol must satisfy in order to be valid, private, and 'fair.'

The main results from this paper were due to the word-of-mouth spread of the garbled circuit construction. The garbled circuit—sometimes also known as the "combined oblivious transfer," thanks to GMW—is an extremely useful primitive for use in building protocols for several reasons:

It's generalizable: since Boolean gates are complete over computations, a garbled circuit is able to perform any 2-party computation.
It operates in constant round complexity; that is, the number of interactions between parties is only relative to the size of the inputs, not to the size of the operation. This is starkly in contrast with the GMW construction, in which the number of interactions is relative to the number of gates.

Garbled Circuit Construction

Two parties, $P_1$ and $P_2$ wish to jointly compute the value of some function. Without loss of generality, assume they are performing a binary function on their respective bits $b_1$ and $b_2$.

The two parties first agree on a function, $f(\cdot,\cdot)$. Party 1 creates the truth table for the function. For concreteness, let's assume they are computing AND; the concepts are identical for any gate.

$b_1$	$b_2$	$b_1\wedge b_2$
0	0	0
1	0	0
0	1	0
1	1	1

Both parties then agree on some symmetric encryption and decryption scheme, $\operatorname E,\,\operatorname D,$ along with some sampling algorithm $\operatorname G$ which produces keys within the scheme. Party 1 samples 6 random keys $s_i$ using $\operatorname G$: $s_1\dots s_6$. Party 1 recreates the table, except now, within each column, $P_1$ replaces the pair 0 and 1 with a chosen pair of keys out of $s$.

$b_1$	$b_2$	$b_1\wedge b_2$
$s_1$	$s_3$	$s_5$
$s_2$	$s_3$	$s_5$
$s_1$	$s_4$	$s_5$
$s_2$	$s_4$	$s_6$

Party 1 then encrypts the output column using both of the keys within its row, like so:

$b_1$	$b_2$	$b_1\wedge b_2$
$s_1$	$s_3$	$\operatorname E_{s_1}(\operatorname E_{s_3}(s_5))$
$s_2$	$s_3$	$\operatorname E_{s_2}(\operatorname E_{s_3}(s_5))$
$s_1$	$s_4$	$\operatorname E_{s_1}(\operatorname E_{s_4}(s_5))$
$s_2$	$s_4$	$\operatorname E_{s_2}(\operatorname E_{s_4}(s_6))$

$P_1$ shows $P_2$ some permutation of the rows, but doesn't show $P_2$ the keys themselves; that is, $P_2$ knows the evaluation of (for instance) $\operatorname E_{s_1}(\operatorname E_{s_3}(s_5))$, and knows that it uses $s_1$ and $s_3$, but does not know the values of $s_1$ or $s_3$. $P_1$ also tells $P_2$ the association between $P_2$'s bit's value and $s_3,\,s_4$; so $P_2$ knows that $s_3$ corresponds to 0 and $s_4$ corresponds to 1. Again, $P_2$ does not know the value of any keys at this point.

$P_1$ sends to $P_2$ the specific key associated with the value of $b_1$: $P_2$ now has one of the two keys necessary to decrypt an output value. In order to get the other key, $P_2$ performs a one-out-of-two oblivious transfer with $P_1$, retrieving only the key associated with $b_2$'s value.

$P_2$ now possesses two keys, and can therefore decrypt the output of one row of the encrypted truth table—that is, the output of the circuit. $P_2$ now possesses a key which is directly associated with the output of the gate; depending on how the parties wish to continue, one of two things occurs. If the output of this gate is not going to be used as input in another gate, $P_1$ simply tells $P_2$ the associations between (0,1) and ($s_5,s_6$), so $P_2$ knows how to interpret the output. Otherwise, $P_1$ can use the two possible output keys as new input keys for another garbled gate, ad infinitum.

Assumptions

Let $W_n$ be the set of all integers $N$ of the form $p\cdot q$ where $p\equiv q\equiv 3\bmod4$ are prime numbers.

The Intractability Assumption of Factoring (IAF)

Let $k\gt0$ be any fixed number. For any polynomial time probabilistic algorithm for factoring integers, the probability of success for a random input integer from $W_n$ is less than $\frac{1}{n^k}$ for all large $n$.

Definitions

Definition 1 - Recovery Algorithm

A recovery algorithm $R$ for A is a probabilistic polynomial-time algorithm which takes ($n,$$\Delta_A$) as input, and outputs a string $v$.

An optimal recovery algorithm would produce $v=$$u_A$.

Theorems

Some general definitions used by several theorems

Theorem 1

Let $P$ be an intractable puzzle ensemble that is uniquely decipherable. There exists a protocol $M=(M_A,M_B)$ for generating a secret from $P$ that achieves validity and fairness.

Theorem 2

Let $P_A$ and $P_B$ be any two intractable ensembles. There exists a protocol $M=(M_A,M_B)$ for exchanging secrets between $P_A$ and $P_B$ that achieves validity and fairness.

Theorem 3

For any interactive computational problem $\langle$$h_n$$,(f_n,g_n)\rangle$, there exists a protocol $M$ that achieves validity, privacy, and fairness.

Theorem 4

For any interactive computational problem $\langle$$h_n$$,(f_n,g_n)\rangle$, there exists a minimum knowledge transfer protocol $M$ that achieves validity and fairness.

Referencing This Paper

To cite this paper, simply copy and paste the below into your citation:

A.C. Yao. How to Generate and Exchange Secrets (extended abstract). 27th Annual Symposium on Foundations of Computer Science, pages 162-167. IEEE. 1986.

Annotated Paper (extended abstract)

Abstract

In this paper we introduce a new tool for controlling the knowledge transfer process in cryptographic protocol design. It is applied to solve a general class of problems which include most of the two-party cryptographic problems in the literature. Specifically, we show how two parties A and B can interactively generate a random integer $N = pq$ such that its secret, i.e. the prime factors $(p, q)$, is hidden from either party individually but is recoverable jointly if desired. This can be utilized to give a protocol for two parties with private values $i$ and $j$ to compute any polynomially computable functions $f(i,j)$ and $g(i,j)$ with minimal knowledge transfer and a strong fairness property. As a special case, A and B can exchange a pair of secrets $s_A$, $s_B$, e.g. the factorization of an integer and a Hamiltonian circuit in a graph, in such a way that $s_A$ becomes computable by B when and only when $s_B$ becomes computable by A. All these results are proved assuming only that the problem of factoring large integers is computationally intractable.

1. Introduction

A protocol $M=(M_A,M_B)$ is a pair of communicating probabilistic Turing machines each with a special "send-receive" tape. Given inputs of the form $(n,i_A)$ and $(n,i_B)$, the two machines will alternately send and receive message strings using the send-receive tapes; each machine will perform computation as a standard Turing machine after receiving a message string, including the computation of the next message to be sent. Eventually both machines halt within a number of steps bounded by some polynomial in $n$, leaving strings $u_A$ and $u_B$ on the output tapes. For a detailed description, see for example [1][2]; in our case we allow each machine to have their own private input tape. For any run $\sigma$ of the protocol, let $\Delta_A(\sigma)$ denote the history of the run from A's view, i.e. a sequence of the instantaneous descriptions of $M_A$; similarly $\Delta_B(\sigma)$ denote the history of this run from B's view.

The class of problems we are interested in are as follows. Given inputs $(n,i_A)$ and $(n,i_B)$, where $(i_A,i_B)$ is a random pair of strings distributed according to a probability distribution $h_n$ over $\{0,1\}^*\times\{0,1\}^*$, we wish to design a protocol $M=(M_A,M_B)$ such that the outputs ($u_A$$,$$u_B$) are distributed according to a certain probability distribution $w_{n,i_A,i_B}$ over $\{0,1\}^*\times\{0,1\}^*$. The sequence of distributions $(h_1,h_2,\dots,h_n,\dots)$ is assumed to be a polynomial ensemble in the sense that there is a probabilistic Turing machine which, given input $n$, will generate in time polynomial in $n$ a random string $x$ with a distribution indistinguishable computationally from $h_n$; similarly we assume that $w_{n,i_A,i_B}$ is a polynomial ensemble in that a random sample point can be generated in time polynomial in $n$, when the parameters $n,i_A,i_B$ have been given. Let us call this a (two-party) interactive computational problem $\langle$$h_n$,$w_n$$\rangle$. Of special interest is the case when the probability distribution $w_{n,i_A,i_B}$ is nonzero only at one point, call it $(f_n(i_A,i_B),g_n(i_A,i_B))$, in which case we can regard the problem as the evaluation of a pair of functions $f_n(i_A,i_B),g_n(i_A,i_B)$; write it as $\langle h_n,(f_n,g_n)\rangle$.

Instead of defining the sequence of $h_n$'s as a polynomial ensemble, it may be simpler to simply state that, for any $n$, a string $x$ in the distribution $h_n$ can be produced by a probabilistic polynomial-time Turing machine.

In addition to the validity requirement above, we would like the protocol to have certain privacy and fairness properties. Roughly, "privacy" means that if A behaves according to the protocol, then B will have no more information about the values of $i_A$,$u_A$ than in the situation where an oracle does the computation for B and just hands B a value $u_B$. Classical examples where privacy is the main concern include oblivious transfer^[3]^[4], coin tossing^[5]^[6], mental poker^[7]^[8]. A general study of this problem is given by Yao^[9]^[10]. A related problem is the interactive proof system^[1] in which player A wishes to convince player B that a string $\tau$ is in a certain language $L$. Recently, Goldreich, Micali, and Wigderson^[11] proved that, for players with polynomial-time computing power, an language in NP has a minimum knowledge interactive proof, assuming the existence of suitable one-way functions. This latter problem is closely related to, in our formulation, the case of computing a pair of functions $f_n(i_A,i_B),g_n(i_A,i_B)$, where $i_A=(s,\tau),\;i_B=\tau,\;g_n(i_A,i_B)=1$ if and only if $s$ is a short proof for $t\in L$, and $f_n(i_A,i_B)\equiv 1$.

Let's give a more specific example for this final sentence. Let's say our language $L$ is the language Isomorphic, where, given two graphs $G_1,G_2$, $(G_1,G_2)\in L$ if and only if $G_1$ is isomorphic to $G_2$. $\tau$ would be $(G_1,G_2)$ since it's what we hope to prove is in $L$. $s$ would be a proof for their isomorphism, which would be the one-to-one mapping from vertices in $G_1$ to vertices in $G_2.\;g_n$ should be 1 if and only if A is able to produce such a mapping, which could only be so if $s\in L.\;f_n$ does not matter, since $A$ does not mean to learn anything, so it can simply be any value, such as 1.

The "fairness" requirement means that a cheater should not be able to obtain the desired output while denying the other party to find the proper output. The problem of exchanging secrets^[12]^[13]^[14] has this requirement as its main concern.

In this paper, we will give a protocol for performing the computation $\langle$$h_n$,$w_n$$\rangle$ which achieves validity, privacy, and fairness as stated in Theorem 3, under the assumption that factoring large integers is computationally intractable. Many of the existing results mentioned are special cases of this theorem. A particular interesting special case (stated as Theorem 2) is that it allows two parties to exchange secrets, such as the factorization of a publicized integer or the Hamiltonian circuit of a publicized large graph, in a way that the probability of successful cheating can be made arbitrarily small. It is somewhat surprising that the two secrets being exchanged could be of very different apparent complexity, and one would have thought that it is difficult to find an equitable ratio of bits to be maintained during the process of swapping the secrets. Previously Blum^[12] gave a protocol for exchanging prime factors based on several assumptions (see Hastad and Shamir^[15] for discussions); Luby, Micali, and Rackoff^[13], and Vazirani and Vazirani^[14] gave protocols for exchanging secrets which are one bit long.

The proof of Theorem 3 depends on the ability of two parties to generate a random integer $N=p\cdot q$, with its secret $(p,q)$ hidden from each party, but recoverable at a later time by a joint effort. This result is of independent interest, and should serve as another useful tool for cryptographic protocol design. A general form of this result is given as Theorem 1.

Compared with [9][10], which deals with the same general problem, the addition of the fairness property is the new motive which leads to the present work. We should mention that all the protocols considered in this paper for solving the interactive computational problems $\langle$$h_n$,$w_n$$\rangle$ will be independent of $h_n$, as is traditional in considering cryptographic protocols. The main results (Theorems 1,2, and 3) are all proved under the following assumption. Let $W_n$ be the set of all integers $N$ of the form $p\cdot q$ where $p\equiv q\equiv 3\bmod{4}$ are prime numbers.

The Intractability Assumption of Factoring (IAF)

Let $k\gt0$ be any fixed number. For any polynomial time probabilistic algorithm for factoring integers, the probability of success for a random input integer from $W_n$ is less than $\frac{1}{n^k}$ for all large $n$.

2. Terminology

Let $S=(S_1,S_2,\dots)$ and $S'=(S_1',S_2',\dots)$ be polynomial ensembles, where $S_n=(X_n,Y_n)$ and $S_n'=(X_n',Y_n')$ and each is a probability distribution over $\{0,1\}^*\times\{0,1\}^*$. Furthermore, assume that the two ensembles $(X_1,X_2,\dots)$ and $(X_1',X_2',\dots)$ are indistinguishable for polynomial-time computations.

Let $D=(d_1,d_2,\dots)$ be a sequence of predicates $d_n:\;\{0,1\}^*\rightarrow\{0,1\}$, where given $d$ and $n,\,d_n(x)$ can be computed probabilistically in time polynomial in $n$. Define a guessing algorithm $Q_B$ to be a probabilistic algorithm which takes $(n,y)$ as input, where $y\in\{0,1\}^*$, and outputs a 0 or 1 in time polynomial in $n$.

Consider the experiment of taking a random $(x_n,y_n)$ distributed according to $(X_n,Y_n)$. Suppose that one observes the value $y_n$ and tries to guess what the value of $d_n(x_n)$ is by using a guessing algorithm $Q$; let us denote by $r(d_n,X_n,Y_n,Q)$ the probability that a correct guess will be made. We use the notation $\operatorname o$(poly-small) to denote any sequence $(b_1,b_2,\dots)$ that has the property $b_n\in\operatorname o\left(\frac{1}{n^k}\right)$ for all fixed $k$.

$\operatorname o$(poly-small) may be recognizable as the class of all negligible functions. This experiment might be recognized as similar to how a hardcore bit is defined, except, since it is not being applied to one-way functions, there are no defined bounds on the outcome of the experiment.

We write $I_n$$(X_n\;|\;Y_n)\;$$\leq$ $I_n$$(X_n'\;|\;Y_n')$ if $\forall\,D,Q\;\exists\,Q'$ such that $r(d_n,X_n',Y_n',Q')-r(d_n,X_n,Y_n,Q)$$\geq$ $\operatorname o$(poly-small).

Given a set of predicates, for all guessing algorithms $Q$ to be applied on $(X_n,Y_n)$ under those predicates, we can produce a new guessing algorithm $Q'$ that is strictly not worse on $(X_n',Y_n')$ for the same predicates. It might be said that $(X_n',Y_n')$ is strictly not harder to guess on than $(X_n,Y_n)$, regardless of the predicates.

We cannot produce a set of predicates for which it will be easier to guess on $(X_n,Y_n)$ than $(X_n',Y_n')$, and vice versa—so they are equally hard (or easy) to guess on.

A puzzle ensemble $P=(L,F)$ consists of a language $L\in$ BPP and a polynomial-time ensemble $F=(F_1,F_2,\dots)$ where each $f_n$ is a distribution over $\{0,1\}^*\times\{0,1\}^*$; we require further than a random $(s,\tau)$ distributed according to $f_n$ will satisfy $(n,s,\tau)\in L$ with probability 1-$\operatorname o$(poly-small); we will call $s$ a secret of the text $\tau$. Let $T_{P,n}$ denote the distribution of a random $\tau$ taken from the second component of a random $(s,\tau)$ distributed as $f_n$. We will call $P$ intractable if every probabilistic polynomial-time algorithm $S$, when given as input a pair $\cancel{(s,\tau)} (n,\tau)$ where $\tau$ is distributed according to $T_{P,n}$, will fail with probability 1-$\operatorname o$(poly-small) to produce an $s$ satisfying $(n,s,\tau)\in L$.

A puzzle ensemble is a language and a probability distribution over secrets and texts where randomly sampling from the distribution produces an invalid secret/text pair only negligibly often. That puzzle ensemble is intractable if we cannot make an algorithm that can produce a secret given its text with more than negligible probability. Note the likely error in the original form above that would give $S$ the answer to the question it is being asked, as opposed to the security parameter.

For example, let $L=\{(n;\,p,q,N)\;|\;N=p\cdot q;\;p,q$ are $n$-bit primes$\}$, and $f_n$ be the uniform distribution over the set $W_n$. Under the Intractability of Factorization Assumption, the factorization puzzle ensemble $P=(L,F)$ is an intractable puzzle ensemble.

This is because, according to the assumption, given our text $\tau=N$, we will only negligibly often be able to produce the secret $s=(p,q)$ for sufficiently large $n$.

3. Generating a Secret

Let $P=(L,F)$, where $F=(F_1,F_2,\dots,F_n,\dots)$, be an intractable puzzle ensemble. We wish to design a protocol $M=(M_A,M_B)$ which has the following properties for any given $n$:

$M$ generates implicitly a pair $(s,\tau)$ distributed according to $f_n$.
The text $\tau$ will be found out by $M_A$ and $M_B$ as their outputs.
The secret $s$, while computable by A and B jointly based on the information they have at the end of the execution of the protocol, is completely hidden from each party by itself, even if one of them cheats during the execution of the protocol.

We should note that we want $s$ to still be the correct secret for $\tau$ if a party cheats as well.

To simplify the presentation of the result, we restrict ourselves to puzzles that have unique secrets. Let us call a puzzle ensemble $P=(L,F)$ uniquely decipherable if, for every $n,\tau$, there is at most one $s$ satisfying $(n,s,\tau)\in L$. For example, the factorization puzzle ensemble is uniquely decipherable. For a uniquely decipherable puzzle ensemble, we can write it as $P=(\alpha,D)$, where $\alpha=(\alpha_1,\alpha_2,\dots$ and $D=(D_1,D_2,\dots)$ are given by $\alpha_n(\tau)=s$ and $D_n=T_{P,n}$.

Though not explicitly stated, we can note here that $\alpha_n$ is injective, which is what allows us to explicitly define the probability distribution for only $\tau$ (as it must be identical for $s$ by definition of injectivity).

Let $P=(\alpha,D)$ be a uniquely decipherable, intractable puzzle ensemble, where $\alpha=(\alpha_1,\alpha_2,\dots)$ and $D=(D_1,D_2,\dots)$. Formally, we define our requirements on a protocol $M=(M_A,M_B)$ for generating a secret for $P$ as follows. (A or B will sometimes output $u_A$ or $u_B$=Cheating; informally we say that A or B has detected that the other party is cheating.)

3.1. Validity

If both A and B follow the protocol, then

With probability 1-$\operatorname o$(poly-small), $u_A$$=$$u_B$, and their common value $\tau$ is distributed according to a distribution indistinguishable (by polynomial-time computations) from $D_n$.
$I_n^{(\mathcal{J})}$$(a_n(\tau)\;|\;\tau,$$\Delta_j$$)$ $\approx$ $I_n^{(\mathcal{L})}$$(a_n(\tau)\;|\;\tau)$ for $j\in \{A,B\}$, where $\mathcal{J}$ is the stochastic process induced by the execution of the protocol $M=(M_A,M_B)$, and $\mathcal{L}$ is the stochastic process of fetching $\tau$ according to $D_n$.

The ability to guess $a_n(\tau)$ is precisely as difficult whether done through the protocol (and therefore with extra information from the run of the protocol $\Delta_j$), or done by simply taking $\tau$ directly from $D_n$ (which, as discussed above by definition of an intractable puzzle ensemble, is extremely difficult).

$\exists$ a protocol $N=(N_A,N_B)$ which, given input ($\Delta_A,\Delta_B$), computes outputs $v_A,v_B$, with the property that $v_A=v_B$$=a_n(\tau)$ with probability 1-$\operatorname o$(poly-small).

Given $\Delta_A$ and $\Delta_B$ together, a probabilistic polynomial-time algorithm can produce the secret $s$ of $\tau$ with only a negligible probability of failure.

Now to discuss the validity concept when one party, say B, may misbehave. Let $d_n$ be the probability for runs in which $u_A\neq$Cheating, and let $D_n'$ be the probability distribution for $\tau$ when restricted to such runs. If $d_n$ is negligible, then A will almost always catch B cheating, and no further requirement is needed. On the other hand, if $d_n\in\operatorname\Omega\left(\frac{1}{n^t}\right)$ for some fixed $t\gt0$, then we require the following two constraints to be true:

$P'=(\alpha,D')$ is a uniquely decipherable intractable puzzle ensemble, where $D'=(D_1',D_2',\dots)$.
$I_n^{(\mathcal{J})}$$(a_n(\tau)\;|\;\tau,$$\Delta_B)$ $\approx$ $I_n^{(\mathcal{L})}$$(a_n(\tau)\;|\;\tau)$, where $\mathcal{J}$ is the stochastic process induced by the execution of the protocol $M=(M_A,M_B')$, and $\mathcal{L}$ is the stochastic process of fetching $\tau$ according to $D_n'$.

Basically, the distribution of $\tau$ when B cheats successfully is still intractable, and $a_n(\tau)$ is still just as difficult to produce from ($\tau$,$\Delta_B$) as it was from a normally chosen $\tau$. Obviously, the above applies when switching the roles of A and B as well.

To develop the concept of fairness, consider the execution of protocol $M$ and then $N$. If A follows the protocols, we require that the probability for B to obtain $s$ while A cannot recover $s$ to be small.

3.2. Fairness

[B may cheat.] Suppose protocols $M=(M_A,M_B)$ and $N=(N_A,N_B)$ are run with machine pairs $(M_A,M_B'),(N_A,N_B')$. There exists a polynomial-time probabilistic algorithm $Y$ (dependent on $M_B'$ and $N_B'$), which takes a history pair for $M$ and $N$ as input, and outputs a string $w$. We require that if A follows the protocols $M$ and $N$ and then runs $Y$, the probability that $u_A$$=\tau$, $v_B$$=a_n(\tau)$ while $w$$\neq a_n(\tau)$ is $\operatorname o$(poly-small).
[A may cheat.] (Interchange the roles of A and B in (i).)

Theorem 1

Let $P$ be an intractable puzzle ensemble that is uniquely decipherable. There exists a protocol $M=(M_A,M_B)$ for generating a secret from $P$ that achieves validity and fairness.

4. Exchange of Secrets

Let $P_A=(L_A,F_A)$ and $P_B=(L_B,F_B)$ be two intractable puzzle ensembles. Let $(s_A,\tau_A),(s_B,\tau_B)$ be random puzzles distributed according to $F_{A,n}$ and $F_{B,n}$; give $(n,s_A,\tau_A,\tau_B)$ as input to A and $(n,s_B,\tau_A,\tau_B)$ to B. We wish to design a protocol $M=(M_A,M_B)$ that will enable A and B to exchange their secrets $s_A$ and $s_B$ so that neither will be swindled. We state the criteria for the protocol below.

Validity

If both parties follow the protocol, then with probability $1-\operatorname o$(poly-small), $u_B$$=s_A$ and $u_A$$=s_B$.

Fairness

[If B gets $s_A$, then A can compute $s_B$.]
If A follows the protocols and B does not (i.e., $M_B'\neq M_B$), then for any fixed $k$, there exists a probabilistic polynomial-time algorithm S which takes ($n$,$\Delta_A$) as input and outputs a number $v$ such that the following is true:
$$Pr\{(u_B=s_A)\wedge(v\neq s_B)\}\in O\left(\frac{1}{n^k}\right).$$
[If A gets $s_B$, then B can compute $s_A$.] (Interchange A and B in (i).)

Theorem 2

Let $P_A$ and $P_B$ be any two intractable ensembles. There exists a protocol $M=(M_A,M_B)$ for exchanging secrets between $P_A$ and $P_B$ that achieves validity and fairness.

5. General Computation

Consider an interactive computational problem $\langle$$h_n$,$w_n$$\rangle$ as defined in Section 1. We will show that there exists a protocol for it that satisfies some strong privacy and fairness constraints. In this extended abstract, we restrict ourselves to the case when $w_n$ represents a pair of functions $(f_n,g_n)$ to be evaluated, i.e. given inputs $i_A,i_B$, A and B wish to compute $f_n(i_A,i_B)$ and $g_n(i_A,i_B)$. The results can be extended to the general case.

We will consider two variants, which differ in their input-output format. Model I is the natural one, in which the inputs and outputs are as specified in the previous paragraph. However, since in general A does not have any control over the value of $i_B$, a dishonest B can pretend that $i_B$ is an arbitrary value $y$. As a result, the fairness constraint can at most force B to compute the value of $f_n(i_A,y)$ for some $y$. In Model II, A will be given as input $(i_A,p_A,q_A,N_A,N_B,E_{N_B}(i_B))$ where $N_A=p_A\cdot q_A$ is the product of two large primes, and $N_B$ is another integer of two large prime factors used to encode B's parameter $i_B$ as $E_{N_B}(i_B)$; B has as input $(i_B,p_B,q_B,N_B,N_A,E_{N_A}(i_A))$. The integers $N_A$ and $N_B$ are generated from some distributions such that factoring these numbers are computationally intractable; $\operatorname E_N$ can be any probabilistic encryption scheme that is provably secure under the Intractability Assumption of Factoring (e.g. the ones in Alexi, Chor, Goldreich, and Schnorr^[16] or Blum and Goldwasser^[17]). In the output, A, B obtain ($u_A$$,v_A,w_A$) and $\cancel{(u_A,v_A,w_A)}\;$($u_B$$,v_B,w_B$). When both parties behave honestly, $u_A$$=f_n(i_A,i_B), v_A=(p_A',q_A',N_A'),$ and $w_A=\left(N_B', E_{N_B'}\left(g_n(i_A,i_B)\right)\right)$, where $N_A'$ and $N_B'$ are integers which are the products of two large prime factors; similarly for the output of B. Such formats arise quite naturally in concatenating protocols. The privacy and fairness constraints in this model are stronger than the first model.

Notice the error corrected above.

5.1. Model I

We first define the constraints when both parties follow the protocol.

Validity

With probability 1-$\operatorname o$(poly-small), $u_A$$=f_n(i_A,i_B)$ and $u_B$$=g_n(i_A,i_B)$.

Privacy

$I_n^{(\mathcal{J})}$$(i_A,i_B,$$u_A$$\;|\;$$\Delta_B$$,i_B,$$u_B$$)\;$$\approx$ $I_n^{(\mathcal{L})}$$(i_A,i_B,$$u_A$$\;|\;i_B,$$u_B$$)$ where $\mathcal{J}$ is the stochastic process of running $M$ with input from $h$, and $\mathcal{L}$ is the stochastic process of having $(i_A,i_B)$ distributed according to $h$ and $u_A$$=f_n(i_A,i_B),$$u_B$$=g_n(i_A,i_B)$.
(Interchange A and B in (i).)

That is to say, running our protocol will not make it any easier to find the other person's input than it would have been if an oracle had given us the answer.

We now define the constraints when A follows the protocol while B may cheat; that is, B executes the protocol with any $M_B'$. Since $M_B'$ is arbitrary, B can always generate an $i_B'$ and acts as if this is the input value $i_B$. As A can never detect this method of cheating, A has to cooperate and let B know the value of $g_n(i_A,i_B')$. This enables B to control A's output $u_A$, and to probe somewhat into the value of $i_A$; this cannot be prevented if we want to preserve the validity condition for honest parties described above. We shall require that B cannot do more than that. Let us denote by $\mathcal{Z}$ the set $\{0,1\}^*\cup\{$Cheating$\}$, and extend the function $f_n$ by $f_n(i_A,y)=$Cheating if $y=$Cheating.

Let $M_B'$ be any communicating Turing machine, and let $U_n$ be the distribution corresponding to $u_A$ when $(M_A,M_B')$ are used to carry out the protocol.

Validity

There exists a probabilistic polynomial-time algorithm $S$ that takes input $(n,i_B)$ and produces a random $y\in \mathcal{Z}$ such that $U_n$ is indistinguishable from the distribution corresponding to $f_n(i_A,y)$.

Let $\mathcal{J}$ be the stochastic process of running $(M_A,M_B')$ with input $(i_A,i_B)$ distributed according to $h_n$. Let $\mathcal{S}$ be the set of all probabilistic polynomial-time algorithms $S$ that take input $(n,i_B)$ and produce random $y\in \mathcal{Z}$. For any $S\in\mathcal{S}$, let $\mathcal{L}(S)$ be the stochastic process of generating $(i_A,i_B)$ according to $h_n$, running $S$ on input $(n,i_B)$ to produce a random $y$, and defining $u_A$$=f_n(i_A,y),$$u_B$$=g_n(i_A,y)$. Intuitively, B may use $S$ to generate a random $y$, and after that, acts as if $y$ were the value of $i_B$, and otherwise follows the protocol; $\mathcal{L}(S)$ is clearly a less informative process for B in which A simply tells B the value of $u_B$$=g_n(i_A,y)$ without other communications taking place.

Yao wasn't extremely clear here: $\mathcal{J}$ is the first of those two options, in which they run the protocol after B chooses some $y$, whereas $\mathcal{L}$ is the oracle model in which B is simply handed the value $g_n(i_A,y)$.

Privacy

For any $M_B'$, there exists an $S\in\mathcal{S}$ such that $I_n^{(\mathcal{J})}$$(i_A,i_B,$$u_A$$\;|\;$$\Delta_B$$,i_B,$$u_B$$)\;$$\leq$$\;$$I_n$$^{(\mathcal{L}(S))}(i_A,i_B,$$u_A$$\,|\,i_B,$$u_B$$)$.

In words, the probability of recovering extra information during a real run of the protocol is not more likely than the probability of recovering extra information in the oracle model. The key intuition here is that we only need to prove the existence of some $S$ because this is any $M_B'$. In other words, no matter what $M_B'$ does, there is some oracle model (for some input) that would give B at least as much information, if not more.

The fairness concept refers to obtaining the information that one is entitled to. Suppose B wishes to know the value of $g_n(i_A,y)$ for some $y$ other than $i_B$. As we mentioned earlier, B can succeed by pretending $i_B=y$ and otherwise follow the protocol; in the process A will obtain also the value of $f_n(i_A,y)$. The privacy constraint stipulates that no information other than the value of $g_n(i_A,y)$ is conveyed from A to B. The fairness constraint is concerned with whether it is possible for B to stop at some point, once B has the information about $g_n(i_A,y)$, and deny the knowledge of $f_n(i_A,y)$ to A. The following formulation is not the strongest possible version of this constraint, but it is sufficient for some applications such as exchanging secrets of sufficient length. Let $L_n$ denote the set of all possible values of $f_n(i_A,i_B)$ when $(i_A,i_B)$ is distributed according to $h_n$.

Definition 1 - Recovery Algorithm

A recovery algorithm $R$ for A is a probabilistic polynomial-time algorithm which takes ($n$,$\Delta_A$) as input, and outputs a string $v$.

That is to say, a recovery algorithm is any which attempts to determine $f_n(i_A,i_B)$ given what A knows.

Consider a pair $(i_A,i_B)$ distributed according to $h_n$. Let $G$ denote a probabilistic polynomial-time Turing machine that takes $i_B$ as input and outputs $z$; let $\beta_n(G)$ denote the probability that $z=g_n(i_A,i_B)$.

So $G$ tries to come up with $g_n(i_A,i_B)$ given only $i_B$, with success rate $\beta_n(G)$.

Fairness

For any fixed $k$, there exists a recovery algorithm $R$ (dependent on $M_B'$) whose output $v$ satisfies the following condition: $$\operatorname{Pr}\{(u_B=g_n(i_A,i_B))\wedge (v\notin L_n)\}\leq \beta_n(G)+\operatorname O\left(\frac{1}{n^k}\right)$$ for some $G$.

Saying it in words is helpful. For any fixed $k$, we can find a recovery algorithm $R$ and a guessing algorithm $G$ so that the probability that B correctly determined $g_n(i_A,i_B)$ by the end, but that A could not find any possible value for $f_n(i_A,i_B)$ by the end, is only negligibly higher than the probability that B could have just guessed $g_n(i_A,i_B)$ in the first place.

To complete the definitions, we interchange the roles of A and B in the above discussions, which gives the constraints of validity, privacy, and fairness when B follows the protocol and A is cheating.

A protocol is said to achieve validity, privacy, and fairness, if all the above constraints are satisfied.

Theorem 3

For any interactive computational problem $\langle$$h_n$$,(f_n,g_n)\rangle$, there exists a protocol $M$ that achieves validity, privacy, and fairness.

In Model II, the constraints are simpler. The input-output formats are as explained at the beginning of this section.

5.2. Model II

When both A and B follow the protocol, the following is required.

Validity

With probability 1-$o$(poly-small), $u_A$$=f_n(i_A,i_B),v_A=(p_A',q_A',N_A')$ and $w_A=E_{N_B'}(g_n(i_A,i_B))$, where $N_A'$ is the product of $n$-bit primes $p_A'$ and $q_A'$; the distribution of $N_A'$ is such that it is intractable to factor. A dual constraint on B is also required.

Privacy

$I_n^{(\mathcal{J})}$$(i_A,i_B,$$u_A$$\;|\;$$\Delta_B$$,i_B,$$u_B$$,v_B,w_B)\;$$\approx$ $I_n^{(\mathcal{L})}$$(i_A,i_B,$$u_A$$\;|\;i_B,$$u_B$$)$ where $\mathcal{J}$ is the stochastic process of running $M$ with input from $h$, and $\mathcal{L}$ is the stochastic process of having $(i_A,i_B)$ distributed according to $h$ and $u_A$$=f_n(i_A,i_B),$$u_B$$=g_n(i_A,i_B)$.
(Interchange A and B in (i).)

So one can not learn anything extra by having $\Delta, v, w$ that they wouldn't know from the oracle.

If A follows the protocol, but B may cheat and execute some $M_B'$, then let $d_n$ be the probability of runs in which $v_A\neq$Cheating, and let $U_{n,i_B}$ be the probability distribution for $u_B$ when restricted to such runs and with $i_B$ being an input for B. If $d_n$ is negligible, then A will almost always catch B cheating, and no further requirement is needed. On the other hand, if $d_n\in\operatorname\Omega\left(\frac{1}{n^t}\right)$ for some fixed $t\gt0$, then we require the following constraints of Validity and Privacy.

Validity

With probability $d_n-$$\operatorname o$(poly-small), $u_A$$=f_n(i_A,i_B), v_A=(p_A',q_A',N_A')$ and $w_A'=E_{N_B'}(g_n(i_A,i_B))$, where $N_A'$ is the product of $n$-bit primes $p_A'$ and $q_A'$; the distribution of $N_A'$ is such that it is intractable to factor.

Only negligibly often can B both cheat undetectedly and change Alice's output.

Privacy

$I_n^{(\mathcal{J})}$$(i_A,i_B,$$u_A$$\;|\;$$\Delta_B$$,i_B,$$u_B$$,v_B,w_B)\;$$\approx$ $I_n^{(\mathcal{L})}$$(i_A,i_B,$$u_A$$\;|\;i_B,$$u_B$$)$ where $\mathcal{J}$ is the stochastic process induced by the execution of the protocol $M=(M_A,M_B')$, and $\mathcal{L}$ is the stochastic process of being given the value of $u_B$ distributed according to $U_{n,i_B}$.

In other words, cheating undetectedly does not allow B to learn anything more than he would have by using a trusted party.

As in Model I, let $G$ denote a probabilistic polynomial-time Turing machine that takes $i_B$ as input and outputs $z$; let $\beta_n(G)$ denote the probability that $z=g_n(i_A,i_B)$.

Fairness

For any fixed $k$, there exists a recovery algorithm $R$ (dependent on $M_B'$) whose output $s$ satisfies the following condition: $$Pr\{(u_B=g_n(i_A,i_B))\wedge(s\neq f_n(i_A,i_B))\} \leq\beta_n(G)+\operatorname O\left(\frac{1}{n^k}\right)$$ for some $G$.

We can make a recovery algorithm good enough that the probability of B getting $g_n$, but our recovery algorithm not working, is negligible, unless B just guessed by using $G$.

When B follows the protocol and A may cheat, we have a set of requirements obtained from the above ones by switching the roles of A and B.

Theorem 3 is also true for Model II.

6. Connections

We have chosen a semantic definition of privacy, namely, that communications will not enable one to compute more accurately any polynomial-time predicates. In recent literature, an elegant concept of minimum-knowledge transfer protocol was introduced in [1] (and generalized in [2]) to capture the notion of no unintended information disclosure. It is easy to define privacy constraints for our problems in terms of this concept. We can show that the protocols used to prove the theorems also satisfy the minimum knowledge transfer requirements.

Theorem 4

For any interactive computational problem $\langle$$h_n$$,(f_n,g_n)\rangle$, there exists a minimum knowledge transfer protocol $M$ that achieves validity and fairness.

The proofs of the theorems are lengthy, and will be given in the complete paper.

References

S. Goldwasser, S. Micali, and C. Rackoff, "The knowledge complexity of interactive proof systems," Proceedings of 17th Annual ACM Symposium on Theory of Computing, 1985, 291-304.
Z. Galil, S. Habe, and M. Yung, "A private interactive test of a Boolean predicate and minimum-knowledge public-key cryptosystems," Proceedings of 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, 360-371.
M. Rabin, "How to exchange secrets," 1981, unpublished manuscript.
M. Fischer, S. Micali, C. Rackoff, and D. Wittenberg, "An oblivious transfer protocol," 1985, to appear.
M. Blum, "Coin flipping by phone," COMPCON (1982), 133-137.
R. Cleve, "Limits on the security of coin flips when half of the processors are faulty," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 364-369.
A. Shamir, R. Rivest, and L. Adleman, "Mental Poker," MIT Technical Report, 1978.
S. Goldwasser and S. Micali, "Probabilistic encryption and how to play mental poker keeping secret all partial information," Proceedings of 14th Annual ACM Symposium on Theory of Computing, 1982, 365-377.
A.C. Yao. Protocols for secure computations (extended abstract). In Proc. of the 23rd Annu. IEEE Symp. on Foundations of Computer Science. pages 160-164. 1982.
A. Yao, "Protocols for secure computations," in preparation.
O. Goldreich, S. Micali, and A. Widgerson, "Proofs that yield nothing but their validity and a methodology of cryptographic protocol design," Proceedings of 27th Annual IEEE Symposium on Foundations of Computer Science, 1986.
M. Blum, "How to exchange (secret) keys," ACM Transactions on Computer Systems (1983), 175-193.
M. Luby, S. Micali, and C. Rackoff, "How to simultaneously exchange a secret bit by flipping a symmetrically-based coin," Proceedings of 24th Annual IEEE Symposium on Foundations of Computer Science, 1985, 11-22
U. Vazirani and V. Vazirani, "Trapdoor pseudo-random number generators, with applications to protocol design," Proceedings of 24th Annual IEEE Symposium on Foundations of Computer Science, 1985, 23-30.
J. Hastad and A. Shamir, "The cryptographic security of truncated linearly related variables," Proceedings of 17th Annual ACM Symposium on Theory of Computing, 1985, 356-362.
W. Alexi, B. Chor, O. Goldreich, and C.P. Schnorr, "RSA/Rabin bits are 1/2+1/2poly(log n) secure," Proceedings of 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, 449-457.
M. Blum and S. Goldwasser, "An efficient probabilistic PKCS as secure as factoring," Proceedings of Crypto 84, 1984.

Problem with this page?

\(b_1\)	\(b_2\)	\(b_1\wedge b_2\)
\(s_1\)	\(s_3\)	\(s_5\)
\(s_2\)	\(s_3\)	\(s_5\)
\(s_1\)	\(s_4\)	\(s_5\)
\(s_2\)	\(s_4\)	\(s_6\)

\(b_1\)	\(b_2\)	\(b_1\wedge b_2\)
\(s_1\)	\(s_3\)	\(\operatorname E_{s_1}(\operatorname E_{s_3}(s_5))\)
\(s_2\)	\(s_3\)	\(\operatorname E_{s_2}(\operatorname E_{s_3}(s_5))\)
\(s_1\)	\(s_4\)	\(\operatorname E_{s_1}(\operatorname E_{s_4}(s_5))\)
\(s_2\)	\(s_4\)	\(\operatorname E_{s_2}(\operatorname E_{s_4}(s_6))\)