%% List-selection: Last modified by Yevgeniy, Feb 2, 2000
%
% token status: all yours.
%
\documentclass[11pt]{article}
\def\submission{0} % Set to 1 to get submission version

\usepackage{amsfonts}
\usepackage{fullpage}
\usepackage{times}
\usepackage{wrapfig}
%\usepackage{graphics}
\pagestyle{plain}

\ifodd\submission
  \newcommand{\snote}[1]{}
  \newcommand{\tnote}[1]{}
  \newcommand{\ynote}[1]{}
\else 
  \newcommand{\snote}[1]{{\sf [[#1 Shai.]]}}
  \newcommand{\tnote}[1]{{\sf [[#1 Tal.]]}}
  \newcommand{\ynote}[1]{{\sf [[#1 Yevgeniy.]]}}
\fi

%% Yevgeniy: changed the name to Element Selection.
\def\corsel{Correlated Element Selection}
\newcommand{\crsl}[1]{{\sf CES-#1}}
\def\elc{Encrypted List Correspondence}
\def\blc{Blinded List Correspondence}

\iffalse %\ifodd\submission
 %set dimensions of columns, gap between columns, and space between paragraphs
 \setlength{\textheight}{8.75in}
 \setlength{\columnsep}{2.0pc}
 \setlength{\textwidth}{7in}
 \setlength{\topmargin}{0.25in}
 \setlength{\headheight}{0.0in}
 \setlength{\headsep}{0.0in}
 \setlength{\oddsidemargin}{-.25in}
 \setlength{\evensidemargin}{-.25in}
 \setlength{\parindent}{1pc}
\fi

\newcommand{\R}{R}

\def\FullBox{\hbox{\vrule width 8pt height 8pt depth 0pt}} 
\newcommand{\qed}{\;\;\;\FullBox}
\newenvironment{proof}{\noindent{\bf Proof:~~}}{\(\qed\)}

\newtheorem{definition}{Definition}
\newtheorem{idef}{Informal Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{question}{Question}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}

\newcommand{\secref}[1]{Section~\ref{sec:#1}}
\newcommand{\thmref}[1]{Theorem~\ref{thm:#1}}
\newcommand{\defref}[1]{Definition~\ref{def:#1}}
\newcommand{\eqref}[1]{Equation~(\ref{eq:#1})}
\newcommand{\figref}[1]{Figure~\ref{fig:#1}}

\newcommand{\CtoP}{C\longrightarrow P}
\newcommand{\PtoC}{P\longrightarrow C}
\newcommand{\PtoV}{P\longrightarrow V}
\newcommand{\VtoP}{V\longrightarrow P}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\al}{\alpha}
\newcommand{\bt}{\beta}
\newcommand{\tg}{\tilde{g}}
\renewcommand{\th}{\tilde{h}}
\newcommand{\room}{\medskip\noindent} 
\renewcommand{\ni}{\noindent}

\newcommand{\bit}[1]{\{0,1\}^{#1}} 
\newcommand{\brak}[1]{\langle {#1} \rangle}
\newcommand{\eqdef}{\stackrel{\mbox{\tiny def}}{=}}
\newcommand{\equalby}[1]{\stackrel{(\ref{eq:#1})}{=}}
\newcommand{\etc}[2]{{#1},\ldots,{#2}}
\newcommand{\half}{\frac{1}{2}} 
\newcommand{\implies}{\Rightarrow} 
\newcommand{\nin}{\not \in}
\newcommand{\ot}[1]{${{#1} \choose 1}$-OT}
\newcommand{\poly}{poly}
\newcommand{\set}[1]{\{#1\}} 
\newcommand{\ignore}[1]{}
\newcommand{\xor}{\oplus}
\newcommand{\zk}{zero-knowledge}

\newcommand{\calE}{{\cal E}}
\newcommand{\gen}{Gen}
\newcommand{\enc}{Enc}
\newcommand{\dec}{Dec}
\newcommand{\blind}{Blind}
\newcommand{\comb}{Combine}

\newcommand{\pk}{pk}
\newcommand{\sk}{sk}

\newcommand{\nset}[1]{\set{#1_i}_{i=1}^n}
\newcommand{\nlist}[1]{#1_1,\ldots, #1_n}
\newcommand{\pairs}[2]{\set{({#1}_i,{#2}_i)}_{i=1}^n}

\newcommand{\lcs}[1]{
	Lab. of Computer Science, Massachusetts Institute of Technology,
        545 Tech Square, Cambridge, MA 02139, USA.
        Email: {\tt #1@\allowbreak theory.lcs.mit.edu}.}
\newcommand{\ibm}[1]{
	IBM T.J. Watson Research Center, 
	P.O. Box 704, Yorktown Heights, New York 10598, USA.  
	Email: {\tt #1@\allowbreak watson.ibm.com}.}
  

\title{An Efficient Cryptographic Solution to a Game Theoretic Problem}

\ifodd\submission
  \author{Anonymous submission to Crypto'00}
\else
  \author{Yevgeniy Dodis\footnotemark[1] 
          \and Shai Halevi\footnotemark[2] 
          \and Tal Rabin\footnotemark[2]}
  \renewcommand{\thefootnote}{\fnsymbol{footnote}}
  \footnotetext[1]{\lcs{yevgen}}
  \footnotetext[2]{\ibm{\{shaih,talr\}}}
  \renewcommand{\thefootnote}{\arabic{footnote}}
\fi

\date{\today}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% document starts here %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\begin{titlepage}
\maketitle

\begin{abstract}
Although Game Theory and Cryptography seem to address similar scenarios, 
it is very rare to find instances where tools from one area are useful 
in the other. In this work we exhibit such an instance, where cryptographic 
tools can be used to solve a game theoretic problem. 
The problem that we discuss arises naturally in the area of two-party 
strategic games. In these games, each player decides on a ``move'' 
(according to some strategy), and receives a payoff, which depends 
on both moves. Each player only cares to maximize its payoff. 
The standard solution concept for such games is that of an {\em
equilibrium}, which is a pair of ``self-enforcing'' strategies making
each player's strategy an optimal response to the other player's
strategy. It is known that for some games, the expected equilibrium
payoffs can be much higher when a ``mediator'' helps the players
choose dependent self-enforcing strategies ({\em Correlated
equilibria}), than when each player has to choose its strategy on its
own ({\em Nash equilibria}).  
%But the former setting is no longer a two player game, as the players
%require the aid of a trusted mediator. 
Our solution enables the players to choose correlated equilibrium
strategies {\em without the mediator}.
%, while preserving the stability of the game. 
Informally speaking, {\em any Correlated equilibrium payoffs for
2-player games can achieved using a Nash equilibrium}, provided the
players are computationally bounded and can can communicate before
playing the game.

To obtain an efficient solution to the above game-theoretic problem, 
we provide a cryptographic solution to the following {\em \corsel} 
problem. Both Alice and Bob know a list of pairs $(a_1,b_1)\ldots
(a_n,b_n)$ (possibly with repetitions), and they want to pick a 
{\em random} index $i$ such that Alice learns only $a_i$ and Bob 
learns only $b_i$. 
We believe that this problem has other applications, beyond our 
application to game theory. 
%%SHAI1: No need for that in the abstract 
%The special case when all $a_i$'s and $b_i$'s are distinct corresponds 
%to the classical coin flipping (since both players learn $i$).
Our solution is quite efficient: it has constant number of rounds, 
negligible error probability, and uses only very simple {\zk} proofs. 
%similar to the {\em graph isomorphism} ZK protocol. 
\iffalse
  The protocol that we describe in this work uses as a basic building
  block ``blindable encryption schemes'' (such as ElGamal or
  Goldwasser-Micali). We note that such schemes seem to be a very useful
  general primitive for constructing efficient protocols. As an example,
  we show a simple $1$-out-of-$n$ oblivious transfer protocol based on
  any such encryption scheme.
\fi
\end{abstract}

\bigskip

\paragraph{Key words.}
Game theory, Nash equilibria, Correlated equilibria, Element selection, 
Correlated coins, Coin Flipping, Blindable encryption, Oblivious transfer.

\thispagestyle{empty}
\end{titlepage}
%\setcounter{page}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction} \label{sec:intro}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The research areas of Game Theory and Cryptography are both
extensively studied fields with many problems and solutions.  
Yet, the cross-over between them 
%, which seems very natural to expect in certain settings, 
is surprisingly small: very rarely (if at all) are tools
from one area borrowed to address problems in the other.  In this
paper we utilize the benefits which arise in such a combined
setting. Namely, we show how cryptographic tools can be used to
address a natural problem in the Game Theory world.  We hope that this
work will encourage greater interaction between these classical
fields.

\iffalse 
  More specifically we look at two players strategic games and
  show the analysis and solutions which were achieved via game 
  theory means, and then proceed to our new solution using cryptography.  
  The research of the two players game in game theory brought about
  the notion of a Nash equilibria which achieves certain results in
  the game, then it was shown that by modifying the model and inserting
  a trusted third party better results could  be achieved.
  Here we will show that by introducing cryptography we can remove
  the trusted third party but still achieve the improvements that it
  offered.  We will devise cryptographic protocols which are specifically
  suited to solve our problem.
\fi 

\subsection{Two Player Strategic Games}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The game-theoretic problem that we consider in this work belongs to
the general area of {\em two player strategic games}, which is an
important field in Game Theory (see~\cite{book1,book2}).  In the most
basic notion of a two player game, there are two players, each with a
set of possible moves. The game itself consists of each player
choosing a move from its set, and then both players execute their
moves simultaneously. The rules of the game specify a {\em payoff}
function for each player, which is computed on the two moves. Thus,
the payoff of each player depends both on its move and the move of the
other player.  A {\em strategy} for a player is a (possibly
randomized) method for choosing its move. The fundamental assumption
of game theory is that each player is {\em selfish and rational},
i.e. its sole objective is to maximize its (expected) payoff.

A pair of players' strategies achieves an {\em equilibrium} when these
strategies are {\em self-enforcing}, i.e. each player's strategy is an
{\em optimal response} to the other player's strategy. In other words,
once a player has chosen a move and believes that the other player will 
follow its strategy, its (expected) payoff will not increase by changing 
this move.  This notion was introduced in the classical work of Nash 
\cite{nash51}.  

In a {\em Nash equilibrium}, each player chooses its move {\em
independently} of the other player. (Hence, the induced distribution
over the pairs of moves is a product distribution.)  Yet,
Aumann~\cite{aumann} showed that in many games, the players can
achieve much higher expected payoffs, while preserving the
``self-enforcement'' property, if their strategies are {\em
correlated} (so the induced distribution over the pairs of moves is 
no longer a product distribution).  To actually implement such a {\em 
correlated equilibrium}, the model of the game is modified and a 
``trusted third party'' (called a {\em mediator}) is introduced.  This 
mediator chooses the pair of moves according to the right distributions 
and privately tells each player what its designated move is. Since the 
strategies are correlated, the move of one player typically carries some 
information on the move of the other player. In a Correlated equilibrium, 
no player has an incentive to deviate from its designated move, even 
knowing this extra information about the other player's move. 

\subsection{Removing the Mediator} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
As the game was intended for two players, it is natural to ask if 
correlated equilibria can be implemented the without the mediator. 
In the language of cryptography, we ask if we can design a two party 
game to eliminate the trusted third party {from} the original game.  
It is well known that in the standard cryptographic models, the answer 
is positive, provided that the two players can interact, that they are 
computationally bounded, and assuming some standard hardness assumptions 
(\cite{gmw87,yao82b}).  We show that this positive answer carries over 
also to the Game Theory model. Specifically, we consider an {\em extended 
game}, in which the players first exchange messages, and then they choose 
their moves and execute them simultaneously.  
(The payoffs are still computed as a function of the moves, according 
to the same payoff function as in the original game.)  Also, we define 
a {\em computational Nash equilibrium} as one where the strategies of 
both players are restricted to probabilistic polynomial time.
%(in an appropriate security parameter).  
Then, we prove the following: 

\begin{theorem}\label{thm:main}
If secure two-party protocols exist for non-trivial functions, then 
for any Correlated equilibrium $s$ of the original game $G$, there 
exists an extended game $G'$ with a computational Nash equilibrium 
$s'$, such that the payoffs for both players is the same in $s'$ and 
$s$. 
\end{theorem}

In other words, any Correlated equilibrium payoffs of $G$ can be
achieved using a computational Nash equilibrium of $G'$. Thus, the
mediator can be avoided if the players are computationally bounded and
can communicate prior to the game.

We stress that although this theorem is quite natural from a cryptography 
point of view, the models of Game Theory and Cryptography are different 
enough so that proving it in the Game Theory framework requires some 
care. In particular, two-party cryptographic protocols always
assume that at least one player is honest, while the other player 
could be arbitrarily malicious. In the game-theoretic
setting, on the other hand, {\em both players are selfish and
rational}: they (certainly) deviate from the protocol if they benefit
from it, and (can be assumed to) follow their protocol otherwise.
Also, it is important to realize that in this setting we cannot use
cryptography to ``enforce'' honest behavior. The only thing that the
players are able to do is to choose their moves and execute them at
the end of the game. Hence, even the most elaborate protocol would be
useless if a ``cheating player'' can simply ignore the fact that it
was ``caught cheating'' during the protocol, and nonetheless choose a
move that maximizes its profit.  We discuss these issues further in
\secref{chicken}.

\snote{The remark on repeated games may be appropriate for a 
game-theory audience, but not for a crypto audience.}
\iffalse 
  We also remark that the notion of an extended game is very different
  and much less understood than a seemingly related notion of a {\em
  repeated game} (see~\cite{book1}), where the original game is played
  many times, and where essentially any reasonable payoffs can typically
  be ``enforced'' (so called {\em folk theorems}). Extended game still
  plays the original game {\em only once}, but allows the players to
  communicate prior to the game in hope to convince each other to play
  in a ``mutually beneficial'' way, despite the selfishness of both
  the participants.
\fi

\subsection{Doing it Efficiently}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Although the assumption of \thmref{main} can be proven using tools of
generic two-party computations \cite{gmw87,yao82b}, it would be nice
to obtain extended games (i.e. protocols) which are more efficient
than the generic ones.  In \secref{corsel} we observe that for many
cases, the underlying cryptographic problem reduces to a problem which
we call {\em \corsel}. We believe that this natural problem has other
cryptographic application and is of independent interest. 
%(This problem may also have other cryptographic applications.)  
In this problem, two players, $A$ and $B$, know a list of pairs
$(a_1,b_1), \ldots,(a_n,b_n)$ (maybe with repetitions), and they need
to jointly choose a random index $i$, so that player $A$ only learns
the value $a_i$ and player $B$ only learns the value $b_i$.
\footnote{A special case of \corsel\ when $a_i=b_i$ is just the standard 
  {\em coin-flipping} problem~\cite{blum81}. However, this is a degenerate
  case of the problem, since it requires no secrecy.  In particular,
  none of the previous coin-flipping protocols seem to extend to
  solve our problem.
}

%In particular, $A$ does not learn anything about $B$'s value $b_i$ 
%aside from what can be learned from $a_i$ and vice versa.
%While preventing $A$ ($B$) from learning anything about $B$'s 
%($A$'s) value aside from what can be learned from $a_i$ ($b_i$). 

We therefore dedicate a large part of the paper to presenting an
efficient cryptographic solution to the {\corsel} problem.  Our final
protocol is very intuitive, has constant number of rounds, negligible
error probability, and uses only very simple zero-knowledge proofs.
%, similar to the {\em graph isomorphism} proof~\cite{gmw86}
\iffalse 
  \footnote{A special case of \corsel\ when $a_i=b_i$ is just the standard 
  {\em coin-flipping} problem~\cite{blum81}. However, this is a degenerate
  case of the problem, since it requires no secrecy.  In particular,
  none of the previous coin-flipping protocols seem to extend to
  solve our problem.}.
  %We also remark that such a degenerate
  %case will {\em provably} never come up in a Correlated equilibrium
  %achieving payoffs better than the convex combination of what could be
  %achived using Nash equilibria, see~\cite{book1}.)
\fi 
We note that some of our techniques (in particular, the zero-knowledge
proofs) are similar to those used for mixing networks 
(see~\cite{abe,jakobsson98} and the references therein), even though
our usage and motivation are quite different. 


\iffalse 
  One important component in our solution is a simple zero-knowledge
  proof to show that two lists of ciphertexts are encryptions of the same
  list (perhaps with a different order). The proof can be provided in
  two flavors: one where the plaintext list itself is to remain secret,
  and the second where it is known (and the reordering of the list is
  the secret information).  In our application we use the latter
  variant, but our solution can be used for the former variant as well.
  We refer to this as {\em equality of encrypted lists.}
\fi 

Our protocol for \corsel\ uses as a tool {\em blindable encryption}
(which can be viewed as a counterpart of blindable signatures
\cite{chaum82}). Stated roughly, blindable encryption is the
following: given an encryption $c$ of an (unknown) message $m$, and an
additional message $m'$, a random encryption of $m+m'$ can be easily
computed.  This should be done without knowing $m$ or the secret
key. Examples of semantically secure blindable encryption schemes
(under appropriate assumptions) include
Goldwasser-Micali~\cite{GoMi84}, ElGamal~\cite{elgamal84} and
Benaloh~\cite{benaloh}.  (In fact, for our \corsel\ protocol, it is
sufficient to use a weaker notion of blindability, such as the one in
\cite{syy99}.)  Aside from our main application, we also observe that
blindable encryption appears to be a very convenient tool for devising
efficient two-party protocols and suggest that it might be used more
often. To demonstrate that, we show in Appendix~\ref{sec:ot} a very
simple protocol to achieve {\em $1$-out-of-$n$ Oblivious Transfer}
(\ot{n}) protocol from any secure blindable encryption scheme.%
\footnote{It is known that oblivious transfer is complete for two-party 
secure computation~\cite{CrKi88a,kilian}, hence blindable encryption 
schemes are sufficient for secure two-party computation.} 
%This assumption is more general than, for example, commonly used 
%factoring or Diffie-Hellman assumptions, since one can easily build 
%a blindable encryption based on any of these assumptions; see 
%Appendix~\ref{sec:encr}.})

%\begin{remark}[Adaptive OT]{\rm 
%Our \ot{n} protocol seem to generalize naturally to an {\em adaptive}
%${n \choose {k\times 1}}$-OT protocol (where $k$ \ot{n} executions are
%performed adaptively). This protocol is a little bit less efficient
%than the one obtained by Naor and Pinkas~\cite{NaPi99b}
%($O(n)$ initialization and essentially constant time per each 
%new transfer), 
%(rougly, by a factor equal to the logarithm of the error probability
%we wish to achieve), but is extremely simple and based on a slightly
%more general assumption (\cite{NaPi99b} use DDH or the random oracle).
%As in \cite{NaPi99b}, a special care has to be taken to overcome the
%``selective decommitment'' problem. We omit the details from this
%abstract.}
%\end{remark}
%--------------------------------------------------------------------
\subsection{Related Work}
\paragraph{Game Theory.} 
Realizing the advantages of removing the mediator, various papers in
the Game Theory community have been published to try and achieve this
goal.  Barany \cite{barany92} substitutes the trusted mediator with
four (potentially untrusted) players.  These players (two of which
were the actual players who needed to play the game) distributedly
(and privately) computed the moves for the two active players.  This
protocol works in an information-theoretic setting (which explains the
need for four players; see \cite{bgw88}).  Of course, if one is
willing to use a group of players to simulate the mediator, then the
general multiparty computation tools (e.g. \cite{bgw88,ccd88}) can
also be used, even though the solution of \cite{barany92} is simpler
and more efficient.  The work of Lehrer and Sorin \cite{ls94}
describes protocols that ``reduce'' the role of the mediator (the
mediator in this protocol computes some function on values which the
players chose).

%--------------------------------------------------------------------
\paragraph{Cryptography.}  
We already mentioned that in principle, the problem of eliminating a
``trusted third party'' from a two party protocol can be solved using
generic tools for two-party secure computations \cite{gmw87,yao82b}.
Yet, those solutions are too generic to be practical.  As previously
stated some of the tools which we use to solve the {\corsel} problem are
closely related to the verification procedures for the mix-networks in
\cite{jakobsson98,abe}.  
%Yet, these solutions provide only a first
%step towards the complete solution which we require.

\iffalse 
  The goal in these networks 
  is to permute and re-encrypt a list of encryptions without revealing
  the random permutation used. This is done collectively by many
  ``mix-servers'' (rather than a single player), and the emphasis is to
  protect against cheating mix-servers.  Not surprisingly, our simple
  ``graph-isomorphism'' kind of zero-knowledge protocol is similar in
  flavor to the techniques used by Abe~\cite{abe}, who constructed
  mix-networks using ElGamal encryption.  Yet, these protocols are
  only the first step to solving the \corsel\ problem  as they don't 
  enable the special exposer of a single element which we require.
\fi

Encryption schemes with various ``blinding properties'' were used for
many different purposes, including among others
% rosario said that he doesnt know any scheme using blindable encryption for
% voting.  benahloh uses just the homomorphic properties and others
% if they use anything  blinded it's signatures.
secure storage \cite{ggjr97}, mixing-networks \cite{jakobsson98,abe}
and secure circuit evaluations \cite{syy99}. 
\iffalse
  more general equilibria, Moti's paper using random self-reducible
  encryption. Coin flipping maybe? 
  Also, the 2 papers of beaver on correlated
  pseudo-randomness and commodity-based cryptography. Also, Ishai/Gilboa
  paper this crypto on compressing cryptoresources.  Finally, maybe
  mention that recently other game theory aspects are of interest to CS,
  e.g. paper by Nisan/Ronen on mechanism design and
  Koutsoupias/Papadimitriou on worst-case equilibria. Anything else???
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{An Application to Game Theory} \label{sec:games}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Two-player Games.} Although our results apply to a much
larger class of two-player games\footnote{For example, {\em extensive
games with perfect information and simultaneous moves}.}, we
demonstrate them on the simplest possible class of finite {\em
strategic games} (with perfect information). Such a game $G$ has two
players $1$ and $2$, each of whom has a finite set $A_i$ of possible
{\em actions} and a {\em payoff function} $u_i:A_1\times A_2 \mapsto
\R$ ($i=1,2$), known to both players. The players move simultaneously,
each choosing an action $a_i \in A_i$. The {\em payoff} of player $i$
is $u_i(a_1,a_2)$. The (probabilistic) algorithm that tells player
$i$ which action to take is called its {\em strategy},
% (which in our case corresponds to choosing a single action), 
and a pair of strategies is called a {\em strategy profile}.  In our
case, a strategy $s_i$ of player $i$ is simply a probability
distribution over its actions $A_i$, and a strategy profile
$s=(s_1,s_2)$ is a probability distribution over $A_1\times A_2$.
Game theory assumes that each player is {\em rational}, i.e. only
cares about maximizing its (expected) payoff.
%Each player wants to choose a strategy that maximizes its (expected)
%payoff.
%The fundamental assumption of game
%theory is that the players are {\em rational}, i.e. each
%player only tries to maximize his own payoff, and this fact
%is known to both players. 
%The basic task of game theory is to model which behaviors (i.e.
%strategy profiles) are reasonable to expect (or explain) when the game
%is actually played. 
%Rationality implies that the solution concept that ``makes sense'' is
%that of an {\em equilibrium}. 
As a result, we are interested in strategy profiles that are {\em
self-enforcing}. In other words, even knowing the strategy of the
other player, each player still has no incentive to deviate from its
own strategy. Such a strategy profile is called an {\em equilibrium}.
% (the one prescribed to him by the
%equilibrium) conditioned on his knowledge or {\em belief} about the
%other player's strategy. 
%The following anecdotal argument illustrates the concept of
%self-enforcing strategies: ``My wife drives because I drink, and I
%drink because my wife drives''.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Nash equilibrium.} This is the best known notion of an 
equilibrium \cite{nash51}. 
It corresponds to a strategy profile in which players'
strategies are {\em independent}.  More precisely, the induced
distribution over the pairs of actions, must be a product
distribution, $s(A_1 \times A_2) = s_1(A_1) \times s_2(A_2)$.
%given a finite set $S$, we denote by 
%$\Delta(S)$ be the set of all probability distributions on $S$. Then a
%strategy $s_i$ of player $i$ is a member of $\Delta(A_i)$, i.e. player
%$i$ plays each $a_i\in A_i$ with probability $s_i(a_i)$.
%(we say that
%any $a_i$ with $s_i(a_i)>0$ is in the {\em support} of
%$s_i$). 
Deterministic (or {\em pure}) strategies are a special case of
independent strategies, where $s_i$ assigns probability 1 to some
action.  For strategies $s_1$ and $s_2$, we denote by $u_i(s_1,s_2)$
the {\em expected} payoff for player $i$ when players independently
follow $s_1$ and $s_2$.

\begin{definition}
A {\em Nash equilibrium} of a game $G$ is a strategy profile
$(s_1^*,s_2^*)$, such that for any $a_1\in A_1$, $a_2\in A_2$, 
we have 
$u_1(s_1^*,s_2^*) \ge u_1(a_1,s_2^*)$ 
and $u_2(s_1^*,s_2^*)\ge u_2(s_1^*,a_2)$.
\end{definition}

\noindent
In other words, given that player $2$ follows $s_2^*$, $s_1^*$ is an
optimal response of player $1$ and vice versa.  
%%SHAI: No need to formally define this
%The pair $[u_1(s_1^*,s_2^*), u_2(s_1^*, s_2^*)]$ is called a pair 
%of {\em Nash equilibrium payoffs} of $G$. One can show that each 
%game $G$ has at least one Nash equilibrium. 


%-----------------------------------------------------------------
\paragraph{Correlated equilibrium.} 
While Nash equilibrium is quite a natural and appealing notion (since 
players can follow their strategies independently of each other), one 
can wonder if it is possible to achieve higher expected payoffs if one 
allows {\em correlated} strategies. 

\ignore{
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \paragraph{Public Coins.} One way to allow correlation is to give
  players {\em public coins}, i.e. let them observe common and truly
  random coin flips. For example, player can coordinate which Nash
  equilibrium to play depending on the outcome of the coin flip. More
  generally, they can achieve any pair of payoffs inside the {\em convex
  hull} of Nash equilibrium payoffs of $G$. It is not hard to see that
  the no other Nash equilibrium payoff is possible with public coins.
  What happens if we allow {\em arbitrary} correlation?
} % end ignore

In a correlated strategy profile \cite {aumann}, the induced distribution over 
$A_1\times A_2$ can be an arbitrary distribution, not necessarily 
a product distribution. This can be modeled by having a trusted party 
(called {\em mediator}) sample a pair of actions $(a_1,a_2)$ according 
to some {\em joint} probability distribution $s(A_1\times A_2)$, 
and ``recommend'' the action $a_i$ to player $i$. 
%We denote by $s_i$ the marginal distribution of player's $i$. 
%recommended actions, so $p=(s_1,s_2)$. 
We stress that knowing $a_i$, player $i$ now knows a {\em conditional
distribution} over the actions of the other player (which can be
different for different $a_i$'s), but knows nothing more. We denote
these distributions by $s_2(\cdot\mid a_1)$ and $s_1(\cdot\mid a_2)$.
As before, we let $u_i(s)$ be the expected value of $u_i$ when
$(a_1,a_2)$ are drawn according to $s$.

For any $a_1'\in A_1, a_2'\in A_2$, let $u_1(a_1', s_2\mid a_1)$ be
the expected value of $u_1(a_1',a_2)$ when $a_2$ is distributed
according to $s_2(\cdot\mid a_1)$ (similarly for $u_2(s_1,a_2'\mid
a_2)$).  In other words, $u_1(a_1', s_2\mid a_1)$ measures the
expected payoff of player 1 if his recommended action was $a_1$ (thus,
$a_2$ is distributed according to $s_2(\cdot\mid a_1)$), but it
decided to play $a_1'$ instead.  Similarly to the notion of Nash
equilibrium, we now define a {\em Correlated equilibrium}, which
requires that players always want to follows the ``recommendation''
they got from the mediator.

\begin{definition}
A {\em Correlated equilibrium} is a strategy profile $s^*=s^*(A_1
\times A_2)=(s_1^*,s_2^*)$, such that for any $(a_1^*,a_2^*)$ in the
support of $s^*$, and any $a_1\in A_1$ and $a_2\in A_2$, we have
$u_1(a_1^*,s_2^*\mid a_1^*)\ge u_1(a_1,s_2^*\mid a_1^*)$ and
$u_2(s_1^*,a_2^*\mid a_2^*)\ge u_2(s_1^*,a_2\mid a_2^*)$.
\end{definition}

%Nash equilibrium is a special case when $(s_1^*,s_2^*)\in
%\Delta(A_1) \times \Delta(A_2)$.  
It is known that Correlated equilibria can give equilibrium payoffs
{\em outside} (and better!)  than anything in the convex hull of Nash
equilibria payoffs, as demonstrated in the following simple example
first observed by Aumann~\cite{aumann}, who defined the notion of
Correlated equilibrium.
%In particular, {\em correlated coins (where each player learns only 
%his ``half'' of the coin) are strictly more powerful than public coins}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{wrapfigure}{r}{1.5in}
%\fbox{
%\begin{minipage}[t]{1.5in}
\begin{tabular}{lc|c|c}
& \multicolumn{1}{c}{C} & \multicolumn{1}{c}{D}&\\ \cline{2-3}
\cline{2-3}
\multicolumn{1}{l|}{~~~C} & 4,4 & 1,5&\\ \cline{2-3}
\multicolumn{1}{l|}{~~~D} & 5,1 & 0,0&\\ \cline{2-3}
\\ \multicolumn{4}{c}{\em Game of ``Chicken''}\\ \\
& \multicolumn{1}{c}{C} & \multicolumn{1}{c}{D}&\\ \cline{2-3}
\cline{2-3}
\multicolumn{1}{l|}{~~~C} & 1/4 & 1/4&\\ \cline{2-3}
\multicolumn{1}{l|}{~~~D} & 1/4 & 1/4&\\ \cline{2-3}
\\ \multicolumn{4}{c}{\em Nash Eq. Distrib.}\\ \\
& \multicolumn{1}{c}{C} & \multicolumn{1}{c}{D}&\\ \cline{2-3}
\cline{2-3}
\multicolumn{1}{l|}{~~~C} & 1/3 & 1/3&\\ \cline{2-3}
\multicolumn{1}{l|}{~~~D} & 1/3 &  0&\\ \cline{2-3}
\\ \multicolumn{4}{c}{\em Correlated Eq. Distrib.}\\
\end{tabular}
%}
%\end{minipage}
\end{wrapfigure}
\paragraph{Game of ``Chicken''.} \label{sec:chicken}
We consider a simple $2\times 2$ game, the so called game of
``Chicken'' shown in the table to the right (much more dramatic
examples can be shown in larger games).  Here each player can either
``dare'' ($D$) or ``chicken out'' ($C$).  The combination $(D,D)$ has
a devastating effect on both players (payoffs $[0,0]$), $(C,C)$ is
quite good (payoffs $[4,4]$), while each player would ideally prefer
to dare while the other chickens-out (giving him $5$ and the opponent
$1$).  While the ``wisest'' pair of actions is $(C,C)$, this is not a
Nash equilibrium, since both players are willing to deviate to $D$
(believing that the other player will stay at $C$). The game is easily
seen to have three Nash equilibria: $s^1=(D,C)$, $s^2=(C,D)$ and $s^3
= (\frac{1}{2}\cdot D + \frac{1}{2}\cdot C, \frac{1}{2}\cdot D +
\frac{1}{2}\cdot C)$. The respective Nash equilibrium payoffs are
$[5,1]$, $[1,5]$ and $[\frac{5}{2}, \frac{5}{2}]$.  We see that the
first two pure strategy Nash equilibria are ``unfair'', while the last
mixed equilibrium has small payoffs, since the mutually undesirable
outcome $(D,D)$ happens with non-zero probability in the product
distribution.  The best ``fair'' equilibrium in the convex hull of the
Nash equilibria is the combination $\frac{1}{2} s^1 + \frac{1}{2} s^2
= (\frac{1}{2}(C,D) + \frac{1}{2}(D,C))$, yielding payoffs $[3,3]$.
On the other hand, the profile $s^* = (\frac{1}{3}(C,D) +
\frac{1}{3}(D,C) + \frac{1}{3}(C,C))$ is a correlated equilibrium,
yielding payoffs $[3\frac{1}{3}, 3\frac{1}{3}]$, which is better than
any convex combination of Nash equilibria.

To briefly see it, consider the ``row player'' $1$ (same works for
player $2$). If it is recommended to play $C$, its expected payoff is
$\frac{1}{2}\cdot 4 + \frac{1}{2}\cdot 1 = \frac{5}{2}$ since,
conditioned on $a_1=P$, player $2$ is recommended to play $C$ and $D$
with probability $\frac{1}{2}$ each. If player $1$ switched to $D$,
its expected payoff would still be $\frac{1}{2}\cdot 5 +
\frac{1}{2}\cdot 0 = \frac{5}{2}$, making player $1$ reluctant to
switch. Similarly, if player $1$ is recommended $D$, it knows that
player $2$ plays $C$ (as $(D,D)$ is never played in $s^*$), so its
payoff is $5$. Since this is the maximum payoff of the game, player
$1$ would not benefit by switching to $C$ in this case. Thus, we
indeed have a Correlated equilibrium, where each player's payoff is
$\frac{1}{3}(1+5+4)=3\frac{1}{3}$, as claimed.

\ignore{We note that $s^*$ completely eliminates the mutually undesirable
  $(D,D)$, and puts as high ``mass'' as possible on the desirable
  (non-Nash) outcome $(C,C)$, just small enough so that none of the
  players would deviate to $D$ when recommended $C$.
} %\end ignore

\ignore{
  To show it, consider player $1$ (same argument works for player
  $2$). If player $1$ is recommended $P$, his expected payoff is
  $\frac{1}{2}\cdot 4 + \frac{1}{2}\cdot 1 = \frac{5}{2}$ since,
  conditioned on $a_1=P$, player $2$ will play $P$ and $W$ with
  probability $\frac{1}{2}$ each. If player $1$ switched to $W$, player
  still got a recommendation to play $P$ and $W$ with probability
  $\frac{1}{2}$ each. Thus, expected payoff of player would be
  $\frac{1}{2}\cdot 5 + \frac{1}{2}\cdot 0 = \frac{5}{2}$. Hence, player
  $1$ is indifferent, and thus reluctant to switch. If player's $1$
  recommendation is $W$, he knows that player $2$ plays $P$ (as $(W,W)$
  is never played), so his payoff is $5$. If he switched to $P$, player
  $2$ still plays $P$, so player's $1$ payoff would decrease to
  $4$. Hence, $(s_1, s_2)$ is indeed a Correlated equilibrium with each
  player's expected payoff equal to $\frac{1}{3}(1+5+4)=3\frac{1}{3}$,
  as claimed.  We note that the profile completely eliminates the
  mutually undesirable $(W,W)$. On the other hand, it puts as high
  ``mass'' as possible on the desirable (non-Nash) outcome $(P,P)$, just
  small enough so that none of the players would deviate to $W$ when
  recommended $P$.
} % end ignore

\paragraph{Marrying Cryptography and Game Theory.} 
In this section we shall show that we can remove the mediator
using cryptographic means.  We shall assume the existence of a
generic two party protocol which satisfies our requirements and
show how to plug it into the game and further prove that it
does maintains the game theory properties.

As we have defined in the introduction the union of the cryptographic
protocol and the game will be termed the {\em extended game}.
We shall assume two players who are computationally bounded.
The extended game will be composed of three parts:  in the first
the players will carry out the two party cryptographic protocol, then
each player will decide locally what its move is, and finally both
players will execute their move simultaneously and by that complete
the game.

The cryptographic protocol which the players will carry out is
one which achieves the actions carried out by the mediator, i.e. 
a correlated strategy is chosen and 
each player is provided with its designated move.  In Section 
\ref{sec:corsel} we will give a specific implementation of this protocol.
We stress that the players always remain rational, even when running
the cryptographic protocol. In order to prove Theorem \ref{thm:main}
we start by proving the following lemmas.
\begin{lemma}
The players will
be willing to follow the cryptographic protocol. 
\end{lemma}

\proof
Technically speaking, 
our solution is a Nash equilibrium of the extended game, where
the players can talk before choosing their simultaneous actions,
which we call the {\em Computational Nash equilibrium}.
We remark that permitting
the players to communicate before choosing their actions clearly does
not allow us to obtain a Nash equilibrium whose payoffs are better
than what is achievable by a Correlated equilibrium of the original
game, so our result is the best possible.  This means that the
cryptographic protocol could not ``create'' a better equilibrium
point (say for example, always choosing $(C,C)$) to improve the
payoffs of the players.

As the cryptographic protocol introduces a situation where one
player might cheat and the other can ``catch'' him, we need to state
what would happen under these circumstances in the extended game.
We will employ the standard game-theory solution which is to
punish the cheating player to his {\em minimax level} (the minimax
level of player $2$ is the smallest payoff that player $1$ can force
player $2$ to have, i.e. $\min_{s_1} \max_{s_2} u_2(s_1,s_2)$.)  And
we proceed by proving that:
\begin{lemma}
The extended game maintains the equilibrium of the correlated
game, i.e. the computational Nash equilibrium.
\end{lemma}

\proof
The payoff which is achieved after the punishment for cheating 
is never more (and typically much less) than the equilibrium
payoff that we are trying to implement. Indeed, any
equilibrium profile $(s_1,s_2)$ achieves a better payoff for player
$2$ than its minimax payoff, since $s_2$ is the best response to
$s_1$. Thus, if we have a solution where cheating is detected with
very high probability, the risk of getting caught out-weights the
benefits of cheating, and players will not have an incentive to
deviate from the protocol. In this context, a particular type of
cheating is early stopping. Since the extended game must always result
in players getting payoffs, stopping is not an issue in game theory,
since it will be punished by the minimax level as well.

In the two-party cryptographic protocol setting we have as a standard 
assumption that at least one of the players is honest (clearly,
if both are dishonest then the protocol cannot guarantee anything).
In game theory, on the other hand, no player is assumed to be honest.
Rather, it is assumed that players will deviate from their protocol if
this will increase their expected payoff.  Luckily, in the definition
of equilibria that we consider, the player only considers the benefits
of cheating assuming that the other player follows its prescribed
strategy (i.e. behaves honestly). Thus the players maintain 
an ``honesty equilibrium'', i.e. they force each other to act
according to the protocol, which enables to have the proper setting
for the cryptographic protocol. A final question is why would a
player want to carry out a ``minimax punishment'' when it catches the
other player cheating. Again, our notion of equilibrium only
requires player's actions to be optimal {\em provided the other player
is honest}. Thus, it is acceptable to carry out the punishment even if
this results in a loss for both players: the cheating player should
have been rational and should not have cheated in the first place.

The above lemmas prove Theorem \ref{thm:main}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The \corsel\ Problem} \label{sec:prot}\label{sec:corsel} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In most common games, the joint strategy of the players is described 
by a short list of pairs $\{\mathsf{move1, move2}\}$, where the strategy 
is to choose at random one pair from this list, and have Player~1 play 
$\mathsf{move1}$ and Player~2 play $\mathsf{move2}$. (For example, in 
the game of chicken the list consists of three pairs $\{(D,C),(C,D),
(C,C)\}$.)%
\footnote{Choosing from the list with distribution other than the 
uniform can be accommodated by having a list with repetitions, where 
a high-probability pair appears many times.}\ 

Hence, to obtain an efficient solution for such games, we need an 
efficient cryptographic protocol for the following problem: Two players, 
$A$ and $B$, know a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$ (maybe 
with repetitions), and they need to jointly choose a random index $i$, 
and have player $A$ learn only the value $a_i$ and player $B$ learn only 
the value $b_i$.  We call this problem the {\em \corsel} problem.  In this 
section we describe our efficient solution for this problem. We start by 
presenting some notations and tools that we use (in particular, ``blindable 
encryption schemes''). We then show a simple protocol that solves this 
problem in the special case where the two players are ``honest but curious'', 
and explain how to modify this protocol to handle the general case where 
the players can be malicious. 

\subsection{Notations and Tools}\label{sec:tools}
%==========================================================
We denote by $[n]$ the set $\{1, 2, \ldots n\}$.  For a
randomized algorithm $A$ and an input $x$, we denote by $A(x)$ the
output distribution of $A$ on $x$, and by $A(x; r)$ we denote the
output string when using the randomness $r$. If one of the inputs to
$A$ is considered a ``key'', then we write it as a subscript (e.g.,
$A_k(x)$).  We use $\pk, \pk_1, \pk_2, \ldots$ to denote public keys
and $\sk, \sk_1, \sk_2, \ldots$ to denote secret keys.

The main tool that we use in our protocol is {\em blindable encryption
schemes}.  Like all public key encryption schemes, blindable
encryption schemes include algorithms for key-generation, encryption
and decryption. In addition they also have a ``blinding'' and 
``combining'' algorithms.  
\iffalse 
  that given a message and an encryption of another message generates 
  an encryption of some combination of the two messages. 
  An additional ``combining'' function is also required and it is used in
  the following.
  We require that if we execute two consecutive blindings
  on a cipher $c$ with messages $m_1$ and $m_2$ and randomness $r_1,r_2$
  resp. then this would be equivalent to blinding $c$ by
  $m_1 +m_2$ with randomness which is generated via the combing function.
  A more formal definition of the blinding and combing functions
  follows.
\fi
We denote these algorithms by ${\gen}$, ${\enc}$, ${\dec}$, 
${\blind}$, and ${\comb}$, respectively. Below we formally define 
the blinding and combing functions. In this definition we assume 
that the message space $M$ forms a group (which we denote as an 
additive group with identity $0$).

\begin{definition}[Blindable encryption]
A public key encryption scheme $\calE$ is {\em blindable} if there exist 
(PPT) algorithms {\blind} and {\comb} such that for every message $m$ and 
every ciphertext $c \in \enc_{\pk}(m)$: 
\begin{itemize}
\item For any message $m'$ (also referred to as the ``blinding factor''), 
$\blind_{\pk}(c,m')$ 
produces a {\em random} encryption of $m+m'$. Namely, the distribution 
$\blind_{\pk}(c,m')$ should be equal to the distribution 
$\enc_{pk}(m+m')$. 
\begin{equation}\label{eq:1} 
\enc_{\pk}(m+m') \equiv \blind_{\pk}(c,m')
\end{equation}

\item If $r_1, r_2$ are the random coins used by two successive 
``blindings'', then for any two blinding factors $m_1,m_2$, 
\begin{equation}\label{eq:2} 
  \blind_{\pk}(\blind_{\pk}(c,m_1;~r_1),m_2;~r_2) = 
  \blind_{\pk}(c, m_1+m_2;~\comb_{\pk}(r_1,r_2))
\end{equation}
\end{itemize}
\end{definition}
Thus, in a blindable encryption scheme anyone can ``randomly translate'' 
the encryption $c$ of $m$ into an encryption of $m+m'$, without 
knowledge of $m$ or the secret key, and there is an efficient way 
of ``combining'' several blindings into one operation. 

Both the ElGamal and the Goldwasser-Micali encryption schemes can
be extended into blindable encryption schemes.  We note that most 
of the components of our solution are independent of the specific
underlying blindable encryption scheme, but there are some aspects 
that still have to be tailored to each scheme. 
(Specifically, proving that the key generation process was done
correctly is handled differently for different schemes. See
\secref{keygen}). The reader is referred to \secref{encr} for further
discussion of the blindable encryption primitive.


\subsection{A Protocol for the Honest-but-Curious Case} \label{sec:honest}
%==========================================================
Let us recall the {\corsel} problem. Two players share a public list 
of pairs $\pairs{a}{b}$. 
For reasons that will soon become clear, we call the two players the 
``Preparer'' ($P$) and the ``Chooser'' ($C$). The players wish to pick 
a random index $i$ such that $P$ only learns $a_i$ and $C$ only learns 
$b_i$. 

\figref{honest} describes the {\corsel} protocol for the
honest-but-curious players. We employ a
semantically secure blindable encryption scheme and for simplicity, we
assume that the keys for this scheme were chosen by a trusted party
ahead of time and given to $P$, and that the public key was also given
to $C$.  We briefly discuss some key generation issues in
\secref{keygen}.

\begin{figure}[t]
\begin{center}
{\sf\large Protocol \crsl{1}}

\smallskip
\fbox{
\begin{minipage}{4in}
\begin{tabbing}
123\=1234567890\=123\=123\=123\=123\=123\=123\=123\=123\=123\=123\=\kill
{\it Common inputs}: List of pairs $\pairs{a}{b}$, public key $pk$. \\
{\it Preparer knows}: secret key $sk$. \\
\\
\> $P:$\> {\bf 1. Permute and Encrypt}.\\
\>\> Pick a random permutation $\pi$ over $[n]$. \\ 
\>\> Let $(c_i, d_i) = (\enc_{\pk}(a_{\pi(i)}),~\enc_{\pk}(b_{\pi(i)}))$, 
     for all $i\in[n]$.\\ 
\>\> Send the list $\pairs{c}{d}$ to $C$. \\ 
\\ 
\> $C:$ \> {\bf 2. Choose and Blind}.\\
\>\> Pick a random index $\ell\in [n]$, and a random blinding factor $\bt$.\\
\>\> Let $(e, f) = (\blind_{\pk}(c_{\ell},0),~\blind_{\pk}(d_{\ell},\bt))$.\\
\>\> Send $(e,f)$ to $P$. \\ 
\\
\> $P:$ \> {\bf 3. Decrypt and Output}.\\
\>\> Set $a=\dec_{\sk}(e)$, $\tilde{b}=\dec_{\sk}(f)$. Output $a$.\\
\>\> Send $\tilde{b}$ to $C$.\\ 
\\
\> $C:$ \> {\bf 4. Unblind and Output}.\\ 
\>\> Set $b=\tilde{b}-\bt$. Output $b$.
\end{tabbing}
\end{minipage}
}
\caption{Protocol for {\corsel} in the honest-but-curious model.}
\label{fig:honest}
\end{center}
\end{figure}

The protocol is very simple: First the Preparer randomly permutes the
list, encrypts it element-wise and sends the resulting list to the
Chooser. (Since the encryption is semantically secure, the Chooser
``cannot extract any useful information'' about the permutation
$\pi$.)  The Chooser picks a random pair of ciphertexts $(c_{\ell},
d_{\ell})$ from the permuted list (so the final output pair will be
the decryption of these ciphertexts).  It then blinds $c_{\ell}$ with
$0$ (i.e. makes a random encryption of the same plaintext), blinds
$d_{\ell}$ with a random blinding factor $\bt$, and sends the
resulting pair of ciphertexts $(e,f)$ back to the Preparer.
Decryption of $e$ gives the Preparer its element $a$ (and nothing
more, since $e$ is a {\em random} encryption of $a$ after the blinding
with $0$), while the decryption $\tilde{b}$ of $f$ does not convey
the value of the actual encrypted message 
since it was blinded with a random blinding factor. The Preparer sends
$\tilde{b}$ to the Chooser, who recovers his element $b$ by
subtracting the blinding factor $\bt$.

It is easy to show that if both players follow the protocol then their 
output is indeed a random pair $(a_i,b_i)$ from the known list. Moreover, 
at the end of the protocol the Preparer has no information about $b$ 
other than what's implied by its own output $a$, and the Chooser gets 
``computationally no information'' about $a$ other than what's implied 
by $b$. Hence we have: 

\begin{theorem} \label{thm:honest}
Protocol \crsl{1} securely computes the (randomized) function 
of the {\corsel} problem in the honest-but-curious model.
\end{theorem}

\noindent{\em Proof omitted.}

\subsection{Dealing with Dishonest Players} \label{sec:dishonest}
%==========================================================
\paragraph{Generic transformation.}
Following the common practice in the design of secure protocols, one 
can modify the above protocol to deal with dishonest players by adding 
appropriate zero-knowledge proofs.  That is, after each flow of the 
original protocol, the corresponding player proves in zero knowledge 
that it indeed followed its prescribed protocol: 
After Step~1, the 
Preparer proves that it knows the permutation $\pi$ that was used to 
permute the list. After Step~2 the Chooser proves that it knows the 
%permutation $\rho$, 
index $\ell$ and the blinding factor that was used to produce the pair
$(e,f)$.  Finally, after Step~3 the Preparer proves that the plaintext
$\tilde b$ is indeed the decryption of the ciphertext $f$. Given these
\zk\ proofs, one can appeal to general theorems about secure two-party
protocols, and prove that the resulting protocol is secure in the
general case of potentially malicious players.

We note that the zero-knowledge proofs that are involved in this protocol 
can be made very efficient, so even this ``generic'' protocol is quite 
efficient (these are essentially the same proofs that are used for 
mix-networks in \cite{abe}, see \secref{zkp}).  However, a closer 
look reveals that one does not need all the power of the generic 
transformation, and the protocol can be optimized in several ways. 

%----------------------------------------------------------
\paragraph{Proof of proper decryption.}
To withstand malicious players, the Preparer $P$ must ``prove'' 
that the element $\tilde b$ that it send in Step~3 of \crsl{1} is a 
proper decryption of the ciphertext $f$.  However, this can be done 
in a straightforward manner without requiring zero-knowledge proofs.  
Indeed, the Preparer can reveal additional information (such as the 
randomness used in the encryption of $f$), as long as this extra 
information does not compromise the semantic security of the ciphertext 
$e$.  The problem is that $P$ may not be able to compute the randomness 
of the blinded value $f$ (for example, in ElGamal encryption this would 
require computation of discrete log).  Hence, we need to device a 
different method to enable the proof. 

\ignore{  %i'm removing the options with the keys.
  We propose two  methods to achieve this goal.
  In the first solution we modify the Permute and Encrypt step.
  The Preparer uses two different keys, one to encrypt the 
  $a_i$'s and the second for the $b_i$'s. Thus, in Step~3 instead
  of proving that it decrypted the correct value it simply sends to the 
  Chooser the secret key for decrypting the $b_i$'s. The Chooser can then 
  check for itself that the ciphertext $f$ was decrypted correctly.%
  \footnote{Notice that for this we have to assume that the encryption
  scheme is {\em committing}. Namely, we use the fact that the value
  $\enc_{pk}(b)$ is a commitment to $b$ and cannot be opened as an
  encryption of anything else.  }  This last idea, however, has a
  drawback in terms of key-generation, since we must now generate a new
  public/secret key-pair for encrypting the $b_i$'s in every instance of
  the protocol.  
}

The proof will go as follows: for each $i\in [n]$, the Preparer sends 
the element $b_{\pi(i)}$ and corresponding random string that was used 
to obtain ciphertexts $d_i$ in the first step.
The Chooser can then check that the element $d_{\ell}$ that it chose
in Step~2 was encrypted correctly, and learn the corresponding
plaintext.

Clearly, in this protocol the Chooser gets more information than just
the decryption of $f$ (specifically, it gets the decryption of all the
$d_i$'s).  However, this does not effect the security of the protocol,
since the Chooser still does not know anything about the output of the
Preparer, other than what is implied by its output $b$.  In particular,
notice that if $b$ appears more than once in the list, then the
Chooser does not know which of these occurrences was encrypted by
$d_{\ell}$.

Next, we observe that there is no need anymore for the Chooser to 
send $f$ to the Preparer; 
% as $P$'s actions are independent of $f$; 
it is sufficient if $C$ sends only $e$ in Step~2, since it can 
compute the decryption of $d_{\ell}$ by itself.


%----------------------------------------------------------
\paragraph{A weaker condition in the second proof-of-knowledge.}
Finally, we observe that since the security of the Chooser relies on an
information-theoretic argument, the second proof-of-knowledge (in
which the Chooser proves that it knows the index $\ell$) does not have
to be fully zero-knowledge.  In fact, tracing through the proof of
security, one can verify that it is sufficient for this proof to be
{\em witness hiding} in the sense of Feige and Shamir~\cite{fs90}. 
\snote{Is this true? I left this in, since I am reasonably convinced 
that it is true. We still need to check it carefully, however.}  
The resulting protocol is described in \figref{modif}.

\begin{figure}[t]
\begin{center}
{\sf\large Protocol \crsl{2}}

\smallskip
\fbox{\begin{minipage}{4in}
\begin{tabbing}
123\=123456\=123\=123\=123\=123\=123\=123\=123\=123\=123\=123\=\kill
{\it Common inputs}: List of pairs $\pairs{a}{b}$, public key $\pk$. \\
{\it Preparer knows}: secret key $\sk$. \\
\\
\> $P:$\> {\bf 1. Permute and Encrypt}.\\
\>\> Pick a random permutation $\pi$ over $[n]$, and random strings 
     $\pairs{r}{s}$. \\ 
\>\> Let $(c_i, d_i) = (\enc_{\pk}(a_{\pi(i)}; r_{\pi(i)}),
                        ~\enc_{\pk}(b_{\pi(i)}; s_{\pi(i)}))$, 
     for all $i\in [n]$.\\
\>\> Send $\pairs{c}{d}$ to $C$. \\
\\
\>\> \underline{\bf Sub-protocol $\Pi_1$}: 
     $P$ proves in \zk\ that it knows the randomness\\
\>\> $\pairs{r}{s}$ and permutation $\pi$ that were used to obtain 
     the list $\pairs{c}{d}$.\\
\\
\> $C:$ \> {\bf 2. Choose and Blind}.\\
\>\> Pick a random index $\ell \in [n]$.\\
\>\> Send to $P$ the ciphertext $e = \blind_{\pk}(c_{\ell},0)$.\\
\\
\>\> \underline{\bf Sub-protocol $\Pi_2$}: 
     $C$ proves in a witness-hiding manner that it knows \\
\>\> the randomness and index $\ell$ that were used to obtain $e$.\\
\\
\> $P:$ \> {\bf 3. Decrypt and Output}.\\
\>\> Set $a=\dec_{\sk}(e)$. Output $a$.\\
\>\> Send to $C$ the list of pairs $\{(b_{\pi(i)}, s_{\pi(i)})\}_{i=1}^n$
     (in this order).\\
\\
\> $C:$ \> {\bf 4. Verify and Output}.\\ 
\>\> Denote by $(b,s)$ the $\ell$'th entry in this lists 
     (i.e., $(b,s)  = (b_{\pi(\ell)}, s_{\pi(\ell)})$ ).\\
\>\> If $d_{\ell} = \enc_{\pk}(b; s)$ then output $b$.\\
\end{tabbing}
\end{minipage}
}
\caption{Protocol for {\corsel}.}\label{fig:modif}
\end{center}
\end{figure}

\paragraph{Remark. } Notice that for the modified protocol we did not 
use the full power of blindable encryption, since we only used
``blindings'' by zero.  Namely, all that was used in these protocols
is that we can transform any ciphertext $c$ into a {\em random}
encryption of the same plaintext.  (The {\zk} proofs below also 
use only ``blindings'' by zero.)  This is exactly the ``random 
self-reducibility'' property used by Sander et al.~\cite{syy99}. 
%Although it is conceivable that some natural encryption scheme is 
%only ``random self-reducible'' but not fully blindable, we do not 
%know of any such scheme.

\subsection{The Zero-Knowledge Proofs} \label{sec:zkp}
%==========================================================
In this section we provide efficient implementations for the 
sub-protocols $\Pi_1$ and $\Pi_2$. Recall that in $\Pi_1$, the 
Preparer needs to prove that the list of ciphertexts $\pairs{c}{d}$ 
is a permuted encryption of the known list $\pairs{a}{b}$,\ \ and 
in $\Pi_2$ the Chooser needs to prove that the ciphertext $e$ was 
obtained as blinding-with-zero of one of the ciphertexts $c_i$. 

Both protocols $\Pi_1$ and $\Pi_2$ are derived from a simple {\zk} 
proof for a problem which we call {\elc}. \label{sec:elc}
In this problem, which was studies in the context of mix-networks, 
a prover $P$ wants to prove in {\zk} that two lists of ciphertexts, 
$\nlist{x}$ and $\nlist{y}$, are permuted encryptions of the same 
list.  More precisely, $P$ wants to prove that one list was obtained 
by blinding-with-zero and permuting the other, and that he knows a 
permutation $\pi$ and random coins $\nlist{r}$ such that $y_i = 
\blind_{pk}(x_{\pi(i)},0;r_i)$, for all $i\in[n]$.%
\footnote{
We remark that a similar proof can be shown even when the two lists 
were not generated as blindings of each other, and even if the two 
lists were obtained using two different blindable encryption schemes.} 
An efficient {\zk} proof for this problem was described by Abe \cite{abe}. 
(Although Abe's proof assumes ElGamal encryptions, it is easy to see 
that any blindable encryption will do.) For self-containment, we describe 
this proof in Figure~\ref{fig:elc}. 
The protocol in Figure~\ref{fig:elc} achieves knowledge-error of 1/2. 
There are known transformations that can be used to derive a constant-round, 
negligible-error protocol from a three-round, constant-error one. 
(Specifically, we can get a 5-round, negligible-error \zk\ 
proof-of-knowledge for \elc.)  We discuss this issue further in 
Appendix~\ref{sec:negl}.

\iffalse 
  The protocol in Figure~\ref{fig:elc} is a simple %``Graph-Isomorphism-like'' 
  zero-knowledge proof-of-knowledge for the {\elc}. 
  The prover prepares another blinded permutation of the original 
  list, $\nlist{z}$, by blinding-with-zero and re-permuting the list 
  $\nlist{y}$. It then sends this list to the verifier, who asks to 
  see either the correspondence between $\nlist{z}$ and $\nlist{y}$ or 
  the correspondence between $\nlist{z}$ and $\nlist{x}$.%
  \footnote{We remark that this is where we use the ``combining''
  algorithm of the encryption scheme, so the prover would be able to
  show the coins of either the blinding of the $\nlist{x}$ or the
  blinding of $\nlist{y}$.}
\fi 

\begin{figure}
\begin{center}
{\sf Protocol ELC}

\smallskip
\fbox{\begin{minipage}{4.0in}
\begin{tabbing}
123\=123456\=123\=123\=123\=123\=123\=123\=123\=123\=123\=123\=\kill
{\it Common inputs}: $\nset{x}$, $\nset{y}$ (and $pk$).\\
{\it $P$ knows}: $\pi$, $\nset{r}$ s.t. 
$y_i=\blind_{\pk}(x_{\pi(i)}, 0;~r_i)$, for all $i\in [n]$. \\ \\
\> $P:$\> Choose a random permutation $\rho$ over $[n]$, 
          and $n$ random strings $\nset{s}$.\\ 
\>\> Set $t_i = \comb(r_{\rho(i)},~s_i)$ \\
\>\> Set $z_i = \blind_{\pk}(y_{\rho(i)},0;~s_i)\ \  
     \left(= \blind_{\pk}(x_{(\pi\circ\rho)(i)}, 0;~t_i) \right)$.\\ 
\>\> Send to $C$ $\nset{z}$.\\ 
\\
\> $C:$\> Choose $\sigma\in_R \bit{}$ and send it to $P$\\ 
\\
\> $P:$ \> If $\sigma=0$, reply with ($\rho$, $\nset{s}$), 
           else reply with ($\pi\circ\rho$, $\nset{t}$).\\ 
\\
\> $C:$ \> If $\sigma=0$, check $z_i =\blind_{\pk}(y_{\rho(i)},0 ;~s_i)$.\\
\>\> If $\sigma=1$, check $z_i = \blind_{\pk}(x_{(\pi\circ\rho)(i)},0;~t_i)$.
\end{tabbing}
\end{minipage}
}
\caption{A zero-knowledge proof-of-knowledge for {\elc}.}\label{fig:elc}
\end{center}
\end{figure}


\subsubsection{The protocol $\Pi_1$} 
%====================================================
In sub-protocol $\Pi_1$, The Preparer needs to prove that the list of
ciphertexts $\pairs{c}{d}$ is a permuted encryption of the known list
$\pairs{a}{b}$.  This can be done by having the prover encrypt the
list $\pairs{a}{b}$ in some ``canonical'' manner (say, using the
all-zero random string) to generate a ciphertext list $\pairs{g}{h}$,
and then prove using the {\sf ELC} protocol that the two lists
$\pairs{c}{d}$ and $\pairs{g}{h}$ are encryptions of the same list.
The only problem here is that the original list of ciphertexts
$\pairs{c}{d}$ was not obtained by blinding the list $\pairs{g}{h}$,
but rather by directly encrypting the plaintext list $\pairs{a}{b}$.
Hence, to use this protocol we slightly change the protocol \crsl{2}
itself, and have the Preparer encrypt the plaintext list by first
encrypting it in a ``canonical'' manner to get $\pairs{g}{h}$, and
then blind with zero and permute the latter list to get
$\pairs{c}{d}$.  We stress that due to \eqref{2} (from the definition
of blindable encryption), this change in the protocol does not change
the distribution of the ciphertext list $\pairs{c}{d}$.

\subsubsection{The protocol $\Pi_2$}
%=====================================================
At first glance, the problem in Protocol $\Pi_2$ seems substantially
different than the {\elc} problem.  Furthermore, constructing a simple
protocol that ``the ciphertext $e$ was obtained as blinding of some
ciphertext $c_{\ell}$'' (without revealing $\ell$) seems rather hard.
Nonetheless, %in spite of the distance between the problems
we can pose the problem of protocol $\Pi_2$ as an
instance of the {\elc}.  To this end, we again slightly modify the
protocol \crsl{2}, by having the Chooser blind with zero and re-permute 
the entire list (rather than just pick and blind one ciphertext), and 
then prove in {\zk} that it knows the corresponding permutation.
Specifically, the Chooser selects a random permutation $\rho$ over
$[n]$, permutes the entire list of $c_i$'s according to $\rho$, and
then blinds with zero each of the ciphertexts.  The entire new list
(denoted $\nset{e}$) is then sent to the Preparer.  The preparer only 
uses a single, agreed upon, ciphertext from the list (say, $e_1$),  
in the rest of the protocol, but it uses the whole list to verify 
the proof.  (Therefore, the effective index that is chosen by Chooser 
is $\ell=\rho^{-1}(1)$.)  
To prove that it chose the list of $e_i$'s according to the prescribed 
protocol, the Chooser now proves that it knows the permutation $\rho$, 
which is exactly what is done in the {\sf ELC} protocol.

%----------------------------------------------------------------
\paragraph{Two optimizations.}
Since we only use the ciphertext $e_1$ in the \crsl{2} protocol (and 
``we don't really care'' whether the other $e_i$'s are obtained 
properly), we can somewhat simplify and optimize the proof in $\Pi_2$, 
as follows: The Chooser can send only $e_1$ (just as it is done in 
the protocol \crsl{2}). Then, in the zero-knowledge proof, he prepares 
the full set of encryptions $z_1,...z_n$ (as if he actually prepared 
and sent all the $e_i$'s).  Then, depending on the query bit, he 
either reveals the correspondence between the $c_i$'s and all the 
$z_i$'s, or the correspondence between $e_1$ and one of the $z_i$'s. 

Another optimization takes advantage of the fact that in the context
of the \crsl{2} protocol, we only need this proof to be witness
hiding, rather than fully {\zk}. It is therefore possible to just
repeat the protocol from \figref{elc} many times in parallel to get a
negligible error (and we do not need to worry about adding extra flows
of commitment). 

\subsection{Key Generation Issues} \label{sec:keygen}
%==========================================================
In the protocols above we assumed that the encryption keys were
chosen in an appropriate way ahead of time (say, by a trusted party).
If we want to include the key generation as part of the protocols
themselves (i.e., have the Preparer choose them and send the public
keys to the Chooser in Step~1), we must ensure that the Preparer
doesn't choose ``bad keys''.

A generic way to solve this problem is to have the Preparer prove in
zero knowledge that it followed the key generation algorithm. We note,
however, that for our application this is an overkill.  Indeed, the
security of the Chooser does not depend on the ``hiding'' properties
of the encryption scheme.  What the Chooser needs to verify is that
this is a committing encryption (so that the Preparer cannot ``open''
the list of $d_j$'s in more than one way), and that the output of the
blinding operation is independent of which ciphertext of a given
message was used as an input (i.e., that for all $m$ and $c_1, c_2 \in
\enc_{\pk}(m)$, it holds that $\blind_{\pk}(c_1,0) \equiv \blind_{\pk}
(c_2,0)$).

If we use ElGamal encryption to implement the blindable encryption,
then checking these conditions is easy (assuming that the
factorization of $p-1$ is known, where $p$ is the modulus used for the
encryption).  For the Goldwasser-Micali encryption, the first property
requires proving that a given element $y$ ($y=-1$ in the case of a Blum 
integer $N$) is a quadratic non-residue mod $N$ (which can be done quite 
efficiently \cite{gmr}), while the second property is automatically 
satisfied. 
%\snote{We need to check this.}\ynote{Agree. Also, that we don't have 
%to show $n$ is a product of two primes.}
%%SHAI: I verified this. If we know that c,c' are ``real ciphertexts'' 
%% (i.e., either squares or squares-time-$y$) then the blinding works, 
%% regardless of what $N$ is. 

\snote{Notice that we do not really need the Preparer to encrypt the 
$b_i$'s. We just need it to commit to them. But to do the {\zk} proof, 
we need this commitment to be blindable, so it could show that ``two 
commitments are for the same thing'' without opening them. If we have 
such blindable commitments (and we can build those based on either DL 
or factoring), then we can have the Chooser pick the public key for the 
commitment, and we basically don't need any proof for it (for example, 
I believe that we can use my commitment scheme from Crypto'95).
%On a practical level, I don't think that we should include this observation 
%in the submission version. It is already too crowded with observations 
%as it is.
}

\subsection{Putting It All Together} \label{sec:all}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We now finally described all the components of our solution. Let us 
quickly re-cap everything and consider the efficiency of the protocol. 
\begin{enumerate}
\item[0.] 
Initially, the Preparer chooses the keys for the blindable encryption 
scheme, sends the public key to the Chooser and proves in {\zk} that 
the encryption is committing and has the blinding property. As we 
said above, this proof must be tailored to the particular encryption 
scheme that is used.  Also, this step can be carried out only once, 
and the resulting keys can be used for many instances of the protocol. 
%% Yevgeniy
(Alternatively, we can use a trusted third party for this step.)

\item[1.]  The Preparer encrypts the known list $\pairs{a}{b}$ in some
``canonical'' manner, blinds with zero the list of ciphertexts, and
permutes it with a random permutation $\pi$.  It sends the resulting
lists $\pairs{c}{d}$ to the Chooser, and uses the {\sf ELC} protocol
to prove in {\zk} that it knows the permutation that was used.

\item[2.]  The Chooser blinds with zeros the list of $c_i$'s, and
re-permutes it with a random permutation $\rho$.  It sends the
resulting list $\nset{e}$ to the Prover, and again uses the {\sf ELC}
protocol to prove that it knows the permutation that was used. Here 
we can optimize the proof somewhat, since we later only use $e_1$, 
and also because the proof only needs to be witness hiding.

\item[3.]  The Preparer decrypts the first ciphertext $e_1$, and
outputs the corresponding plaintext $a$.

It also sends to the Chooser the list of the $b_i$'s, permuted
according to $\pi$, together with the randomness that was used to
blind their ``canonical encryption'' to get the $d_i$'s in Step~1.

\item[4.]  The Chooser $C$ sets $\ell = \rho^{-1}(1)$, and lets $b,s$ 
denote the $\ell$'th element and randomness, respectively, in the 
last list that it got from the Preparer. He checks that blinding with 
zero (and randomness $s$) of the ``canonical encryption'' of $b$ 
indeed yields the ciphertext $d_{\ell}$.  If this is correct, $C$ 
outputs $b$.
\end{enumerate}

Although we can no longer use the general theorems about secure 
two-party protocols, the security proof is nonetheless quite standard. 
Specifically, we can prove: 

\begin{theorem}\label{thm:modif}
Protocol~{\crsl{2}} securely computes the (randomized) function of the 
{\corsel} problem. 
\end{theorem}

\noindent{\em Proof omitted.}

\paragraph{Efficiency.} We note that all the protocols that are involved 
are quite simple.  In terms of number of communication flows, the key 
generation step (Step~0 above) takes at most five flows, Step~1 takes 
five flows, Step~2 takes three flows and Step~3 consists of just one 
flow.  Moreover, these flows can be piggybacked on each other.  
Hence, we can implement the 
protocol with only five flows of communication, which is equal
to the five steps which are required by a single proof. 
In terms of number of operations, the complexity of the protocol is 
dominated by the complexity of the proofs in Steps~1 and~2. The proof 
in Steps~1 requires $nk$ blinding operations (for a list of size $n$ 
and security parameter $k$), and the proof of Step~2 can be optimized 
to about $nk/2$ blinding operations on the average.  Hence, the whole 
protocol has about $\frac32 nk$ blinding operations.%
\footnote{We note that the protocol includes just a single decryption 
operation, in Step~3. In schemes where 
encryption is much more efficient 
than decryption -- such as the Goldwasser-Micali encryption -- this may 
have a significant impact on the performance of the protocol.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Epilogue: Cryptography and Game Theory} \label{sec:conc}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse 
  \snote{We need to re-write this section.}
  We introduced and solved the {\corsel} problem (and in the process also 
  the {\elc} problem). We described an application to game theory, where 
  we can use this protocol to reduce a Correlated equilibria to Nash 
  equilibria in two-party games. 
  We also identified blindable encryption as a useful tool for designing 
  protocols, and showed how to use it for 1-out-of-$n$ oblivious 
  transfer. 
\fi

An interesting aspect of our work is the relation between the cryptographic 
solutions and the game-theory setting.  Notice that by implementing 
our cryptographic solution in the game-theory setting, we gain on the 
game-theory front (by eliminating the need for a mediator), but we 
also gain on the cryptography front (for example, in that we eliminate 
the problem of early stopping). 
In principle, it may be possible to make stronger use of the game 
theory setting to achieve improved solutions. For example, maybe it 
is possible to prove that in the context of certain games, a player 
does not have an incentive to deviate from its protocol, and so in 
this context there is no point in asking this player to prove that it 
behaves honestly (so we can eliminate some {\zk} proofs that would 
otherwise be required). 

More generally, it may be the case that working in a model in which 
``we know what the players are up to'' can simplify the design of 
secure protocols. It is a very interesting open problem to find 
interesting examples that would demonstrate such phenomena. 


%\bibliographystyle{abbrv}
%\bibliography{crypto,mybibs}
\begin{thebibliography}{10}


\bibitem{abe}
M.~Abe.
\newblock Universally Verifiable Mix-net with Verification Work
Independent on the number of Mix-centers.
\newblock In {\em Proceedings of EUROCRYPT '98}, pp. 437-447, 
1998.

\bibitem{aumann}
R.~Aumann.
\newblock Subjectivity and Correlation in Randomized Strategies.
\newblock In {\em Journal of Mathematical Economics}, 1, pp. 67-95, 
1974

\bibitem{barany92}
I.~Barany.
\newblock Fair distribution protocols or how the players replace fortune.
\newblock {\em Mathematics of Operations Research}, 17(2):327--340, May 1992.

\bibitem{bin97}
M.~Bellare, R.~Impagliazzo, and M.~Naor.
\newblock Does parallel repetition lower the error in computationally sound
  protocols?
\newblock In {\em 38th Annual Symposium on Foundations of Computer Science},
  pages 374--383. IEEE, 1997.

\bibitem{benaloh} 
J.~Benaloh.
\newblock Dense Probabilistic Encryption.  
\newblock In {\em Proc. of the Workshop on Selected Areas in 
Cryptography}, pp. 120-128, 1994.

\bibitem{bgw88}
M.~Ben-Or, S.~Goldwasser, and A.~Wigderson.
\newblock Completeness theorems for non-cryptographic fault-tolerant
  distributed computation.
\newblock In {\em Proceedings of the 20th Annual {ACM} Symposium on Theory of
  Computing}, pages 1--10, 1988.

\bibitem{blum81}
M.~Blum.
\newblock Coin flipping by telephone: A protocol for solving impossible
  problems.
\newblock In {\em Advances in Cryptology -- CRYPTO '81}. {ECE} Report 82-04,
  {ECE} Dept., UCSB, 1982.

\bibitem{bcc88}
G.~Brassard, D.~Chaum, and C.~Cr\'{e}peau.
\newblock Minimum disclosure proofs of knowledge.
\newblock {\em JCSS}, 37(2):156--189, 1988.

\bibitem{chaum82}
D.~Chaum.
\newblock Blind signatures for untraceable payment.
\newblock In {\em Advances in Cryptology -- CRYPTO '82}, pages 199--203. Plenum
  Press, 1982.

\bibitem{ChvA}
D.~Chaum and H.~Van Antwerpen.
\newblock Undeniable signatures.
\newblock In G.~Brassard, editor, {\em Advances in Cryptology --- Crypto'89},
  pages 212--217, Berlin, 1989. Springer-Verlag.
\newblock Lecture Notes in Computer Science No. 435. 

\bibitem{ccd88}
D.~Chaum, C.~Cr\'{e}peau, and E.~Damg{\aa}rd.
\newblock Multiparty unconditionally secure protocols.
\newblock In {\em Advances in Cryptology -- CRYPTO '87}, volume 293 of {\em
 99 Lecture Notes in Computer Science}, pages 462--462. Springer-Verlag, 1988.

\bibitem{ChPe93}
D.~Chaum and T.~Pedersen.
\newblock Wallet databases with observers.
\newblock In E.~Brickell, editor, {\em Advances in Cryptology --- Crypto'92},
  pages 89--105, Berlin, 1992. Springer-Verlag.
\newblock Lecture Notes in Computer Science No. 740.  

\bibitem{cdm2000}
R.~Cramer, I.~Damgard, and P.~MacKenzie.
\newblock Efficient zero-knowledge proofs of knowledge without intractability
  assumptions.
\newblock To appear in {\em 2000 International Workshop on Practice and
  Theory in Public Key Cryptography}, January 2000, Melbourne, Australia. 

\bibitem{CrKi88a}
C.~Cr\'{e}peau and J.~Kilian.
\newblock Weakening security assumptions and oblivious transfer.
\newblock In {\em Advances in Cryptology -- CRYPTO '88}, volume 403 of {\em
  Lecture Notes in Computer Science}, pages 2--7. Springer-Verlag, 1990.

\bibitem{dns98}
C.~Dwork, M.~Naor, and A.~Sahai.
\newblock Concurrent zero knowledge.
\newblock In {\em Proceedings of the 30th Annual {ACM} Symposium on Theory of
  Computing}, pages 409--418. {ACM} Press, 1998.

\bibitem{elgamal84}
T.~ElGamal.
\newblock A public key cryptosystem and a signature scheme based on discrete
  logarithms.
\newblock In {\em Advances in Cryptology -- CRYPTO '84}, volume 196 of {\em
  Lecture Notes in Computer Science}, pages 10--18. Springer-Verlag, 1985.

\bibitem{fs90}
U.~Feige and A.~Shamir.
\newblock Witness indistinguishable and witness hiding protocols.
\newblock In {\em Proceedings of the 22nd Annual {ACM} Symposium on Theory of
  Computing}, pages 416--426. ACM Press, 1990.

\bibitem{book1}
D.~Fudenberg, J.~Tirole.
\newblock Game Theory.
\newblock MIT Press, 1992.

\bibitem{ggjr97}
J.~Garay, R.~Gennaro, C.~Jutla, and T.~Rabin.
\newblock Secure distributed storage and retrieval.
\newblock In {\em Proc. 11th International Workshop on Distributed Algorithms
  (WDAG '97)}, volume 1320 of {\em Lecture Notes in Computer Science}, pages
  275--289. Springer-Verlag, 1997.

\bibitem{gmw86}
O.~Goldreich, S.~Micali, and A.~Wigderson.
\newblock Proofs that yield nothing but their validity and a methodology of
  cryptographic protocol design.
\newblock In {\em 27th Annual Symposium on Foundations of Computer Science},
  pages 174--187. IEEE, 1986.

\bibitem{gmw87}
O.~Goldreich, S.~Micali, and A.~Wigderson.
\newblock How to play any mental game.
\newblock In {\em Proceedings of the 19th Annual {ACM} Symposium on Theory of
  Computing}, pages 218--229, 1987.

\bibitem{GoMi84}
S.~Goldwasser and S.~Micali.
\newblock Probabilistic encryption.
\newblock {\em Journal of Computer and System Sciences}, 28(2):270--299, April
  1984.

\bibitem{gmr}
S.~Goldwasser, S.~Micali, and C.~Rackoff.
\newblock The knowledge complexity of interactive proof systems.
\newblock {\em SIAM Journal on Computing}, 18(1):186--208, 1989.

\bibitem{jakobsson98}
M.~Jakobsson.
\newblock A Practical Mix.
\newblock In {\em Proceedings of EUROCRYPT '98}, pp. 448--461, 
1998.

\bibitem{ls94}
E.~Lehrer and S.~Sorin.
\newblock One-shot public mediated talk.
\newblock Discussion Paper 1108, Northwestern Univeristy, 1994.

\bibitem{kilian}
J.~Kilian.
\newblock Founding Cryptography on Oblivious Transfer.
\newblock In {\em Proc. of STOC}, pp. 20--31, 1988.

\bibitem{mac98}
P.~MacKenzie. 
\newblock Efficient ZK Proofs of Knowledge. 
\newblock Unpublished manuscript, 1998.

\bibitem{NaPi99b}
M.~Naor and B.~Pinkas.
\newblock Oblivious transfer with adaptive queries.
\newblock In {\em Advances in Cryptology -- CRYPTO '99}, volume 1666 of {\em
  Lecture Notes in Computer Science}, pages 573--590. Springer-Verlag, 1999.

\bibitem{nash51}
J.F. Nash.
\newblock Non-Cooperative Games.
\newblock {\em Annals of Mathematics,} 54 pages 286--295.

\bibitem{book2}
M.~Osborne, A.~Rubinstein.
\newblock A Course in Game Theory.
\newblock The MIT Press, 1994.

\bibitem{syy99}
T.~Sander, A.~Young, and M.~Yung.
\newblock Non-interactive {CryptoComputing} for {NC1}.
\newblock In {\em 40th Annual Symposium on Foundations of Computer Science},
  pages 554--567. IEEE, 1999.

\bibitem{yao82b}
A.~C. Yao.
\newblock Protocols for secure computations (extended abstract).
\newblock In {\em 23rd Annual Symposium on Foundations of Computer Science},
  pages 160--164. IEEE, Nov. 1982.

\end{thebibliography}


\appendix

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Implementation of Blindable Encryption} \label{sec:encr}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
As we said above, possible implementations of blindable encryption 
include ElGamal encryption and the Goldwasser-Micali encryption 
scheme.  Below we briefly describe these scheme. 
%as well as another 
%encryption scheme due to Benaloh. 

\subsection{ElGamal Encryption}
%===============================================================
The generation algorithm picks a random $k$-bit prime $p=2q+1$, where
$q$ is prime and a generator $g$ for the subgroup $Q$ of quadratic
residues modulo $p$. Then it picks a random $x\in \Z_q$ and sets
$h=g^x$. The secret key is $x$, the public key is $h$ (and $p$).

To encrypt a message $m\in Q$, one picks a random $r\in \Z_q$ and sets
$E(m) = \brak{g^r, h^r \cdot m}$. The decryption $D(s,t)$ outputs
$t/s^x$. The encryption scheme is well known to be semantically 
secure under the decisional Diffie-Hellman assumption (DDH). To blind 
a ciphertext $\brak{s,t}$ with blinding factor $m'$, we compute 
$\blind(\brak{s,t},m') = \brak{s\cdot g^{r'}, t\cdot h^{r'} \cdot m'}$, 
where $r'$ is chosen at random from $\Z_q$. We note that indeed 
if $s=g^r$, $t=h^r\cdot m$ (for some unknown $r$ and $m$), then 
$\blind(\brak{s,t},m')=\brak{g^{r+r'}, h^{r+r'}\cdot (mm')}$, which is
a random encryption of $mm'$ since $(r+r'\bmod q)$ is random when $r'$
is. The $\comb(r_1,r_2)$ operation is just $(r_1+r_2 \bmod q)$.

Checking that the public key $(p,q,g)$ is ``kosher'' can be done 
by verifying that $p,q$ are primes, $p = 2q+1$, and $g$ is an 
element of order $q$.  Thus, no interaction is needed in the key 
generation phase. Proving that a ciphertext $\brak{s,t}$ is an 
encryption of a message $m$ requires proving equality of the 
discrete-log of two known elements with respect to two known bases, 
which can be done using several known simple protocols \cite{ChvA,ChPe93}.
\snote{We should put some ref here.}

\subsection{Goldwasser-Micali Encryption}
%===============================================================
This is the original semantically secure scheme introduced by
Goldwasser and Micali~\cite{GoMi84}. The message is encrypted bit by
bit. The generation algorithm picks a random $n=pq$, a product of two
$k$-bit primes together with any quadratic non-residue $y$ with Jacobi
symbol $1$ (in case $n$ is a Blum integer, i.e. $p\equiv q\equiv 3
\bmod 4$, one can fix $y\equiv -1$). The public key is $n$ and $y$,
and the secret key is $p$ and $q$.

To encrypt a bit $b\in \bit{}$, one picks a random $r\in \Z_n^*$ and
returns $(y^b \cdot r^2 \bmod n)$ (i.e. a random square for $b=0$ and
a random non-square for $b=1$). To decrypt one simply determines if
the ciphertext $c$ is a square modulo $n$, i.e. modulo both $p$ and
$q$. The scheme is semantically secure under the quadratic residue
assumption. The scheme is clearly blindable, since if $c = \enc(b; r)$ 
and $c' = \enc(b'; r')$, then $c \cdot c' = \enc(b+b'; r\cdot r')$ 
(where the addition $b+b'$ is done modulo 2, and all the other operations 
are done modulo $n$). 

Proving that a public key $n,y$ is committing requires proving that 
$y$ is a quadratic-non-residue mode $n$, which can be done efficiently. 
Proving that $c$ is an encryption of $b$ can be done by proving 
quadratic residuacity. 


\ignore{
  \subsection{Benaloh Encryption}
  %===============================================================
  \snote{Why do we talk about this system?}\ynote{I thought it is a cool
  example: simple and elegant.}

  The scheme encrypts messages $m\in \Z_t$, where $t$ is some odd number
  which is not too large and is fixed by the system. The generation
  algorithm picks a random $n=pq$, where $p$ and $q$ are two $k$-bit
  primes such that $t$ divides $(p-1)$, but is relatively prime to both
  $(p-1)/t$ and $(q-1)$. The algorithm also selects some $y\in \Z_n^*$
  such that $z\eqdef y^{\phi(n)/t}$ has order $t$.
  \iffalse
  \footnote{Benaloh claims it suffices to ensure that $z\neq 1$, but I
  do not think this is correct. Think of $p=19$, $q=5$, $t=9$, $g$ be
  the elements of $\Z_{95}$ of order $36$. Set $y=g^3$. Then $y^{72/9} =
  y^8 = g^{24} \neq 1$, while uniqueness of decryption is no longer
  guaranteed. Am I right?}  \fi

  To encrypt $m\in \Z_t$, select random $u\in \Z_n^*$ and return $c=y^m
  u^t\bmod n$. The encryption is unique since $y^{m_1} u_1^t \equiv
  y^{m_2} u_2^t$ implies that $y^{m_1-m_2} = u^t$ for $u=u_2 u_1^{-1}$.
  Raising this to the power $\phi(n)/t$ and noticing that
  $u^{\phi(n)}\equiv 1$, we get that $z^{m_1-m_2}\equiv 1$, which
  implies that $(m_1\equiv m_2\bmod t)$ (because $z$ has order $t$).

  To decrypt, we precompute $z^m\bmod n$ for all $m\in \Z_t$ (that is
  why we want $t$ to be small). Then, given ciphertext $c$ we compute
  $c^{\phi(n)/t}$ (which is equal to $z^m$) and find a corresponding
  unique $m$ from our look-up table. The scheme is known to be
  semantically secure under the assumption that deciding higher
  residuosity is hard. In some sense, it is the generalization of the
  Goldwasser/Micali system for $t=2$, except $2$ always divides $q-1$,
  so Goldwasser and Micali had to restrict themselves to elements of
  $\Z_n^*$ with Jacobi symbol $1$. Here this restriction is not needed.

  Again, the system is clearly blindable since $(y^m u^t)(y^{m'} w^t)
  \equiv y^{m+m'} (uw)^t$. 

  \ynote{This has to be rewritten. In particular, key generation should
  be addressed and should refer to protocol in the next section for
  verifiability.}  Also, it is verifiable since we can apply
  Lemma~\ref{lem:verif}. Indeed, given $p,q,y,m$ and $c(=y^m u^t\bmod
  n)$, one can let $a=c/y^m$ and finding $u$ is equivalent to taking
  $t$-th root of $a$. This in turn is equivalent to taking $t$-th root
  of $a$ modulo $p$ and $q$. Modulo $q$ this simply amounts to raising
  $a$ to the power $(t^{-1}\bmod q-1)$ (since $t$ is relatively prime to
  $q-1$). We can also extract some $t$-th root of $a$ modulo $p$ using a
  more sophisticated procedure of Adelman, Manders and Miller. \ynote{I
  think it is correct, even though not sure if the reference is right.}

}  % end ignore benaloh

\subsection{Verifying Decryption in Blindable Encryption Schemes}
%===============================================================
It is often useful when an encryption scheme has an efficient {\zk}
proofs for claims of the form ``$c$ is an encryption of $m$''. 
\snote{(though we do not need this for the protocols in this paper).} 
\ynote{don't we? what about ot?} \snote{As far as I can see, we don't 
need it also for the OT, at least not as long as the receiver can 
check that a given value is a legal ``encryption of something''.} 
Although we do not know how to construct such
efficient protocol based only on the blindable encryption property
(other than using generic constructions), we can show a simple and
efficient proof for the special case where the decryption algorithm
also reveals the random coins that were used in the encryption (as in 
Goldwasser-Micali). The following simple
3-round protocol is such a proof with soundness error of $1/2$.
%Repeating it in parallel with the extra commitment scheme in the 
%beginning will do the job. Let the input be $m$ and $c$, $P$ be 
%the prover, $V$ -- the verifier.

For this protocol, we assume without loss of generality that
\begin{equation}\label{eq:3}
\blind_{\pk}(\enc_{\pk}(m_1 ;~r_1), m_2;~ r_2) = \enc_{\pk}(m_1+m_2 ;~
\comb(r_1,r_2))
\end{equation}
Indeed, let $c_0$ be any fixed encryption of $0$ (the identity of
$M$). We can then redefine the encryption process to be
$\enc_{\pk}(m;r) = \blind_{\pk}(c_0, m; r)$. \eqref{1} from the
definition of blindable encryption shows that $\enc_{\pk}(m ;r)$ is
indeed a random encryption of $m$, while \eqref{2} now immediately
implies \eqref{3}.

\begin{center}
{\sf Protocol for Proving $c \in \enc_{\pk}(m)$} 

\smallskip
\fbox{\begin{minipage}{4.0in}
\begin{tabbing}
123\=1234567890\=123\=123\=123\=123\=123\=123\=123\=123\=123\=123\=\kill
{\it Common inputs}: $m,c,pk$. \\
{\it Prover knows}: $sk$.\\
\\
\> $P:$\> Compute $r$ such that $c=\enc_{\pk}(m,r)$.
Pick random $m'\in M$ and $r'$. \\ 
\>\> Let $c'=\blind_{\pk}(c,m',r')=\blind_{\pk}(\enc_{\pk}(m,r),m',r')$\\
\>\>\>\>\>\>\>\>\> 
   $\left( \equalby{3} \enc_{\pk}(m+m',\comb_{\pk}(r,r'))\right)$.\\ 
%\>\> Find $r'$ such that $c'=\enc_{\pk}(m+m',r')$.\\ 
\> $\PtoV$:\> Send $m', c'$.\\
\> $\VtoP:$\> Choose $\sigma \in_R \bit{}$; Send $\sigma$. \\
\> $\PtoV:$\> If $\sigma=0$, send $r'$, else send $r''= 
\comb_{\pk}(r,r')$.\\
\> $V:$ \> If $\sigma=0$, check $c'=\blind_{\pk}(c,m',r')$, else
check $c'=\enc_{\pk}(m+m', r'')$.
\end{tabbing}
\end{minipage}
}
\end{center}
%Easy to show that this is a \zk\ argument with soundness
%$1/2$.\footnote{Note, $r$ in the claim does not have to be {\em
%random} such that $c=\enc_{\pk}(m,r)$. Ability to find any such $r$
%will suffice since $\comb_{\pk}(r,r')$ is random if $r'$ is random,
%even if $r$ is not.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Blindable Encryption and Oblivious Transfer} \label{sec:ot}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Blindable encryption schemes, which were the main building block 
%in our protocol, seem to be a very convenient primitive to work 
%with. To demonstrate the usefulness of this primitive, we show 
We show below a very simple implementation of {\em 1-out-of-$n$ 
Oblivious Transfer} using blindable encryption. Recall that a 
$1$-out-$n$ Oblivious Transfer Protocol implements the following 
functionality. There are two players, $P$ and $C$,  who have 
some private inputs: $P$ has a set of $n$ strings $X=(\nlist{x})$, 
and $C$ has an index $\ell\in [n]$. At the end of the protocol $C$ 
should learn $x_{\ell}$ and nothing else, while $P$ should learn nothing 
at all. There are other flavors of oblivious transfer, all known to 
be equivalent to the above.

We let $P$ commit to his input $X$ by encrypting each $x_i$, i.e. set
$y_i=\enc_{\pk}(x_i)$ (for all $i\in [n]$) and send $\nlist{y}$ to
$C$.
%This gives $C$ no information since $E$ is semantically secure. 
%Also, $P$ does not need to prove that $y_i\in E(x_i)$, since $x_i$ 
%is the input of $P$ that is unknown to $C$. 
Now we are in the situation that the Chooser wants the Preparer to
decrypt $y_{\ell}$ without telling him $\ell$. A simple solution that
works in the honest-but-curious model, is as follows: $C$ chooses a
random blinding factor $\bt$, sets $z=\blind_{\pk}(y_{\ell},\bt)$,
asks $P$ to decrypt $z$, and subtracts $\bt$ from the result to
recover the correct $x_{\ell}$.  Since $z$ is the encryption of a
random element $x_j+\bt$, $P$ indeed does not learn any information
about $\ell$.  To adjust this protocol to work against malicious
players, $C$ needs to prove that he knows the index $\ell$ and
blinding factor $\bt$.  This is essentially the same problem as in the
sub-protocol $\Pi_2$ in our \crsl{2} protocol, with the only
difference being that now we also have the blinding factor $\bt$.
Accordingly, the protocol for solving it is nearly identical to the
{\sf ELC} protocol, with the only difference being that the prover
blinds the encrypted lists with random elements rather than with zeros
(and shows the blinding factors when he is asked to ``open'' the
blinding.
Due to space limitations, we omit further details.

We note, though, that a small modification of the above protocol
implements {\em random} $1$-out-of-$n$ oblivious transfer, where $C$
should learn $x_{\ell}$ for a random $\ell$. To implement that, $P$
simply chooses a random permutation $\pi$ in the first step and sets
$y_i = \enc_{\pk}(x_{\pi(i)})$.

\snote{Since we didn't have time to check this thing, I suggest that 
we do not talk about the $k$-out-of-$n$ issue, at least for now.}
\iffalse 
  \paragraph{Remark.}
  Intuitively, it seems like the OT protocol from above also generalizes
  to solve $k$-out-of-$n$ oblivious transfer problem. Here $C$ wants to
  obtain $x_{j_1},\ldots, x_{j_k}$ such that $P$ does not learn anything
  about $j_1,\ldots,j_k$, and $C$ does not learn anything more as well.
  Namely, all we need is for $C$ to re-permute the list of ciphertexts
  using a random permutation $\rho$ subject to $\rho(t)=j_t$ for
  $t=1\ldots k$, and for $P$ to decrypt the first $k$ ciphertexts. 
  Although this simple protocol seems to be doing just what we want, in
  trying to prove it one encounters exactly the same kind of problem that
  arises with selective decommitment \snote{Here is our chance to cite
  DDN.} Although it is possible to solve this using non-committing
  encryption (and it is possible to construct non-committing blindable
  encryption as a composition of two schemes, one non-committing and the
  other blindable), the resulting protocol would not be very efficient.
\fi
\ynote{should we put {\em adaptive} $k$-out-of-$n$ here, rather than
oblivious, and relate it to naor/pinkas?}


\snote{Commented out the correlated coins section.}
\iffalse
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{Correlated Coins} \label{sec:coins}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \snote{To be re-written (or maybe not?)}

  We now show a simple 
  application of the above protocol to the problem of {\em coin
  flipping}, where $P$ and $C$ wish to collectively flip a random bit
  $\sigma$ (which is a special case of Correlated Element Selection
  problem with list $\set{(0,0),(1,1)}$).  The problem is very well
  studied and has quite a simple solution using any commitment scheme
  (and hence, any semantically secure encryption).  $P$ commits to a
  bit $\sigma_1$, $C$ sends $\sigma_2$, $P$ opens the commitment, and
  they both output $\sigma=\sigma_1\xor \sigma_2$.  The main reason for
  such a simple solution is the {\em lack of secrecy} requirements in the
  statement of the problem (the parties should only be unable to bias
  the output).

  We consider a slightly more general coin flipping. Here we are given a
  list $\nlist{x}$ (possibly with repetitions) and wish to pick a random
  $x_i$ from the list (known to both players). This corresponds to the
  special case of Correlated element selection where $a_i=b_i=x_i$.
  While this problem is again trivially solvable by standard coin
  flipping (just pick random $i\in [n]$ and output $x_i$), we present a
  much less efficient (but quite natural) solution that will be geared
  towards our general problem.

  The idea is for the Preparer to choose a random $\pi\in S_n$, and send
  the Chooser the permuted encrypted list, i.e. $y_i = E(x_{\pi(i)})$.
  The Chooser then picks a random $j\in [n]$ and asks to decrypt
  $y_j$. The result is the needed $x_i = x_{\pi^{-1}(j)}$. The Preparer
  can cheat twice: incorrectly decrypt $y_j$ and send the wrong
  list. Both problems can be easily solved by $P$ revealing all his
  random bits at the end. However, we take a more complicated approach
  where $P$ proves both of these statements in \zk: correctness of
  decryption using verifiability and correctness of the list he prepared
  by the ``encrypted list correspondence'' protocol. The resulting
  protocol is shown in Figure~\ref{fig:flipping}. While not needed here,
  the extra property of this protocol is that $C$ obtained only $x_i$
  {\em without obtaining the ``actual index'' $i$ $(=\pi^{-1}(j))$}.

  \begin{figure}
  \begin{center}
  \begin{tabular}{|l|}
  \hline
  \begin{minipage}{5.0in}
  \vspace{1ex}
  \begin{tabbing}
  123\=1234567890\=123\=123\=123\=123\=123\=123\=123\=123\=123\=123\=\kill
  {\it Common inputs}: $\nset{x}$ (and $pk$). \\
  \\
  \> $\PtoC:$\> Pick $\pi \in_R S_n$. Let $y_i = \enc_{\pk}(x_{\pi(i)})$. 
  Send $\nset{y}$. \\ \\
  \>\> Run ``encrypted list correspondence''\\
  \>\> protocol on $\nset{x}$ and $\nset{y}$.\\ \\
  \> $\CtoP:$ \> Pick $j \in_R [n]$. Send $j$ to $P$.\\ \\
  \> $\PtoC:$ \> Set $i=\pi^{-1}(j)$, $x=x_i$ $(=\dec_{\sk}(y_j))$. 
  Send and output $x$.\\ \\
  \>\> Run verifiability protocol to prove that $x=\dec_{\sk}(y_j)$.\\ \\
  \> $C:$ \> Output $x$.
  \end{tabbing}
  \caption{\em (Inefficient) Coin Flipping.}\label{fig:flipping}
  \end{minipage}
  \\
  \hline
  \end{tabular}
  \end{center}
  \end{figure}

  \paragraph{Remark.}
  The above protocol can be used to select a random $k$-tuple of $x_i$'s
  (at the cost better than $k$ times the original protocol). The Chooser
  simply chooses $k$ random indices and asks the Preparer to translate
  (with proofs) all of them.
\fi


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Reducing the error in a {\zk} proof-of-knowledge} \label{sec:negl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Below we describe a known transformation from any 3-round, 
constant-error {\zk} proof-of-knowledge into a 5-round, negligible 
error {\zk} proof-of-knowledge, that uses trapdoor commitment 
schemes.  We were not able to trace the origin of this transformation, 
although related ideas and techniques can be found in 
\cite{dns98,mac98,cdm2000}. \snote{add refs for Mac, CDM99.}

Assume that you have some 3-round, constant-error {\zk} 
proof-of-knowledge protocol, and consider the 3-round protocol 
that you get by running the constant-error protocol many times 
in parallel. Denote the first prover message in the resulting 
protocol by $\alpha$, the verifier message by $\beta$, and the 
last prover message by $\gamma$.  Note that since the original protocol 
was 3-round, then parallel repetition reduces the error exponentially 
(see proof in \cite{bin97}). However, this protocol is no longer {\zk}. 

To get a zero-knowledge protocol, we use a trapdoor (or {\em Chameleon}) 
commitment schemes \cite{bcc88}.  Roughly, this is a commitment scheme 
which is computationally binding and unconditionally secret, with the 
extra property that there exists a trapdoor information, knowledge of 
which enables one to open a commitment in any way it wants. 

In the zero-knowledge protocol,  the prover sends to the verifier in 
the first round the public-key of the trapdoor commitment scheme. The 
verifier then commits to $\beta$, the prover sends $\alpha$, the verifier 
opens the commitment to $\beta$, and the prover sends $\gamma$ and also 
{\em the trapdoor for the commitment}.  The {\zk} simulator follows the 
one for the standard 4-round protocol. The knowledge extractor, on the 
other hand, first runs one instance of the proof to get the trapdoor, 
and then it can effectively ignore the commitment in the second round, 
so you can use the extractor of the original 3-round protocol. 
\end{document}




