\documentstyle[11pt]{article}

%% math.tex -- common mathematical macros
%% Ronald L. Rivest
%% 4/8/90

\renewcommand{\hat}[1]{\widehat{#1}}

%% Sequences, etc.
\newcommand{\ang}[1]{\langle#1\rangle}

%% Algebra
\newcommand{\R}{{\bf R}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\N}{{\bf N}}
\newcommand{\Q}{{\bf Q}}
\newcommand{\C}{{\bf C}}

%% Set theory
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\card}[1]{\left| #1\right|}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\bigset}[2]{\left\{\,#1\::\:#2\,\right\}}
\newcommand{\smallset}[1]{\{ #1 \}}

%% Number theory
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\divs}{\mathrel |}
\newcommand{\ndivs}{\mathrel{\not|}}
\newcommand{\lcm}{\mathop{\rm lcm}\nolimits}
\newcommand{\sign}{\mathop{\rm sign}\nolimits}
\newcommand{\Zn}{\Z_n}
\newcommand{\Zp}{\Z_p}
\newcommand{\Zq}{\Z_q}
\newcommand{\dispLegendre}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\Legendre}[2]{\bigl(\frac{#1}{#2}\bigr)}
\newcommand{\ord}{\mathop{\rm ord}\nolimits}
\newcommand{\ind}{\mathop{\rm ind}\nolimits}
%% ``imod'' is an ``in-line mod'' that leaves less space before the parens.
\def\imod#1{\allowbreak \mkern10mu ({\rm mod}\,\,#1)}
%% boldface imod
\def\bimod#1{\allowbreak \mkern10mu (\hbox{mod}\,\,#1)}

%% Probability and statistics; combinatorics
\newcommand{\prob}[1]{\Pr\left\{ #1 \right\}}
\newcommand{\expect}[1]{{\rm E}\left[ #1 \right]}
\newcommand{\expectsq}[1]{{\rm E}^2\left[ #1 \right]}
\newcommand{\variance}[1]{{\rm Var}\left[ #1 \right]}
\renewcommand{\choose}[2]{{{#1}\atopwithdelims(){#2}}}
\def\pmod#1{\allowbreak\mkern12mu({\rm mod}\,\,#1)}

%% Matrix theory
\newcommand{\transpose}{^{\rm T}}
\newcommand{\transposeintext}{{\rm T}}
\newcommand{\matxspace}{\hspace*{.25pc}}
\newcommand{\matx}[2]{\left(\matxspace\begin{array}{*{#1}{c}}#2\end{array}\matxspace\right)}
\newcommand{\rmatx}[2]{\left(\matxspace\begin{array}{*{#1}{r}}#2\end{array}\matxspace\right)}
%\newcommand{\deter}[2]{\left|\matxspace\begin{array}{*{#1}{c}}#2\end{array}\matxspace\right|}
% Redefined by THC to leave \matxspace after left paren and before right paren.
\def\bordermatrix#1{\begingroup \m@th
  \setbox\z@\vbox{\def\cr{\crcr\noalign{\kern2\p@\global\let\cr\endline}}%
    \ialign{$##$\hfil\kern2\p@\kern\p@renwd&\thinspace\hfil$##$\hfil
      &&\quad\hfil$##$\hfil\crcr
      \omit\strut\hfil\crcr\noalign{\kern-\baselineskip}%
      #1\crcr\omit\strut\cr}}%
  \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}%
  \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}%
  \setbox\tw@\hbox{$\kern\wd\@ne\kern-\p@renwd\matxspace\left(\matxspace\kern-\wd\@ne
    \global\setbox\@ne\vbox{\box\@ne\kern2\p@}%
    \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\baselineskip}\,\matxspace\right)$}%
  \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\cofactor}[1]{{\tilde{#1}}}
\newcommand{\eqnline}{\\[.75ex]}
\newcommand{\bigeqnline}{\\[1.75ex]}
\newcommand{\dollar}[1]{\$$#1$}

%% Complexity theory
\renewcommand{\P}{\func{\mbox{}P}}
\newcommand{\eqnP}{\eqnfunc{\mbox{}P}}
\newcommand{\NP}{\func{NP}}
\newcommand{\NPC}{\func{NPC}}
\newcommand{\coNP}{\func{co-NP}}
\newcommand{\comp}[1]{\overline{#1}}
\newcommand{\red}{\leq_{\rm P}}
\newcommand{\emptystring}{\varepsilon}

%% Asymptotic notation
\newcommand{\Omegainf}{\shortstack{{\scriptsize$\infty$}\\[-.5ex]$\Omega$}}

%% Cases for equations
\renewcommand{\cases}[1]{\left\{ \begin{array}{ll}#1\end{array}\right.}
\newcommand{\cif}[1]{\mbox{if $#1$}}
\newcommand{\cwhen}[1]{\mbox{when $#1$}}

%% Page size
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.0in}
\setlength{\oddsidemargin}{0.in}
\setlength{\evensidemargin}{0.in}
\setlength{\textwidth}{6.5in}
\setlength{\parskip}{2pt}

\def\a{\alpha}
\def\b{\beta}
\def\calE{{\cal E}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}
\newcommand{\heading}[1]{\protect\vspace{8pt}\noindent{\sc #1}}
\newcommand{\headingg}[1]{\noindent{\sc #1}}
\newcommand{\smidge}{{\kern .05em}}	
\newcommand{\Colon}{{\smidge\colon\;\:}}
\def\suchthat{\mbox{ : }}
\newcommand{\iset}[2]{\{\:#1 \suchthat #2\:\}}
\def\eq{\: = \:}
\def\leqq{\: \leq \:}
\def\geqq{\: \geq \:}
\newcommand{\sfrac}[2]{{\textstyle \frac{#1}{#2}}}
\newcommand{\ssum}[2]{{\textstyle \sum_{\,#1}^{\,#2}\,}}
\newcommand{\sprod}[2]{{\textstyle \prod_{\,#1}^{\,#2}\,}}

\newcounter{ctr}
\newcounter{savectr}
\newcounter{ectr}
\newlength{\saveparindent}
\setlength{\saveparindent}{\parindent}
\newlength{\saveparskip}
\setlength{\saveparskip}{\parskip}

\newenvironment{newitemize}{%
\begin{list}{$\bullet$}{\labelwidth=9pt%
\labelsep=7pt \leftmargin=16pt \topsep=5pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{5pt} }}{\end{list}}

\newenvironment{newenum}{%
\begin{list}{{\rm (\arabic{ctr})}\hfill}{\usecounter{ctr} \labelwidth=18pt%
\labelsep=7pt \leftmargin=25pt \topsep=3pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{2pt} }}{\end{list}}

\newenvironment{onelist}{%
\begin{list}{{\rm (\arabic{ctr})}\hfill}{\usecounter{ctr} \labelwidth=18pt%
\labelsep=7pt \leftmargin=25pt \topsep=4pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{4pt}}}{\end{list}}

\newenvironment{namelist}[1]{%
\begin{list}{{\rm (#1\arabic{ctr})}\hfill}{\usecounter{ctr} \labelwidth=27pt%
\labelsep=3pt \leftmargin=30pt \topsep=2pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{1pt}}}{\end{list}}

\newenvironment{twolist}{%
\begin{list}{{\rm (\arabic{ctr}.\arabic{ectr})}%
\hfill}{\usecounter{ectr} \labelwidth=26pt%
\labelsep=7pt \leftmargin=33pt \topsep=1pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{1pt} }}{\end{list}}

\newenvironment{tiret}{%
\begin{list}{\hspace{2pt}\rule[0.5ex]{6pt}{1pt}\hfill}{\labelwidth=15pt%
\labelsep=3pt \leftmargin=22pt \topsep=3pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{2pt}}}{\end{list}}


\newenvironment{newmath}{\begin{displaymath}%
\setlength{\abovedisplayskip}{5pt}%
\setlength{\belowdisplayskip}{5pt}%
\setlength{\abovedisplayshortskip}{3pt}%
\setlength{\belowdisplayshortskip}{3pt} }{\end{displaymath}}

\newenvironment{newequation}{\begin{equation}%
\setlength{\abovedisplayskip}{5pt}%
\setlength{\belowdisplayskip}{5pt}%
\setlength{\abovedisplayshortskip}{3pt}%
\setlength{\belowdisplayshortskip}{3pt} }{\end{equation}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{propo}[thm]{Proposition}
\newtheorem{fct}[thm]{Fact}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exmp}[thm]{Example}
\newtheorem{assm}[thm]{Assumption}
\newtheorem{clm}[thm]{Claim}
\newtheorem{techclm}[thm]{Technical Claim}
\newtheorem{rem}[thm]{Remark}

\newenvironment{theorem}{\begin{thm}\begin{rm}}%
{\end{rm}\end{thm}}
\newenvironment{lemma}{\begin{lem}\begin{rm}}%
{\end{rm}\end{lem}}
\newenvironment{corollary}{\begin{cor}\begin{rm}}%
{\end{rm}\end{cor}}
\newenvironment{proposition}{\begin{propo}\begin{rm}}%
{\end{rm}\end{propo}}
\newenvironment{fact}{\begin{fct}\begin{rm}}%
{\end{rm}\end{fct}}
\newenvironment{definition}{\begin{defn}\begin{em}}%
{\end{em}\end{defn}}
\newenvironment{example}{\begin{exmp}\begin{em}}%
{\end{em}\end{exmp}}
\newenvironment{assumption}{\begin{assm}\begin{em}}%
{\end{em}\end{assm}}
\newenvironment{claim}{\begin{clm}\begin{rm}}%
{\end{rm}\end{clm}}
\newenvironment{techclaim}{\begin{techclm}\begin{rm}}%
{\end{rm}\end{techclm}}
\newenvironment{remark}{\begin{rem}\begin{em}}%
{\end{em}\end{rem}}

\newcommand{\secref}[1]{\mbox{Section~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Appendix~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Theorem~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definition~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corollary~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lemma~\ref{#1}}}
\newcommand{\clref}[1]{\mbox{Claim~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposition~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figure~\ref{#1}}}
\newcommand{\eqref}[1]{\mbox{Equation~\ref{#1}}}

% deluxe proof enviroment
\def\qsym{\vrule width0.6ex height1em depth0ex}
\newcount\proofqeded
\newcount\proofended
\def\qed{ {\hspace{5pt}\rule[-1pt]{3pt}{9pt}}
\end{rm}\addtolength{\parskip}{-0pt}
\setlength{\parindent}{\saveparindent}
\global\advance\proofqeded by 1 }
\newenvironment{proof}%
 {\proofstart}%
 {\ifnum\proofqeded=\proofended\qed\fi \global\advance\proofended by 1
  \medskip}
\makeatletter
\def\proofstart{\@ifnextchar[{\@oprf}{\@nprf}}
\def\@oprf[#1]{\begin{rm}\protect\vspace{6pt}\noindent{\bf Proof of #1:\
}%
\addtolength{\parskip}{5pt}\setlength{\parindent}{0pt}}
\def\@nprf{\begin{rm}\protect\vspace{6pt}\noindent{\bf Proof:\ }%
\addtolength{\parskip}{5pt}\setlength{\parindent}{0pt}}
\makeatother

%
% Mihir's macros for title with ``appears in'' at top.
%
% from  /usr/local/lib/tex/inputs/article.sty  and
%       /usr/local/lib/tex/inputs/latex.tex
%
% Usage: Before the \title command use \appearsin{ ...  } to say whatever
% you want. Eg:
%
% \appearsin{This paper is to appear in the Proceedings of Crypto 94}
% \title{How to ** Perfect ** Optimal ** }
% \author{ }
% \date{ }
% \maketitle
% \begin{abstract}
%     The title says it all
% \end{abstract}
% 

\makeatletter

\def\appearsin#1{\gdef\@appearsin{#1}}

\def\maketitle{\par
 \begingroup
 \def\thefootnote{\fnsymbol{footnote}}
 \def\@makefnmark{\hbox 
 to 0pt{$^{\@thefnmark}$\hss}} 
 \if@twocolumn 
 \twocolumn[\@maketitle] 
 \else \newpage
 \global\@topnum\z@ \@maketitle \fi\thispagestyle{plain}\@thanks
 \endgroup
 \setcounter{footnote}{0}
 \let\maketitle\relax
 \let\@maketitle\relax
 \gdef\@thanks{}\gdef\@author{}\gdef\@title{}\gdef\@appearsin{}
          \let\thanks\relax}
\def\@maketitle{\newpage
 \noindent \@appearsin
 \vskip 1in \begin{center}
 {\LARGE \@title \par} \vskip 1.5em {\large \lineskip .5em
\begin{tabular}[t]{c}\@author
 \end{tabular}\par} 
 \vskip 1em {\normalsize \@date} \end{center}
 \par
 \vskip 1.5em} 
\def\abstract{\if@twocolumn
\section*{Abstract}
\else \small 
\begin{center}
{\bf Abstract\vspace{-.5em}\vspace{0pt}} 
\end{center}
\quotation 
\fi}
\def\endabstract{\if@twocolumn\else\endquotation\fi}
\mark{{}{}} 


\begin{document}

\bibliographystyle{plain}

\appearsin{To appear in {\sl Journal of Cryptology.} Preliminary version
appeared as MIT/LCS Technical Report 683, February 1996.}

\title{{\bf Translucent Cryptography --- An Alternative to Key Escrow, and
its Implementation via Fractional Oblivious Transfer}
% \thanks{\ An
% earlier version of this paper, by the second author, was titled
% ``Translucent Cryptography:~An Alternative to Key Escrow,'' and was
% presented at the Rump session of Crypto~95. The current version appears as
% MIT/LCS Technical Report 683, February 1996.}
\protect\vspace{0.2in}}

\author{{\sc Mihir Bellare}\thanks{\ Department of Computer Science \& 
Engineering, Mail Code 0114, University of California, San Diego, 9500 Gilman
Drive La Jolla, CA 92093, USA. E-mail: {\tt
mihir@{\allowbreak}cs.ucsd.{\allowbreak}edu}.  Web page: {\tt
http://{\allowbreak}www-cse.{\allowbreak}ucsd.{\allowbreak}%
edu/{\allowbreak}users/{\allowbreak}mihir}.  Supported in part by a 1996
Packard Foundation Fellowship in Science and Engineering.}
\and
{\sc Ronald L. Rivest}\thanks{\ Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, USA.
E-mail: {\tt rivest@theory.lcs.mit.edu}.  Web page: {\tt
http://{\allowbreak}theory.{\allowbreak}lcs.{\allowbreak}%
mit.edu/{\allowbreak}\~{\mbox{\ }}rivest}.}\\
\protect\vspace{0.2in}
}
\date{October 1997}
\maketitle

\begin{abstract}

We present an alternative to the controversial ``key escrow'' techniques for
enabling law-enforcement and national security access to encrypted
communications.  Our proposal allows such access with probability $p$ for each
message, for a parameter $p$ between $0$ and $1$ to be chosen (say, by
Congress) to provide an appropriate balance between concerns for individual
privacy, on the one hand, and the need for such access by law-enforcement and
national security, on the other.
(For example, with $p=0.4$, a law-enforcement agency conducting an authorized
wiretap which records 100 encrypted conversations would expect to be able to
decrypt (approximately) 40 of these conversations; the agency would not be 
able to decrypt the remaining 60 conversations at all.)
% Different values of $p$ can be chosen for different situations, such
% as for export. 
% Our proposal can be combined with other ideas, such as
% secret-sharing, to provide additional flexibility. 
Our scheme is remarkably simple to implement, as it requires no prior escrowing
of keys.

We implement translucent cryptography based on non-interactive oblivious
transfer. Extending the schemes of Bellare and Micali
\cite{BellareMi90a}, who showed how to transfer a message with probability
$1/2$, we provide schemes for non-interactive fractional oblivious transfer,
which allow a message to be transmitted with any given probability $p$.  Our
protocol is based on the Diffie-Hellman assumption and uses just one El Gamal
encryption (two exponentiations), regardless of the value of the transfer
probability $p$.  This makes the implementation of translucent cryptography
competitive, in efficiency of encryption, with current suggestions for software
key escrow.

\end{abstract}

\noindent {\bf Keywords:} Key escrow, translucent, oblivious transfer,
discrete logarithms, communications policy.

\newpage

\tableofcontents
\newpage

\section{Introduction}

Our nation is in the midst of an important and critical debate on
cryptographic policy.  The current administration seems committed to
the idea that the government should be able to read encrypted
communications to support law-enforcement or national security
objectives, when appropriately authorized.  (See NIST
\cite{NationalInst94c}.)  This position is highly unpopular with many
(most?) citizens and with much of the business community.

The purpose of this paper is not to contribute to the political debate
directly.  (For the record, the views of the second author are strongly
libertarian.)  The reader is referred to Hoffman \cite{Hoffman95a},
Denning \cite{Denning95}, or Micali \cite{Micali92} for some discussion
of the issues involved.  Rather, our purpose here is contribute as
technologists by pointing out that there are other possible ways we
might try to achieve an appropriate balance between individual privacy
and government access to communications.  Key-escrow is not the only
game in town.  Just as technology can produce or exacerbate a basic
conflict, technology can also provide means for its solution.

\subsection{Translucent cryptography}

This paper introduces a new dimension along which debate can be framed
and compromise can be considered: the probability $p$ with which a
particular message can be decrypted by the government.  A fraction $p$
of the messages sent from a user Alice to a user Bob will be
decryptable by the government, and the remaining $1-p$ fraction will
not be decryptable by the government. (To recover messages from one
user to another, the government would wiretap the communication
between them. Of the recovered messages, it will be able to decrypt a
$p$ fraction.)  Of course, the intended recipient of an encrypted
message can always decrypt it; it is only the government that gets a
``partial view.''  The sender of an encrypted message does not know
whether or not that message will be decryptable by the government.  A
small value of $p$ (say, $p=0.02$) favors a libertarian viewpoint,
while a large value of $p$ (say, $p=0.9$) favors
law-enforcement.

In comparison, we see that debate about key-escrow is a difficult one
because there is no ``middle ground'': either the government has
access (if the keys are escrowed) or it does not (if the keys are not
escrowed).  With our proposal, values of $p$ strictly between $0$ and
$1$ form a ``middle ground'' where each side of the debate has some
gain, and some loss.  A value of $p$ can be chosen that balances the
relative concerns.  Congress might pick the appropriate $p$.  

The scheme is called ``translucent'' because it explores the space
between ``opaque'' (strong encryption with no key escrow) and
``transparent'' (no encryption or encryption with key
escrow).\footnote{Other adjectives we considered instead of ``translucent''
were ``variable-opacity,'' ``fractional-access,'' ``partial-access,''
and ``probabilistic-access.'' Translucent seemed the simplest choice.}
With our translucent scheme, the government can decrypt {\em some} of
the messages, but not all.  Just as a translucent door on a shower
stall provides some privacy, but not perfect privacy, translucent
crypto provides some communications privacy, but not perfect privacy.
In our scheme the degree of ``translucency'' can be controlled by
varying $p$.

The value of $p$ does not even need to be fixed once and for all, nor
need it be the same for each kind of encryption equipment.  The value
of $p$ might be chosen small today (say $p=0.02$), and increased or
reduced later as judged appropriate.  Or, one could have one value of
$p$ for cellular phones and a different one for email encryption
programs.  Or, a larger value of $p$ could be used in export versions
of programs than is used for domestic versions.  The value of $p$ used
is built into the encrypting device or program.  It is possible for
the government to measure the effective value of $p$ used by an
encrypting device or program, and so to monitor compliance with the
overall scheme.

Because a criminal does not know which messages are decryptable and
which are not, he runs the risk every time he uses encryption
that this particular message will be decrypted and will be used
against him.

Our proposal also has the advantage, compared to key-escrow
techniques, that there is practically no ``set-up'' required.  Users and
manufacturers do not need to register or escrow their cryptographic
key information.  More specifically, a manufacturer of cryptographic
circuits does not have to secretly manufacture, record, and deliver to
escrow agents the secret keys of each chip, as is the case for the
``Clipper chip.''  Indeed, the chips can be all made identically in a
non-secret manner.  Analogously, there is no need for users of
public-key cryptosystems to submit their private keys for escrowing;
their private keys remain forever their own secrets.  These are
consequences of the fact that our scheme discloses only the message or
session key to the government, not the long-term keys of the devices
or of the users.  The only set-up required is for the government to 
publish a list of public keys, and for Congress to pick 
an appropriate value(s) for $p$.

This proposal can combined with previously-known techniques (such as secret
sharing) to achieve other objectives, such as requiring more than one
government agency to cooperate before any messages can be decrypted, or
limiting the effective time period of a wire-tap warrant.

This proposal is hardly perfect.  One can object to it on many fronts,
both political (the ``other side'' of the debate gets to win a little, and
could win more later if $p$ changes) and technical (like key escrow, our
scheme is easy to subvert by techniques such as double-encryption).  

Nonetheless, this proposal will serve its purpose if it opens our
imaginations a bit, enlarges our sense of the possible, and helps to
bring a difficult national debate closer to a resolution we can all
live with.

\subsection{Fractional oblivious transfer}

We suggest an implementation of translucent cryptography based on an
implementation of {\em non-interactive fractional oblivious transfer.}
The resulting translucent scheme is as efficient, in terms of
encryption, as current suggestions for software key escrow.
Specifically, we need one El Gamal encryption (two exponentiations),
which is the same as the cost of encryption in the Diffie-Hellman
system.

Non-interactive oblivious transfer was introduced by Bellare and Micali
\cite{BellareMi90a}, who provided an implementation achieving transfer
probability $1/2$. We extend this to achieve transfer probability any fraction
$p\in[0,1]$, at no added encryption cost. We call our scheme the ``polynomial''
scheme because it exploits properties of low degree polynomials over finite
fields. Its security is based on the hardness of the Diffie-Hellman problem
in groups of prime order.

In any suggestion for technical solutions to the policy debate we have
been discussing, efficiency is a key issue. Although a scheme cannot,
of course, stand on efficiency alone, it can certainly fail due to its
inefficiency. By providing an implementation of translucent
cryptography which is competitive, in encryption efficiency, with
implementations of key escrow, we have surmounted at least the first
barrier to its discussion.

Furthermore, we suggest that our implementations of fractional 
oblivious transfer, described in \secref{sec-fot}, may be of 
independent interest.

We stress that our implementation of translucent cryptography based on
non-interactive oblivious transfer will not incur any ``extra flows.''
When Alice wishes to communicate with Bob, her only transmission is to
Bob. (In particular, she doesn't communicate on-line with the
government.)  If the government wants to know something about what
Alice is saying to Bob, it must wiretap their communications, and then
it will be able to decrypt a fraction $p$ of the messages it picks up.

\subsection{Version history}

The first version of this paper (by the second author) was titled ``Translucent
Cryptography:~An Alternative to Key Escrow,'' and was presented at the Rump
session of Crypto~95. The current version first appeared as the Technical 
Report \cite{BellareRi96}.

\section{Preliminaries}\label{sec-pre}

The security of our examples and schemes is based on the presumed computational
hardness of computing discrete logarithms or solving the Diffie-Hellman problem
in appropriate finite groups. It will be helpful to briefly pin down the setup.

We work in some cyclic group $G$. We let $g$ denote a generator, namely a group
element such that $G=\bigset{g^i}{i\in Z_q}$, where $q=|G|$ is the order of
$G$.  We let $\log_g(x)$ denote the discrete logarithm of $x\in G$ to base $g$,
namely the unique index $i\in Z_q$ such that $x=g^i$.

A typical choice of group is $G=Z_\rho^*$ where $\rho$ is a large prime.  (We
denote this global prime by $\rho$, since we are already using $p$ to stand for
something else, namely the transfer probability.)  In this case, $q=\rho-1$. 
The discrete logarithm problem here is hard as long as $q$ has at least one 
large prime factor.

Sometimes, we want more special groups. Specifically, we will work in groups of
prime order. This means $q$, the order of the group, is a prime number.  (Note
above $q=\rho-1$, which is not prime. In fact, it is always even.)  There are
many ways to get groups of prime order in which the discrete logarithm problem
is hard. A simple, concrete implementation is to choose a prime $\rho=2q+1$
where $q$ is also prime, and let $G$ be a subgroup of order $q$ of $Z_\rho^*$.
(Specifically, we can fix and publicize an element $g\in Z_\rho^*$ of
order $q$, and let $G=\bigset{g^i}{i\in Z_q}$ be the sub-group generated
by $g$.  Under this implementation, the arithmetic operations are all in
$Z_\rho^*$, so have the usual costs.)

We will see that the technical motivation for working in a group of prime order
is that the set from which the exponents are chosen, namely $Z_q$, is a field,
and thus every non-zero exponent value $i$ has an inverse in this field. 

Recall that the Diffie-Hellman problem for $G$ is: given $g^x,g^y$, compute
$g^{xy}$, where $x,y$ are chosen at random in $Z_q$. The security of El Gamal
encryption relies on the assumption that this problem is computationally
hard. Since El Gamal encryption is used in the non-interactive oblivious
transfer schemes we discuss, the security of these, too, relies ultimately
on this assumption. Recall also that if the Diffie-Hellman problem is hard,
so is the computation of discrete logarithms.

Finally, a piece of notation: for any integer $m$ we let $[m]=\set{1,\ldots,
m}$.

\section{Non-interactive oblivious transfer}\label{sec-ot}

Since our proposal uses non-interactive oblivious transfer techniques, we
provide some background and a sketch of the technology in this section.

\heading{Oblivious transfer.} Rabin \cite{Rabin81} was the first to introduce
the notion of {\em oblivious transfer\/} (OT), in which one party (Alice) can
transfer a message to another party (Larry\footnote{We explain the cast of
characters: Alice and Bob are citizens, who may or may not be up to something.
Larry works for a law-enforcement agency.})  in such a way that:
\begin{newitemize}
\item Larry receives the message with probability exactly $1/2$.
\item Alice does not know whether Larry received the message or not---that is,
she is {\em oblivious} as to whether the transfer was successful or not.
\end{newitemize}
Rabin introduced the notion of oblivious transfer to help solve the
problem of ``exchanging secrets,'' a problem also studied by Blum
\cite{Blum83}.

Protocols for oblivious transfer have been studied by Even, Goldreich,
and Lempel \cite{EvenGoLe85}, Fischer, Micali, and Rackoff
\cite{FischerMR84}, Berger, Peralta, and Tedrick \cite{BergerPeTe85},
Cr\'epeau \cite{Crepeau88}, and others
\cite{Kilian88,e90:denboer,a91:hl,e92:beaver}.  These protocols are
{\em interactive}: they require the recipient, Larry, to actively
participate in the protocol by sending messages to Alice.  For our
purposes, we need the oblivious transfer to be {\em non-interactive}:
Larry should not have to send any messages in order to receive Alice's
message with probability one-half.  With non-interactive oblivious
transfer, Larry needs merely to receive (or overhear) Alice's message
in order to decrypt it with probability one-half.

\heading{Non-interactive OT.} The notion of non-interactive oblivious transfer,
and the first protocol for it, are due to Bellare and Micali
\cite{BellareMi90a}. Further protocols were given by De Santis and Persiano
\cite{e90:desantis} and De Santis, Di Crescenzo and Persiano
\cite{DeSantisDP95}.

To make this paper concrete and self-contained, we describe the simplest
proposal made by Bellare and Micali for implementing non-interactive oblivious
transfer. (This scheme achieves transfer probability one-half.) Our proposal
does not depend on the details of how non-interactive oblivious transfer is
implemented, however, so that other implementation techniques may be used.  The
rest of this section may be skipped by those not familiar with number theory or
those not wishing to get involved in the mathematical details.

An initial {\em global set-up phase\/} establishes the following three public
values: a large global prime $\rho$ (say at least 1024 bits in length); a
generator $g$ of the multiplicative group $Z_\rho^*$; and a value $U$ such that
no one knows the discrete logarithm $\log_g(U)$ of $U$, modulo $\rho$.  More
precisely, computing $U$'s discrete logarithm should be computationally
infeasible for anyone.  Bellare and Micali suggest
ways that values for $\rho$, $g$, and $U$ could be chosen. In our application,
perhaps the ACLU (American Civil Liberties Union) could choose these values.

The second phase is {\em publication of public keys}.  Like the global set-up
phase, this phase needs to be done only once, no matter how many oblivious
transfers will be performed.  Larry publishes as his public key a pair of
values $(V_1,V_2)$ satisfying $V_2=V_1U$, modulo $\rho$.  
Larry should know either the
discrete logarithm of $V_1$, or the discrete logarithm of $V_2$. (He cannot
know both, as argued below.)  We say that $V_i$ is a {\em good key} (for Larry)
if Larry knows the discrete logarithm of $V_i$, otherwise we say that $V_i$ is
a {\em bad key} (for Larry), for $i=1,2$.

In the final {\em communication phase}, we suppose now that Alice wishes to
obliviously send Larry a message $s\in Z_\rho^*$.  (We use $s$ to denote the
message, since later $s$ will denote a session key in Alice's conversation with
Bob.)  Alice can do so by picking one of Larry's two public keys at random, and
encrypting $s$ using that public key and the El Gamal encryption algorithm
\cite{ElGamal85}, as follows: if $i\in\{1,2\}$ is Alice's choice then
\begin{newitemize}
\item Alice picks a value $y$ from $\{0,1,\ldots,\rho-2\}$ uniformly at random,
and sends Larry $(i,E(s,V))$, where 
\begin{newmath}
	E(s,V) = (c_1,c_2) = (g^y, sV_i^y)\ .
\end{newmath}%
(All values computed modulo $\rho$.)
\item If (and only if) Larry knows the discrete logarithm $x$ of $V_i$, he
can compute $s$ via $s = c_2/c_1^x \pmod{\rho}$.
\end{newitemize}
Thus, Larry receives $s$ with probability exactly $1/2$, since only
one of his two public keys is good.  The protocol is oblivious since
Alice doesn't know which of Larry's keys is good. 

Notice that if both of Larry's public keys are good (namely, he knows the
discrete logarithm of both $V_1$ and $V_2$) then he can cheat, since he would
receive the message $s$ with probability one. But we claim he can't make both
his keys good. Indeed, anyone can check that $V_2=UV_1$, and thus if both $V_1$
and $V_2$ are good for Larry, the latter could easily compute the discrete
logarithm of $U$ via $\log_g(U) = \log_g(V_2) - \log_g(V_1) \pmod{\rho-1}$. So
as long as computing the discrete logarithm of $U$ is computationally
infeasible, Larry cannot successfully cheat. 

Note that this protocol is non-interactive. Also note encryption takes
two exponentiations. This is the same as in the Diffie-Hellman public
key system. (There, Bob would have public key $V=g^x$ and private key
$x$, and Alice would send him a message $s$ by sending $E(s,V)$.)

The above protocol differs in presentation and inessential minor respects from
that proposed by Bellare and Micali; see their paper \cite{BellareMi90a}
for other methods and discussion.

It is important to note that successive oblivious transfers are not
independent: if Alice sends two successive messages using Larry's
public key $V$, Larry either receives them both or receives neither of
them.  This property of non-interactive OT has often been pointed out
in the literature, and has relevance to our application, as discussed
later.

% This para added based on referee comment (1) in major comments section

Recall that Larry can cheat if he can compute the discrete logarithm of $U$.
This task gets harder as the prime $\rho$ gets bigger.  Since the role of Larry
in our context is played by the government or a law enforcement agency, who
have more computing power than most people, it would be advisable to make
$\rho$ larger than the norm. 

\section{Translucent Cryptography}\label{sec-tc}

In the previous section we have explained how non-interactive oblivious
transfer can be achieved, where the probability is $p=1/2$ that Larry receives
the message.  In the next section, section~\ref{sec-fot}, we explain how to
achieve non-interactive {\em fractional\/} oblivious transfer, so that transfer
with a wide range of probabilities $p$ can be implemented.  Before diving into
the mathematics required to implement non-interactive fractional oblivious
transfer, however, we explain in this section how non-interactive (fractional)
oblivious transfer can be used to implement translucent cryptography.  This is
rather straightforward.  The reader should, for the moment, accept our promise
that we will explain how to implement non-interactive fractional oblivious
transfer with a variety of values for $p$; this promise will be kept in
section~\ref{sec-fot}. 

We denote by $p$-NFOT a non-interactive fractional oblivious transfer protocol
with transfer probability $p$.

Assume that a probability $p$ has been determined, and that the global
quantities needed to set-up a $p$-NFOT have been determined.\footnote{For the
schemes described in section~\ref{sec-fot}, these quantities are denoted
$\rho$, $g$, and $U$ if one is using the binary scheme, or $G$, $g$ and $U$ if
one is using the polynomial scheme, where no one can feasibly compute the
discrete logarithm of $U$ to the base $g$.} We also assume that Larry (the
government) has published his public key(s), again according to the algorithm
specified by whichever scheme we are using. Thus he can obtain a message sent
via oblivious transfer with probability $p$.

The above computation and publication by Larry is the {\em only\/} set-up
required by our translucent cryptography scheme; there is no need for each user
to escrow shares of his private key, or for manufacturers to escrow shares of
keys stored in each cryptographic device produced.  Each cryptographic product
can be made in an identical manner, embodying the quantities just described.
In practice, each product would also presumably have a unique identifying
serial number, so that its messages can be distinguished from those of other
products.  This number does not need to be secret.

How can a user Alice now send a message $M$ in encrypted form to another user
Bob, in such a way that Larry (who is authorized to eavesdrop on the message)
can decrypt it with probability $p$?

First, Alice determines a ``message key'' (or ``session key'') key $s$
in an arbitrary manner.  The key $s$ might, for example, be freshly
generated, or might be the result of a prior agreement between Alice
and Bob. Then, Alice computes, as a function of Larry's key, a string
$L$ which comprises the message she would send to transfer $s$ to
Larry under the $p$-NFOT scheme in use. (For example, if we are using
the polynomial scheme of section~\ref{sec-fot} and Larry's public key
is $(V_1,\ldots,V_m,W_0,\ldots,W_a$) then Alice picks $i\in [m]$ at
random and lets $L= (i,E(s,V_i))$.) Now, Alice transmits a message to Bob
consisting of the following fields:
\begin{namelist}{F}
\item The encryption of message $M$ using a standard algorithm (e.g. DES)
      and the message key~$s$.
\item Information, if necessary, that allows Bob to determine 
      what secret message key $s$ is being used. 
\item The string $L$ she computed above.
\end{namelist}
The third field, namely $L$, is the ``LEAF'' (Law Enforcement Access
Field).  With probability $p$ this information allows Larry to
determine the message key $s$, and thus to decrypt the first field to
obtain the message $m$. 

The second field would typically consist of the encryption of $s$ under Bob's
public key, as is done for example in Privacy Enhanced Mail
\cite{Kent93}.  Bob can reliably decrypt this field to obtain $s$, and thus
to decrypt the first field to obtain the message $m$.  In a variation,
the session key $s$ would be encrypted in a DES key known only to
Alice and Bob.  Or, this information might consist of a message that
can be used in a Diffie-Hellman key-agreement protocol to establish
$s$.  There are a variety of methods by which Alice can let Bob know
what $s$ is, any of which can be used in our scheme.  

The message might also contain the identifying serial number of Alice's
cryptographic product.  This could be in the clear, or be part of the
information transferred obliviously to Larry in the third field.

To clarify this transmission, we stress that $L$ is not sent to Larry;
it is sent to Bob. Larry obtains it only if he wiretaps the line 
between Alice and Bob. There is no direct communication from Alice
to Larry at any time.

We note that Bob can verify that Alice is following the translucent
cryptography protocol properly, by checking that the LEAF is properly
constructed.  In this way a correct implementation can refuse to work
with ``rogue'' implementations that do not build proper LEAF's.

This completes our description of the basic translucent cryptography
protocol. We now move on to implementations of fractional oblivious
transfer. Refer to \secref{sec-disc} for a more in depth discussion 
of translucent cryptography issues.

\section{Non-interactive Fractional Oblivious Transfer}\label{sec-fot}

We call an oblivious transfer scheme {\em fractional\/} if the
probability $p$ that Larry successfully receives the message may be
chosen to be different from $1/2$.  The only previous literature on
fractional oblivious transfer schemes that we know of is by Brassard
et al. \cite{BrassardCR86}, who discuss the special case of
transferring one message out of a set of $n$ messages.  We now explain
how to achieve non-interactive fractional oblivious transfer schemes
for a variety of values for $p$.

Let's say that a $p$-NFOT is a Non-Interactive Fractional Oblivious
Transfer protocol in which the transfer probability is $p$. Our goal
is to design such protocols for given values of the probability $p\in
[0,1]$. We begin by noting simple solutions for certain values of
$p$. Then we move on to the general case, and present two protocols.

\subsection{Some simple special cases}

\headingg{A one out of $n$ NFOT.} To obtain a simple form of fractional
capability, it is easy to modify the basic scheme discussed above to provide
``one of $n$'' capability non-interactively. (That is, given $n$, we can design
a $p$-NFOT with $p=1/n$.) For this scheme, we work over a group $G$ of prime
order $q$, as described in \secref{sec-pre}.  As before, $g$ is a generator
(now of $G$) and $U\in G$ is such that $\log_g(U)$ is both unknown and
infeasible for anyone to compute. Larry publishes a list of values $(V_0, V_1,
\ldots, V_{n-1})$ such that $V_i = V_0 U^i$, in such a way that only one of
these keys is good for Larry. (See below for how.)  Alice checks that indeed
$V_i=V_0U^i$ for $i=0,\ldots,n-1$, then picks one of Larry's public keys at
random, and uses it to encrypt the message to be sent to him.

To make his key, Larry picks $x\in Z_q$ at random and $i\in Z_n$ at random. He
sets $V_i=g^x$, and then sets $V_j=V_iU^{j-i}$ for $j\neq i$. One can check
that $V_j=V_0U^j$ for all $j=0,\ldots, n-1$.

On the other hand, no matter how Larry makes his key, he cannot know the
discrete logs of two (or more) members of the list of group elements which
comprises his key. For, say, he knew $x_i,x_j$ such that $V_i=g^{x_i}$ and
$V_j=g^{x_j}$ where $0\leq i<j<n$. Dividing, we see that
$U^{j-i}=g^{x_j-x_i}$. It follows that $\log_g(U)$ can be computed, as
$\log_g(U)=(j-i)^{-1}(x_j-x_i)\bmod q$, where $(j-i)^{-1}$ represents the
multiplicative inverse of $j-i$ in the field $Z_q$. (It is to ensure this
inverse exists that we work in a group of prime order.)

\heading{A $n-1$ out of $n$ NFOT.} Similarly for any $n$ it is easy to
obtain a $p$-NFOT with $p=(n-1)/n$.  Larry publishes a list of values
$(V_0,V_1,\ldots,V_{n-1})$ such that $\prod_{i=0}^nV_i = U$, in such a way that
$n-1$ of these keys are good for Larry.  (See below for how.)  Alice checks the
product constraint, then picks one of Larry's public keys at random, and uses
it to encrypt the message to be sent to him.  The product constraint implies
that Larry cannot know the discrete logs of all the keys, so the transfer
probability is $(n-1)/n$.

It is easy for Larry to pick keys satisfying the constraints. He first picks
$i\in Z_n$ at random. Then he picks $V_j\in G$ so that he knows the discrete
logarithm of $V_j$, for all $j\neq i$, and sets $V_i=U/\prod_{j\neq i}V_j$.

This time we don't require a group of prime order; any group in which the
discrete logarithm problem is hard will do.

\heading{Arbitrary $p$.} Now our goal is to accomplish $p$-NFOT for an
arbitrary, given value of $p\in [0,1]$. We would like, ideally, to be
as efficient as the above schemes, and use just one encryption. We
do not accomplish this in our first scheme, the binary scheme of
\secref{sec-binfot} below, where we use a number of
encryptions proportional to the number of bits in the binary expansion of $p$.
Then in \secref{sec-polyfot} we present another scheme which requires only one
encryption.

\subsection{The binary scheme}\label{sec-binfot}

Here is a way to extend the basic scheme to get a fractional scheme
where the probability $p$ can be any finite binary fraction $p=a/2^n$,
where $a$ is an integer in the range $1$ to $2^n-1$.  (The cases $p=0$
and $p=1$ can be easily handled without any oblivious transfer; for
$p=1$ Alice merely needs to encrypt $s$ with an additional public key
known to be good for Larry.) In this solution Alice will use a number
of encryptions depending on $p$ to accomplish the transfer.
(Specifically, $2n$ encryptions, which is $4n$ exponentiations.)

Let the $n$-bit binary expansion of $p = a/2^n = 0.a_1a_2\ldots a_n$, 
so that
\begin{newequation}
	p = \ssum{i=1}{n} a_i 2^{-i}\ . \label{eq:pdef}
\end{newequation}%
We assume the values of $n$, $a$, and $p$ are public knowledge, as are $\rho$,
$g$, and $U$---the global set-up phase is the same as for the scheme in
\secref{sec-ot}. We let $G=Z_{\rho}^*$ be the group over which we work, and 
let $q=\rho-1$ be the order of this group. Recall that exponents range in 
$Z_q$.

\heading{Key setup.} In the publication of public keys phase, Larry publishes 
a sequence of $n$ pairs of public keys:
\begin{newmath}
  (V_1,V_1'), (V_2,V_2'),\ldots,(V_n,V_n')\ ,
\end{newmath}%
where exactly one key in each pair is good for Larry.  For each $i\in [n]$,
Larry picks $x_i\in Z_q$ at random. He then flips a coin $b_i\in \{0,1\}$
to determine whether $V_i$ or $V'_i$ will be good for him, and proceeds to
generate the $i$-th pair of keys as 
\begin{newmath}
	(V_i,V_i') = \cases{  
          (g^{x_i}, Ug^{x_i})  & {b_i=0}  \\
          (g^{x_i}/U, g^{x_i}) & {b_i=1}  \;.
    }
\end{newmath}%
Thus he knows the logarithm of $V_i$ if $b_i=0$ and of $V_i'$ if $b_i=1$.  Note
that $V_i' = U V_i$ in either case, which can be checked by anyone.  Of 
course, Larry should not tell anyone which public keys are good for him.

\heading{Transfer.} We now describe how, in the communication phase, Alice can
non-interactively and obliviously transfer a message $s$ to Larry so that he
receives it with probability $p$. She will send a sequence of $n$ triples
\begin{newequation}
	T_1, T_2, \ldots, T_n  \label{eq-triples}
\end{newequation}%
to Larry, where each triple contains two values encrypted with Larry's keys
$V_i$ and $V_i'$, in a manner to be described.  (In our application, we imagine
that $n$ probably need not be larger than about five to obtain satisfactory
precision in the value of $p$, so that this sequence is actually quite short.)

First, Alice chooses a sequence of $n$ keys $K_1,K_2,\ldots,K_n$ as 
random values in $Z_{\rho}$ and computes their running sums:
\begin{eqnarray*}
L_0 & = & 0, \hbox{~and~} \\
L_i & = & K_1 + K_2 + \ldots + K_i \pmod{\rho}, \hbox{~for~} i = 1,2,
    \ldots,n\ .
\end{eqnarray*}
She also determines a value $J_i$ for each $i\in [n]$, via
\begin{newmath}
	J_i = \cases{
			0	             & \cif{a_i = 0}, \\
			s + L_{i-1} \pmod{\rho} & \cif{a_i=1}\ . 
		     }
\end{newmath}%
Each $J_i$ is either ``junk'' ($0$, if $a_i=0$) or a ``jewel'' ($s+L_{i-1}$,
if $a_i=1$).

Second, Alice chooses a sequence of $n$ random bits $r_1,r_2,\ldots,r_n$. Now
the $i$-th triple in the sequence~(\ref{eq-triples}), namely $T_i$, contains
$r_i$ and the encrypted versions of $J_i$ and $K_i$, where the encryption is
performed using Larry's public keys $V_i$ and $V_i'$ as follows:
\begin{newitemize}
\item If $r_i=0$, then $J_i$ is encrypted with $V_i$ and $K_i$ is encrypted
with $V'_i$; the $i$-th triple is $T_i = (0, E(J_i,V_i), E(K_i,V'_i))$.
\item Otherwise (if $r_i=1$) the public keys are switched: 
$J_i$ is encrypted with $V_i'$ and $K_i$ is encrypted with $V_i$;
the $i$-th triple is $T_i = (1, E(J_i,V'_i), E(K_i,V_i))$.
\end{newitemize}
Since each triple contains $r_i$, Larry knows which way his public keys were
used.  For each $i$, Larry can decrypt either $J_i$ or $K_i$; he knows which
he can decrypt and which he cannot.

This completes our description of the binary non-interactive fractional
oblivious transfer scheme.

\heading{Why this works.} To see that this scheme works as advertised,
note that Alice sends Larry exactly $n$ triples, and that Larry can decrypt
exactly one ciphertext of each triple.  On the $i$-th triple, if $a_i=0$, Larry
gets either junk ($0$) or a key ($K_i$).  If $a_i=1$, Larry either gets a jewel
($s+L_{i-1}$), or a key ($K_i$).  Larry knows whether he gets junk, a jewel, or
a key, since he knows $a_i$ and $r_i$.  Larry obtains $s$ if and only if he
gets $t-1$ keys followed by a jewel, for some $t$, $1\le t \le n$.  He can tell
if he is able to obtain $s$ or not.  Since succeeding in position $t$ happens
only if $a_t=1$, and then only with probability $2^{-t}$, Larry receives $s$
with probability exactly $p$, by equation~(\ref{eq:pdef}).

\heading{Alice's random bits $r$.}  Note that as long as Larry chooses
which of each pair of public keys are good for him at random, then it does not
matter whether or not Alice chooses the bits $r_i$ randomly; Larry has a chance
of exactly $p$ of reading any particular message.  Similarly, as long as Alice
chooses her bits $r$ at random, then Larry will have a chance of exactly $p$ of
reading any particular message, even if Larry did not randomly decide which of
each pair of public keys would be good.

However, we observe that Alice can in principle, if she wishes, choose her $r$
bits to be identical or correlated from message to message.  In some situations
this might give her a perceived advantage, since this might allow Larry to read
all of a sequence of messages, or none of them.

To help ensure that Alice uses appropriate randomness, one could require that
Alice's random bits $r$ be determined in some fixed manner, say by cycling
sequentially through all possible values for $r$, or by hashing (taking a
message digest of) the first field (the encrypted message $m$).  It is easy for
Larry to determine whether or not Alice is complying with this standard
procedure.  The second procedure is not perfect, since Alice can encrypt
several variants of the same message, and only transmit those with desired $r$
values, but this approach may not help her, inasmuch as she doesn't know which
keys are good for Larry.

% This para added based on referee comment (2) in major comments section

On the other hand, if Alice is known to be choosing her ``random'' bits in some
non-random way, say by cycling through all possible values, Larry may have some
advantage. For example, he could choose his public key so as to able to decrypt
a particular ``burst'' of messages. That is, out of $N$ messages Alice sends he
would still get only about a $pN$ fraction, but might be able to arrange that
this was a consecutive sequence, or even the first messages. Thus, Alice may
prefer to use real randomness.

\subsection{The polynomial scheme}\label{sec-polyfot}

We now propose a different scheme in which Alice needs only a single
encryption (costing two exponentiations) in order to accomplish the
transfer, regardless of the value of $p$. (However, the size of 
Larry's public key will be larger than in the scheme above.)

\heading{Preliminaries.} We consider a transfer probability of the
form $p=a/m$ where $a,m$ are integers satisfying $0<a\leq m$. (In the binary
scheme, $m=2^n$ was a power of two. Here we won't make this restriction.)  The
scheme is based, as before, on the hardness of discrete logarithms, but this
time in a group $G$ of prime order $q\geq m+2$ for which the discrete logarithm
problem is hard. (See \secref{sec-pre}).  

Notice that all non-trivial elements of $G$ are generators of $G$. We
let $g$ be a randomly chosen generator of $G$, so $G=\iset{g^i}{i\in
Z_q}$.  As before, we let $U\in G$ be an element for which $\log_g(U)$
is unknown and infeasible to compute.  We let $\a_0=1\in Z_q$. We also
fix $m$ {\em distinct\/} elements $\a_1,\ldots,\a_{m}$ of
$Z_q^*-\{\a_0\}$.  (It must be that $\a_0=1$. But it does not matter
what $\a_1,\ldots,\a_m$ are as long as they are distinct, non-zero,
and non-one, and we suggest the reader think of them as
$2,3,\ldots,m+1$.  That $\a_0,\ldots,
\a_m$ must be distinct is the reason we have $q\geq m+2$.)

The values $p$, $a$, $m$, $\rho$, $q$, $g$, and $\a_0,\ldots,\a_m$ are all
fixed and public.

\heading{The idea.} Before specifying the scheme, let us try to give a
brief, informal overview of the ideas.  Larry will form a public key
$V_1,\ldots, V_{m},W_0,\ldots,W_a$ consisting of $m+a+1$ elements of
$G$. The last $a+1$ elements will be used only by Alice to verify that
Larry's key is properly made.
Letting $x_i=\log_g(V_i)\in Z_q$ for $i=1,\ldots,m$, the key will be
chosen so that:
\begin{onelist}
\item Larry knows a random, size $a$ subset of $\{x_1,\ldots,x_m\}$.
\item There exists a degree $a$ polynomial $f(x)=f_0+f_1x+\cdots+
f_ax^a\in Z_q[x]$ such that
\begin{twolist}
\item $x_i=f(\a_i)$ for all $i=1,\ldots,m$, and
\item {\em Larry does not know $f$.}
\end{twolist}
\end{onelist}
Furthermore, this will be done in such a way that Alice can check the
property~(2). Now if Larry does not know $f$ then he cannot know
{\em more\/} than $a$ of the values $x_1,\ldots,x_{m}$ (otherwise
he could interpolate to find the coefficients of $f$). Thus, in fact,
he knows exactly $a$ of these values. Now to accomplish the transfer,
Alice can choose one key out of $V_1,\ldots,V_{m}$ at random, and use it
as before.  This calls, on the part of Alice, for only a single
encryption.

The problem is how to set up the constraints we have discussed.
Obviously we cannot have Larry choose $f$, since then he would know
it. Instead, we make Larry specify $W_0,\ldots,W_a$ in some particular
way, and then view the coefficients of the polynomial as {\em
implicitly\/} specified by $f_i =\log_g(W_i)$ for $i=0,\ldots,a$.
Furthermore, we will ensure (and Alice will check) that $W_0\cdot
W_1\cdots W_a=U$, which implies that Larry doesn't know all of
$f_0,\ldots,f_a$, and hence doesn't know $f$.  (In our scheme if Larry
is honest he will in fact know the discrete logs of none of the
$W_i$'s.)  Furthermore, Alice can verify item~(2.1) above using
a technique of Feldman \cite{Feldman87} and Pedersen
\cite{e91:pedersen1} used for verifiable secret sharing.

Larry will proceed by first specifying a random, size $a$ subset of
$V_1, \ldots,V_m$ in such a way that he knows the discrete logs of
these $a$ elements. Then, we will show how he can compute
$W_0,\ldots,W_a$ by a linear algebraic technique. Finally, he will use
these values to specify the remaining $m-a$ elements amongst
$V_1,\ldots,V_m$. Let us now describe the scheme in full.

\renewcommand{\arraystretch}{1.3} 

\heading{Key setup.} Larry chooses at random a size $a$ subset of $[m] = \{1,2,\ldots,m\}$. 
This choice can be thought of as specifying an injective map $\pi\Colon 
[a]\to [m]$, where $\pi(1),\ldots,\pi(a)$,
all distinct, are the $a$ chosen indices. He now chooses elements
$x_{\pi(1)},\ldots,x_{\pi(a)}\in Z_q$ at random and sets
\begin{newequation}
  V_{\pi(l)} \eq g^{x_{\pi(l)}}\in G\hspace{20pt}\mbox{for $l=1, \ldots,a$}\;.
  \label{eq-chosenv}
\end{newequation}%
(This specifies $a$ of the elements $V_1, \ldots,V_m$ in such a way
that Larry knows their discrete logs.  The other $m-a$ still need to
be specified, in such a way that Larry doesn't know, and can't
compute, their discrete logs.) Now Larry defines the $a+1$ by $a+1$
Vandermonde matrix
\begin{newmath}  A \eq \left[  \begin{array}{ccccc}
 \a_0^0 & \a_0^1 &  \cdots & \a_0^{a} \\
 \a_{\pi(1)}^0 & \a_{\pi(1)}^1  & \cdots & \a_{\pi(1)}^{a} \\
  \vdots & \vdots & \vdots & \vdots \\
 \a_{\pi(a)}^{0} & \a_{\pi(a)}^1 & \cdots & \a_{\pi(a)}^{a} 
           \end{array}\right]\;.
\end{newmath}%
Since $A$ is Vandermonde it is invertible. Larry computes its inverse
\begin{newmath} B \eq A^{-1} \eq \left[  \begin{array}{cccc}
        \b_{0,0} & \b_{0,1} &  \cdots & \b_{0,{a}} \\
        \b_{1,0} & \b_{1,1} &  \cdots & \b_{1,{a}} \\
         \vdots & \vdots & \vdots & \vdots \\
     \b_{{a},{0}} & \b_{{a},1} & \cdots & \b_{{a},{a}} 
                \end{array}\right]\;.
\end{newmath}%
The arithmetic here is over the field $Z_q$. (Notice that in saying this 
inverse exists and can be computed we need the fact that $Z_q$ is a field. 
This is why we choose $G$ to be of prime order $q$.) Larry now sets
\begin{eqnarray}
  W_0 & = & U^{\b_{0,0}}\cdot\sprod{l=1}{a} V_{\pi(l)}^{\b_{0,l}} \nonumber\\ 
  W_1 & = & U^{\b_{1,0}}\cdot\sprod{l=1}{a} V_{\pi(l)}^{\b_{1,l}} \nonumber\\
   {\vdots\hspace{8pt}} & & \hspace{30pt} \vdots  \label{eq-w} \\
  W_a & = & U^{\b_{a,0}}\cdot\sprod{l=1}{a} V_{\pi(l)}^{\b_{a,l}}\;,\nonumber
\end{eqnarray}
the arithmetic here being in $G$. (We will see that by doing this,
Larry has implicitly chosen the polynomial $f(x)=f_0+f_1x+\cdots
f_ax^a\in Z_q[x]$ where $f_i=\log_g(W_i)$. But Larry does not know
$f_0,\ldots,f_a$.) Now Larry specifies the remaining $V_i$'s as
follows--- he sets
\begin{newequation}
  V_i \eq \sprod{j=0}{a} W_j^{\a_i^j} \hspace{20pt}
\mbox{for all $i\in [m]$ that are not in the range of $\pi$}\;,
                 \label{eq-otherv}
\end{newequation}%
the arithmetic being in $G$. Finally, Larry outputs $(V_1,\ldots,V_m,
W_0,\ldots,W_a)$ as his public key.

\heading{Properties of this key.} To better understand what follows,
it is worth saying something about what Larry accomplishes by the
above steps.  The following claim says that he is implicitly defining
the polynomial $f(x)=f_0+f_1x+\cdots+f_ax^a\in Z_q[x]$ by the matrix
equation \eqref{eq-f}, and that his key is related to this polynomial
as we would like.

\begin{claim}\label{cl-f} Suppose Larry follows the key generation procedure
described above. Define
\begin{newequation}
  \left[\begin{array}{c}f_0 \\ f_1 \\ \vdots \\ f_a\end{array}\right]
 \eq 
\left[  \begin{array}{cccc}
        \b_{0,0} & \b_{0,1} &  \cdots & \b_{0,{a}} \\
        \b_{1,0} & \b_{1,1} &  \cdots & \b_{1,{a}} \\
        \vdots & \vdots & \vdots  & \vdots \\
     \b_{{a},{0}} & \b_{{a},1}  & \cdots & \b_{{a},{a}} 
                \end{array}\right]
  \;
\left[\begin{array}{c}\log_g(U) \\ x_{\pi(1)} \\ \vdots \\ x_{\pi(a)}
     \end{array}\right]\;,
\label{eq-f}
\end{newequation}%
the arithmetic being in $Z_q$, and let $f(x)=f_0+f_1x+\cdots+f_ax^a\in 
Z_q[x]$. Then
\begin{newenum}
\item $\log_g(W_j)=f_j$ for all $j=0,\ldots,a$, and
\item $\log_g(V_i)=f(\a_i)$ for all $i=1,\ldots,m$, and, finally,
\item $f_0+f_1+\cdots+f_a=\log_g(U)$.
\end{newenum}
\end{claim}
The proof of this claim is in \apref{sec-proofs}.  Note that from item~(1)
we have $W_j=g^{f_j}$, and thus from item~(3) we have $W_0\cdot W_1\cdots
W_a=U$, which is the product constraint that Alice will check.

\heading{Verification.} Alice verifies the public key $(V_1,\ldots,V_m,
W_0,\ldots,W_a)$ as follows. First, she checks the size, namely that 
it really consists of $m$ elements of $G$ followed by another $a+1$ 
elements of $G$. Then she checks two things---
\begin{eqnarray}
   U & = & W_0\cdot W_1\cdots W_a \label{eq-checkprod} \\
  V_i & = & \sprod{j=0}{a} W_j^{\a_i^j}\hspace{20pt}\mbox{for all 
        $i=1,\ldots,m$}\;.\label{eq-checkpoly}
\end{eqnarray}
If these checks pass, she accepts the public key as valid. 

One can check that \clref{cl-f} implies that if Larry is honest then 
these checks do succeed. More important, however, is that even if
Larry is not honest, this verification guarantees Alice that
Larry will not receive the OT with probability {\em more\/}
than $p$. Why this is true is discussed below.

We note that Alice has to perform this verification step only once, no matter
how many messages she sends.

\heading{Transfer.} As we have already indicated, to perform the $p$-NFOT, 
Alice picks $i\in [m]$ at random, and uses $V_i$ as the key with which 
to encrypt her message $s\in G$. Namely, she picks $y\in Z_q$ at random and
sends $E(s,V_i)=(c_1,c_2)=(g^y,sV_i^y)$, the operations being in $G$.

\heading{Efficiency.} The key feature is that transfer needs only one
El Gamal encryption (which is two exponentiations), regardless of the
value of $p=a/m$. We pay for this in the size of the public file,
which is $O(k(m+a))$ where $k=|\rho|$ is the security parameter. (In
the binary scheme, it was $O(k\log_2(m))$.)  But this is not too
important. The public file is down-loaded once (or at not too frequent
intervals) and stored by Alice on her machine. The time needed to
compute a ciphertext and the size of the ciphertext don't depend on
the size of this file.

\heading{Security for Alice.} The verification is for Alice's
security; it is supposed to guarantee her that even if Larry is
dishonest, he won't get her data with probability more than $p$.  So
consider a Larry who tries to cheat. His goal is to somehow create the
public key so that he ends up knowing $\log_g(V_i)$ for more than $a$
values of $i\in [m]$. The following claim implies Larry cannot cheat in
this way.  To state it we first need some terminology. Given elements
$W_0,\ldots, W_a$ of $G$, we define the {\em polynomial defined by
$W_0,\ldots,W_a$} as $f(x)=f_0+f_1x+\cdots+f_ax^a$ where
$f_j=\log_g(W_j)$ for $j=0, \ldots,a$. Now, the following claim says that if
verification succeeds then exactly the same conditions as in
\clref{cl-f} hold with respect to the polynomial defined by Larry's
public key, even if Larry had tried to cheat.

\begin{claim}\label{cl-verify} Suppose Alice's verification of key $(V_1,
\ldots,V_m,W_0,\ldots,W_a)$ is successful, and let $f(x)=f_0+f_1x+\cdots
+f_ax^a\in Z_q[x]$ be the polynomial defined by $W_0,\ldots,W_a$. 
Then
\begin{newenum}
\item $\log_g(W_j)=f_j$ for all $j=0,\ldots,a$, and
\item $\log_g(V_i)=f(\a_i)$ for all $i=1,\ldots,m$, and, finally,
\item $f_0+f_1+\cdots+f_a=\log_g(U)$.
\end{newenum}
\end{claim}
The proof is in \apref{sec-proofs}.  In consequence of item~(3), Larry can
know at most $a$ of the values $f_0,\ldots, f_a$, not matter how he
plays, because otherwise he would know $\log_g(U)$. Intuitively, this
means he doesn't know $f$.  But now, from item~(2), it follows that Larry
can know at most $a$ of the values $\log_g(V_1),\ldots,\log_g(V_m)$. 
This, intuitively, means that Larry cannot receive the transfer with 
probability higher than $a/m=p$. Notice that Alice's security
depends on the intractability of the discrete logarithm problem
for Larry.

\heading{Security for Larry.} We want to argue that we have security
for Larry, meaning that Alice doesn't know which subset of $a$ out 
of $n$ keys is the one for which Larry knows the discrete logs.

\begin{claim}\label{cl-larry} Suppose Larry uses the procedure prescribed
above to construct his public key $(V_1,\allowbreak \ldots,\allowbreak
V_m,\allowbreak W_0,\allowbreak \ldots,W_a)$.
Then the distribution on this key is the same as if the key were
generated by the following experiment:
\begin{newenum}
\item Pick $f_0,\ldots,f_a\in Z_q$ at random subject to $f_0+f_1+\cdots+
f_a=\log_g(U)$,
\item Let $f(x)=f_0+f_1x+\cdots+f_ax^a\in Z_q[x]$,
\item For $i=1,\ldots,m$ let $V_i=g^{f(\a_i)}$,
\item For $j=0,\ldots,a$ let $W_j=g^{f_j}$, and 
\item Output $(V_1,\ldots,V_m,W_0,\ldots,W_a)$.
\end{newenum}
\end{claim}
The proof of \clref{cl-larry} is in \apref{sec-proofs}. Now, clearly,
presented with a key from this distribution, Alice has no idea of what
Larry knows about the $\log_g(V_i)$'s, even if she can compute
discrete logs.

Based on this, one can argue that there is no ``key-choosing''
strategy for Alice under which her expected transfer probability is reduced
below $p$.  By this we mean the following. Suppose that instead of
using a random $V_i$ as key, Alice chooses, somehow, probabilities
$p_1,\ldots,p_m$ summing to $1$, and transfers as follows--- she picks
$i\in [m]$ according to the distribution $\Pr[i=j]=p_j$ for all $j\in
[m]$, and then uses $V_i$ as the key. (If she is honest, $p_j=1/m$ for
all $j\in [m]$.) Then her expected transfer probability is still $p$,
regardless of the values of $p_1,\ldots,p_m$.

As for the binary scheme, it may be simplest to specify that Alice's
``random'' choices are to be made in a specific manner, say by cycling
through all values. This, however, might disadvantage Alice slightly
if Larry cheats, as discussed at the bottom of \secref{sec-binfot}.

\section{Discussion and Variations}\label{sec-disc}

\headingg{Set-up.}
Note that Alice needs {\em no} ``set-up'' to follow the translucent
cryptography protocol.  She does not need to be a registered user,
have any private keys escrowed, etc.

\heading{Efficiency.}  With the proposal of \secref{sec-polyfot}
described above, Alice needs to perform $2$ modular exponentiations
(one El Gamal encryption) in order to compute the desired LEAF.  An
implementation can, if it wishes, precompute future session keys and
their associated LEAFs as a means of decreasing the latency in
encrypting a new message. 

\heading{The value of $p$.}  The value of $p$ that is effective is the
value of $p$ that is embedded in Alice's translucent cryptography
implementation.

Different categories of equipment could have different probabilities
$p$.  For example, software and hardware that are exported could have
$p=1$, while domestic versions could have $p=0.02$.

Larry can monitor whether or not Alice is using the correct value of
$p$, by monitoring what fraction of the time he actually succeeds in
getting $s$.


\heading{Warrants.}
To ensure that Larry must get a warrant in order to decrypt his
allowed fraction of the translucent crypto, the value transmitted
obliviously should be the message key $s$ encrypted with the public
key of Jerry (the judge), or his designated agent who can be
available in real-time to decrypt LEAFs.  
This encrypted block could also include the ID
of the software or hardware generating the message, if the search
warrant is to be restricted to messages from a single source.

\heading{Multiple agencies and multiple probabilities}
The LEAF could easily contain messages for two or more agencies that
need to cooperate to get the final message key.  Larry might receive
message key $s_1$ encrypted with his public key, and Louis (who works
for another organization) might receive message key $s_2$, encrypted
with his public key.  The actual message key $s$ might be the sum (or
the exclusive-or) of $s_1$ and $s_2$.

Differing agencies could even receive the message key with different
probabilities.  The FBI might receive the message key with probability
$0.02$, whereas an escrow agent of the user's choice might receive the
message key with probability $1$.

Stewart Baker (in a private communication that was probably intended
to tease the authors) suggested that law enforcement
might find this proposal more attractive if it were implemented in a
related variant, making 1\% of the messages accessible to law
enforcement (without even a warrant(!). Another 20\% or so of the
messages would become accessible if suspicious activity is detected in
the first 1\%, and the remainder would become available to law
enforcement with a court order.  It is straightforward to implement
such a variation based on our ideas.  (It is not so easy, fortunately,
to get around the Constitution!)

\heading{Export.}
Of course, non-U.S. companies may object to Larry accessing their
communications, whether this access was obtained through key escrow or
through translucent cryptography.  Translucent cryptography is likely
to fare no better in an international market than key escrow fares.

On the other hand, it is easy, for example, for U.S. manufacturers to
develop products (say for France) that give U.S. access with
probability $0.5$ and the French government access with probability
$1.0$.  This would merely require the use of two LEAF fields, one
for each government.

\heading{The opening problem.} A weakness of our implementations,
inherited from a weakness of non-interactive oblivious transfer, is
that in some circumstances, if Larry does exercise his privilege and
decrypt the fraction $p$ of Alice's traffic to which he is entitled,
Alice may learn some information about Larry's secret key which would
enable her, in future, to decrease the probability that Larry recovers
her messages.  This happens if Larry not only decrypts, but also
reveals {\em which\/} ciphertexts he decrypted. (As long as Larry
keeps secret the decrypted information, nothing is revealed.)  For
this reason it may be desirable for Larry to have many public keys,
with different keys used in different programs, different devices, or
products produced in different months.  Let us explain this issue by
example.

Say we are using the polynomial scheme, and Larry's public key is $(V_1,V_2,
V_3,W_0,W_1)$, and Larry knows $\log_g(V_1)=x_1$. (The transfer probability 
here is $p=1/3$.) Thus, Larry's secret key consists of two things: a secret
index, namely $1$, saying which of the three keys is a ``receiving'' one
for Larry, and the value $x_1$, which enables the actual receipt. Larry's
security relies on the fact that Alice does not know his secret index;
if she did, she could encrypt using only the other keys, and Larry
would never be able to recover the message.

Now suppose Alice encrypts 5 messages, and her choices of keys are
$V_2,V_1,V_2,V_3,V_2$. Suppose Larry decides to wiretap.  He will
obtain the second message.  A priori Alice does not know which message
Larry got. But suppose now she learns, somehow, that Larry got the
second message. Then she knows that Larry knows $\log_g(V_1)$, because
$V_1$ was the key she used in the second message. Thus she has
determined Larry's secret index. Now she can fool him; in future, she
will never use key $V_1$.

How could Alice learn which ciphertext Larry decrypted? The issue is
how wiretap information is used. We expect that often Larry wiretaps
for his own information; the recovered plaintexts are not revealed to
the public. In such a case, Alice, or other users, learn nothing about
Larry's secret index. But suppose Larry needs to use the wiretap
information, say as evidence in a court case. The plaintexts are then
revealed, and, by their examination, Alice can determine which of her
messages were decrypted. This tells her what is Larry's secret index.

The extent to which this is a problem thus depends on the extent to
which Larry intends to publicize information obtained by wiretaps.
Since this must happen to some extent, we need to mitigate its
effects. Our suggestion, as indicated above, is that Larry have
many public keys, with different keys used in different programs
or devices at different times.

For the benefit of a reader familiar with non-interactive oblivious
transfer (NIOT), let us add some historical notes and comparison.  The
underlying issue of revelation of the secret index of a recipient in a
NIOT based on some action of the recipient arose, and was recognized,
in the context of implementing non-interactive zero-knowledge based on
NIOT \cite{BellareMi90a}.  There the problem was that if the sender
learned that her proof had been rejected then the receiver's secret
index would leak. The suggestion of \cite{BellareMi90a} to overcome
this was to change the public key when a proof was rejected. But this
is not too practical, because the sender can {\em force\/} revelation
by sending bad proofs. (This issue, and attacks based on it, have been
discussed a few times in the literature.) In comparison, in
translucent cryptography, there is much less of a problem, because it
is much harder to force Larry to reveal which ciphertexts he
decrypted. Thus, our suggestion above, that Larry have many different
public keys, seems to provide an acceptable resolution to this
``opening'' problem in this context.

\heading{Other ways of getting around these schemes.}
With sufficient work, these schemes, like other proposals, are easy to
get around.  Two particularly relevant references are Wyner's papers on the
``wire-tap channel'' \cite{Wyner75,OzarowWy85}.  Super-encryption also
defeats this approach, of course; these sorts of ``work-arounds'' on
the part of a user are problems common to any such proposal for
government access to messages.

% This para added based on referee comment (3) in major comments section

It may be worth adding mechanisms to prevent some very simple workarounds like
the following. Alice buys a commercially available crypto-box that implements
the translucent protocol given Larry's keys as input. (The keys can't be
embedded in the box because they may need to be changed now and then.) Alice
then feeds incorrect keys into the box, so that useless LEAFs are produced. 
This can be prevented by having Larry's key digitally signed under some 
global public key which is embedded in the box.

\heading{Why NIOT?} A reader may ask why NIOT is used at
all. Specifically, how about the following instead? Let Larry publicize a
public key of a conventional public key cryptosystem such as RSA, and
let $\calE$ denote encryption under this key. (Larry knows the
corresponding decryption key.)  When Alice is to send a message $m$ to
Bob, she picks, as before, a session key $s$, uses it to produce the
first field (F1) as described in \secref{sec-tc}. The second field too
is as before. She now lets $s^*$ equal $s$ with probability $p$, and
$0$ otherwise. She then lets the LEAF be $\calE(s^*)$. Larry can
access the LEAF, and has $s$ a fraction $p$ of the time.

This is certainly much simpler than NIOT. But the problem is that it
puts greater trust in Alice. Alice could cheat very easily, and yet
evade detection. For example, whenever $m$ is an ``important'' message
she would choose $s^*=0$, and otherwise choose $s^*=s$, doing this in
such a way that she chooses $s^*=s$ a fraction $p$ of the time. Then
Larry gets only the unimportant stuff, but, because he is getting a
fraction $p$ of the plaintexts, he can't really complain.  In contrast,
in NIOT, there is no key-choosing strategy for Alice which lowers the
transfer probability below $p$.

All implementations, whether of key escrow or translucent cryptography
such as we discuss, rely on some trust in Alice. The question is the
{\em degree\/} of this trust. Our goal is to make it as hard as
possible for Alice to cheat. As discussed above, there will always be
ways around the schemes; but let us not make it {\em too\/} easy.

\heading{Comparison with key escrow.}
The approach proposed has the following 
advantages over key-escrow schemes:
\begin{namelist}{A}
\item Set-up is particular easy with our scheme; there is no escrow
      procedure required of users or manufacturers.  We feel that this 
      is a very significant advantage of our proposal.
\item There are no escrow agents holding users' keys, who might be
      tempted (or ordered) to abuse users' privacy.  In our scheme,
      the corresponding agents are those parties holding the private
      keys corresponding to the published public keys.
\item There is a firm upper bound on the extent to which law enforcement
      can encroach on individual privacy; a certain fraction of Alice's
      messages will be private from everyone except their intended 
      recipients.
\item There is a firm lower bound on the extent to which cryptography
      will prevent authorized wiretapping from being effective; a certain
      fraction of Alice's messages will be wire-tappable (on the average).
\item The scheme contains a variable-access rate $p$ that may be changed
      according to the specific use or the perceived risks.
\item Compliance with the scheme can be monitored.
\item The scheme can be easily elaborated or combined with other approaches 
      to meet more detailed requirements.
\end{namelist}
\medskip

\noindent
Our scheme has the following possible disadvantages:
\begin{namelist}{D}
\item Law enforcement may be frustrated that when it has an authorized
wiretap, it is not getting decryption of {\em all} of the messages. (Too bad;
that is the nature of the compromise proposed here.)
\item Individuals may be frustrated that this scheme does not provide
absolute privacy for their messages; law enforcement can read some fraction
of their messages.  (Too bad; that is the nature of the compromise
proposed here.)
\end{namelist}

\heading{Related work.} Upton \cite{Upton93} has suggested using {\em
interactive\/} oblivious transfer as a replacement for key escrow.  In
his suggestion, every time Alice wishes to communicate with Bob, she
must first communicate with Larry, engaging in an oblivious transfer
protocol in which she transfers to Larry either the session key or a
random string, she doesn't know which. But this means Larry must
actively participate in every communications session, which 
creates some significant practical problems.


\section{Open Questions}

Can one build an efficient non-interactive fractional oblivious
transfer scheme based on RSA or the Rabin function rather than on the
Diffie-Hellman assumption?

\section{Conclusions}

We have presented a novel alternative to standard key escrow schemes,
that may allow a generally acceptable compromise to be reached on a
difficult issue of national cryptographic policy. We have proposed an
efficient implementation of it, based on a primitive that may be of
independent interest, namely fractional oblivious transfer.

\section*{Acknowledgments}
\addcontentsline{toc}{section}{Acknowledgments}

We thank Stewart Baker, Tony Eng, Rosario Gennaro, Oded Goldreich, Burt
Kaliski, and an anonymous referee for helpful comments and suggestions.

% Crepeau moved to ``paper.bib'' to avoid getting wrong paper out of crypto:

\addcontentsline{toc}{section}{References}
\bibliography{paper}

\appendix

\section{Proofs of Claims}\label{sec-proofs}

\begin{proof}[\clref{cl-f}] From \eqref{eq-f} we have
\begin{newequation}
   f_j \eq \b_{j,0}\log_g(U)+\ssum{l=1}{a}\b_{j,l}x_{\pi(l)}\hspace{20pt}
    \mbox{for $j=0,\ldots,a$}\;.
\label{eq-fe}
\end{newequation}%
Now {from} \eqref{eq-w} we have
\begin{eqnarray*}
 \log_g(W_j) & = & \log_g\left(U^{\b_{j,0}}\cdot\sprod{l=1}{a}
     V_{\pi(l)}^{\b_{j,l}}\right) \\
 & = & \b_{j,0}\log_g(U)+\ssum{l=1}{a}\b_{j,l}\log_g(V_{\pi(l)}) \\
 & = & \b_{j,0}\log_g(U)+\ssum{l=1}{a}\b_{j,l}x_{\pi(l)} \\
 & = & f_j \;,
\end{eqnarray*}
proving item~(1) of the claim. (Here we used \eqref{eq-chosenv},
namely the fact that $V_{\pi(l)}=g^{x_{\pi(l)}}$ by definition.) Now,
multiply both sides of \eqref{eq-f} by the matrix $A$, and use the
fact that $AB=I$, to get
\begin{newmath}
\left[  \begin{array}{cccc}
 \a_0^0 & \a_0^1 & \cdots & \a_0^{a} \\
 \a_{\pi(1)}^0 & \a_{\pi(1)}^1  & \cdots & \a_{\pi(1)}^{a} \\
 \vdots & \vdots & \vdots  & \vdots \\
 \a_{\pi(a)}^{0} & \a_{\pi(a)}^1  & \cdots & 
  \a_{\pi(a)}^{a} 
                \end{array}\right]
  \;
  \left[\begin{array}{c}f_0 \\ f_1 \\ \vdots \\ f_a\end{array}\right]
 \eq 
\left[\begin{array}{c}\log_g(U) \\ x_{\pi(1)} \\ \vdots \\ x_{\pi(a)}
     \end{array}\right]\;.
\end{newmath}%
In other words,
\begin{eqnarray}
  \ssum{l=0}{a}\a_0^lf_l & = & \log_g(U) \label{eq-feif} \\
  \ssum{l=0}{a}\a_{\pi(j)}^lf_l & = & x_{\pi(j)}\hspace{20pt}\mbox{for
   $j=1,\ldots,a$}\;. \label{eq-feis}
\end{eqnarray}
But recall that $\a_0=1$. Thus \eqref{eq-feif} directly gives us item~(3)
of the claim. Furthermore, note that \eqref{eq-feis} is the same as
\begin{newmath}  f(\a_{\pi(j)}) \eq x_{\pi(j)}\hspace{20pt}\mbox{for
   $j=1,\ldots,a$}\;,
\end{newmath}%
which establishes item~(2) for all $i$ in the range of $\pi$. Now we must
check item~(2) for $i$ not in the range of $\pi$. For these $i$ we know
that $V_i$ is defined by \eqref{eq-otherv}. Taking discrete logs 
of both sides of that equation we have
\begin{newmath}  \log_g(V_i)  \eq \log_g\left(\sprod{j=0}{a} W_j^{\a_i^j}\right) \eq
     \ssum{j=0}{a}\a_i^j\log_g(W_j) \eq \ssum{j=0}{a}\a_i^jf_j \eq
   f(\a_i)\;,
\end{newmath}%
as desired. This completes the proof.
\end{proof}

\noindent
Now, we would like to discuss the security.  Refer to 
\secref{sec-polyfot} for the definition of the polynomial defined by
some elements of $G$.

\begin{proof}[\clref{cl-verify}] Item~(1) is a tautology. Taking discrete
logs of both sides of \eqref{eq-checkpoly} gives
\begin{newmath}  \log_g(V_i)  \eq \log_g\left(\sprod{j=0}{a} W_j^{\a_i^j}\right) \eq
     \ssum{j=0}{a}\a_i^j\log_g(W_j) \eq  \ssum{j=0}{a}\a_i^jf_j 
     \eq f(\a_i)\;,
\end{newmath}%
establishing item~(2). Finally, taking discrete logs of both sides of 
\eqref{eq-checkprod} proves item~(3).
\end{proof}

\begin{proof}[\clref{cl-larry}] Fix the map $\pi$ chosen by Larry. Now
let $f_0,\ldots,f_a\in Z_q$ be arbitrary subject to their sum being
$\log_g(U)$. We argue that there is a unique choice of $x_{\pi(1)},
\ldots,x_{\pi(a)}\in Z_q$ such that \eqref{eq-f} holds, namely
\begin{newequation}
\left[\begin{array}{c} x_{\pi(1)} \\ \vdots \\ x_{\pi(a)}
     \end{array}\right] \eq
\left[  \begin{array}{cccc}
 \a_{\pi(1)}^0 & \a_{\pi(1)}^1  & \cdots & \a_{\pi(1)}^{a} \\
 \vdots & \vdots & \vdots  & \vdots \\
 \a_{\pi(a)}^{0} & \a_{\pi(a)}^1  & \cdots & 
  \a_{\pi(a)}^{a} 
                \end{array}\right]
  \;
  \left[\begin{array}{c}f_0 \\ f_1 \\ \vdots \\ f_a\end{array}\right]\;.
\label{eq-dist}
\end{newequation}%
To see that this choice makes \eqref{eq-f} hold, first note that since
$\a_0=1$ and $f_0+\cdots+f_a=\log_g(U)$ we have
\begin{newmath}
\left[\begin{array}{c} \log_g(U) \\ x_{\pi(1)} \\ \vdots \\ x_{\pi(a)}
     \end{array}\right] \eq
\left[  \begin{array}{cccc}
 \a_0^0 & \a_0^1 & \cdots & \a_0^{a} \\
 \a_{\pi(1)}^0 & \a_{\pi(1)}^1  & \cdots & \a_{\pi(1)}^{a} \\
 \vdots & \vdots & \vdots  & \vdots \\
 \a_{\pi(a)}^{0} & \a_{\pi(a)}^1  & \cdots & 
  \a_{\pi(a)}^{a} 
                \end{array}\right]
  \;
  \left[\begin{array}{c}f_0 \\ f_1 \\ \vdots \\ f_a\end{array}\right]\;,
\end{newmath}%
and now multiplying both sides by $B$ yields \eqref{eq-f}. On the other
hand the choice of \eqref{eq-dist} is unique because multiplying both
sides of \eqref{eq-f} by $A$ recovers it.

This means that for any fixed $\pi$, any vector $f_0,\ldots,f_a$ with
$f_0+\cdots+f_a=\log_g(U)$ has the same probability of being defined
by Larry's choices in his key construction process. Since the
other quantities, namely $V_1,\ldots,V_m,W_0,\ldots,W_a$, are
uniquely defined given $f_0,\ldots,f_a$, we have established
\clref{cl-larry}.
\end{proof}

\end{document}


