\documentclass[11pt]{article}
\usepackage{amssymb,amsfonts}

\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textheight}{8.8in}
\setlength{\topsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\topskip}{0in}
\parskip=0.050in
\textwidth=6.5in
\oddsidemargin=0truecm
\evensidemargin=0truecm

\newcommand{\Z}{\mathbb{Z}}	% Rich man's black board's font.
\newcommand{\F}{\mathbb{F}}
\newcommand{\T}{\mathbb{T}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}[section]
\newcounter{note}[section]
\newenvironment{note}{\stepcounter{note} \noindent 
	{\bf Note \thesection.\thenote:}}{}

\newcommand{\comment}[1]{}
\newcommand{\proof}{ \noindent {\bf Proof \ } }
\newcommand{\proofsk}{ \noindent {\bf Proof Sketch \ } }
\def\QED {\hfill $\!\square$ \newline}

\newcommand{\st}{\;\;\mbox{s.t.}\;\;}
\newcommand{\half}{{1 \over 2}}
\newcommand{\xor}{\oplus}
\newcommand{\norm}{\parallel}
\newcommand{\legandre}[2]{\left( {#1 \over #2} \right)}
\newcommand{\set}[2]{\left\{ {#1} \;\big|\; {#2} \right\}}
\newcommand{\lcat}{\langle}
\newcommand{\rcat}{\rangle}

\begin{document}

\mbox{} \vspace{2cm}

\begin{centering}
{\huge
	Protocols for Secure Generation of Shared RSA Keys \\[2cm]
	DARPA Contract F30602-97-C-0326 \\[0.5cm]
}
{\Large
	Data Item Number A007: Technical Information Report.
}

\vspace{2cm}

\begin{tabular}{ccc}
    {\Large Bill Aiello} & \hspace{0.5cm} & {\Large Dan Boneh} \\
    {\large aiello@bellcore.com} &  & {\large dabo@cs.stanford.edu} \\[1cm]
    {\Large Matthew Franklin} & \hspace{0.5cm} & {\Large Jeremy Horwitz} \\
    {\large franklin@research.att.com} & & {\large horwitz@cs.stanford.edu}
\end{tabular}

\end{centering}

\newpage

\section{Executive Summary}

\input{summary}

\newpage

\part{Algorithms for Generating Shared RSA keys}

\vspace{2cm}

\begin{abstract}
We describe efficient techniques for a number of parties to
jointly generate an RSA key.  At the end of the protocol an RSA
modulus $N=pq$ is publicly known. None of the parties know the
factorization of $N$.  In addition a public encryption exponent is
publicly known and each party holds a share of the private exponent
that enables threshold decryption. 
Our protocols are efficient in computation and communication.
\end{abstract}


\input{part1}

\newpage

\part{Generating a Product of Three Primes With \\ an Unknown Factorization}

\vspace{2cm}

\begin{abstract}
We describe protocols for three or more parties to jointly generate a
composite $N = pqr$ which is the product of three primes.  After our
protocols terminate $N$ is publicly known, but neither party knows the
factorization of $N$.  Our protocols require the design of a new type
of distributed primality test for testing that a given number is a
product of three primes.  
\end{abstract}

\input{part2}

\begin{thebibliography}{Knu81}

\bibitem{AGY95}
N. Alon, Z. Galil and M. Yung, ``Dynamic-resharing verifiable secret
sharing,'' ESA 1995.

\bibitem{Bea90} 
D. Beaver, ``Security, fault tolerance, and
communication complexity in distributed systems,'' Ph.D. thesis,
Harvard University, May 1990.

\bibitem{BGW}
M. Ben-Or, S. Goldwasser, A. Wigderson, ``Completeness theorems for
non-cryptographic fault tolerant distributed computation'', 
STOC 1988, pp. 1--10.

\bibitem{Be86} 
J. Benaloh (Cohen), ``Secret sharing homomorphisms:
keeping shares of a secret secret,'' Crypto '86, 251-260.

% \bibitem{BB78} B. Blakley and G. Blakley, ``Security of number
% theoretic public key cryptosystems against random attack,'' {\em
% Cryptologia}, Part I (Vol. 2, No. 4, Oct 1978), Part II (Vol. 3,
% No. 1, Jan 1979), Part III (Vol. 3, No. 2, Apr 1979).

\bibitem{BBBG}
S. Blackburn, S. Blake-Wilson, M. Burmester, S. Galbraith, ``Secure
construction of shared RSA keys'', preprint.

\bibitem{BG84}
M. Blum and S. Goldwasser.  An efficient probabilistic public key
encryption scheme that hides all partial information.  In {\it
Proceedings of Advances in Cryptology: CRYPTO '84}, pages 289--302.
Lecture Notes in Computer Science, Springer-Verlag, New York, 1985.

\bibitem{BF97}
D. Boneh, M. Franklin, ``Efficient generation of shared RSA keys'',
in Proceedings Crypto' 97, pp. 425--439.

\bibitem{BH98}
D. Boneh, J. Horwitz, ``Generating a product of three primes with
and unknown factorization'', Proc. of the third Algorithmic Number Theory
Symposium (ANTS), 1998, pp.

\bibitem{CW79} 
J. Carter and M. Wegman, "Universal classes of hash
functions", {\em J. Comput. Syst. Sci.} 18 (1979), 143--154.

\bibitem{CCD} 
D. Chaum, C. Cr\'{e}peau, and I. Damg{\aa}rd,
``Multiparty unconditionally secure protocols,'' ACM STOC 1988, 11-19.

\bibitem{Cocks97}
C. Cocks, ``Split knowledge generation of RSA parameters'',
Available from the author {\tt cliff\_cocks@cesg.gov.uk}.


\bibitem{Coppersmith}
D. Coppersmith, ``Private Communications''.

\bibitem{D50}
N. De Bruijn, "On the number of uncanceled elements in the sieve
of Eratosthenes",
Proc. Neder. Akad. Wetensch, vol. 53, 1950, pp. 803--812.
Reviewed in LeVeque Reviews in Number Theory, Vol. 4, Section N-28,
p. 221.

\bibitem{DDFY}
A. DeSantis, Y. Desmedt, Y. Frankel, M. Yung, ``How to share
a function securely'', STOC 1994, pp. 522--533.

\bibitem{D}
Y. Desmedt, ``Threshold cryptography," European Transactions on
Telecommunications and Related Technologies, Vol. 5, No. 4, 
July-August 1994, pp. 35--43.

\bibitem{DDB96}
Y. Desmedt, G. Di Crescenzo, M. Burmester, ``Multiplicative non-abelian
sharing schemes and their applications to threshold cryptography'',
Asiacrypt '94, pp. 21--32.

\bibitem{DF91}
Y. Desmedt and Y. Frankel, ``Shared generation of authenticators and
signatures'', Crypto '91, 457--469.

\bibitem{ElGamal}
T. ElGamal, ``A public key cryptosystem and a signature scheme based on the
discrete logarithm'', 
IEEE Transactions on Information Theory, 31(4):469--472, 1985.

\bibitem{FNW96}
R. Fagin, M. Naor, P. Winkler, ``Comparing information without leaking it",
CACM, Vol 39, No. 5, May 1996, pp. 77--85.

\bibitem{FFS88}
U. Feige, A. Fiat, and A. Shamir, ``Zero-knowledge proofs of identity,"
Journal of Cryptology 1 (1988), 77-94.

\bibitem{FS86}
A. Fiat and A. Shamir, ``How to prove yourself: Practical solutions
to identification and signature problems," Crypto '86, 186-194. 

\bibitem{F89}
Y. Frankel, ``A practical protocol for large group oriented networks",
Eurocrypt 89, pp. 56--61.

\bibitem{FGMY97}
Y. Frankel, P. MacKenzie, M. Yung, ``Optimal resilience proactive
proactive public key cryptosystems'', FOCS 1997.

\bibitem{FMY98}
Y. Frankel, P. MacKenzie, M. Yung, ``Robust efficient distributed RSA
key generation'', STOC 1998, pp. 663--672.

\bibitem{FH96}
M. Franklin and S. Haber, ``Joint encryption and message-efficient
secure computation," Journal of Cryptology, 9 (1996), 217-232.

\bibitem{G97}
P. Gemmel, ``An introduction to threshold cryptography'', in CryptoBytes, 
a technical newsletter of RSA Laboratories, Vol. 2, No. 7, 1997.

\bibitem{GJKR96}
R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, 
``Robust and efficient sharing of RSA functions'', 
Crypto 96, pp. 157--172.

\bibitem{GMW}
O. Goldreich, S. Micali, A. Wigderson, ``How to play any mental game'',
STOC 1987, pp. 218--229.

\bibitem{Gor}
J. Gordon, ``Strong primes are easy to find'',
Eurocrypt 84, pp. 216--223.

\bibitem{Gr97}
J. Grantham.  A probable prime test with high confidence.  Available
online ({\tt http://www.clark.net/pub/grantham/pseudo/}).

\bibitem{GQ88}
L. Guillou and J. Quisquater, ``A practical zero-knowledge
protocol fitted to security microprocessor minimizing both
transmission and memory," Eurocrypt '88, 123-128.

%\bibitem{G89}
%C. Gunther, "An identity-based key-exchange protocol,"
%Eurocrpyt '89, 29-37.

%\bibitem{K}
%J. Kilian, ``Founding cryptography on oblivious transfer'', STOC 1988,
%pp. 20--31. 

\bibitem{NFS}
A. Lenstra, H. W. Lenstra ed, ``The development of the number field
sieve'', Lecture Notes in Computer Science 1554, Springer-Verlag,
1994.

\bibitem{ECM}
H. W. Lenstra,  ``Factoring integers with elliptic curves'',  {\it Annals
of Mathematics}, 126:649--673, 1987.

\bibitem{MWB98}
M. Malkin, T. Wu, D. Boneh, ``Experimenting with shared RSA key
generation'', preprint.

\bibitem{OO88}
K. Ohta and T. Okamoto, ``A modification of the Fiat-Shamir scheme,"
Crpto '88, 232-243.

\bibitem{OS90}
H. Ong and C. Schnorr, ``Fast signature generation with a Fiat
Shamir-like scheme," Eurocrypt '90, 432-440.

\bibitem{P}
T. Pederson, ``A threshold cryptosystem without a trusted party,"
Proceedings of Eurocrypt 91, pp. 522--526.

\bibitem{GP87}
R. Peralta and J. van de Graaf.  A simple and secure way to show the
validity of your public key.  In {\it Proceedings of Advances in
Cryptology: CRYPTO '87}, pages 128--134.  Lecture Notes in Computer
Science, Springer-Verlag, New York, 1988.

\bibitem{Rabin}
M. Rabin, ``Probabilistic algorithm for testing primality",
J. of Number Theory, vol. 12, pp. 128--138, 1980.

\bibitem{Tal}
T. Rabin, ``A simplified approach to threshold and proactive RSA'',
Proceedings of Crypto' 98.

\bibitem{Shamir}
A. Shamir, ``How to share a secret'', Comm. of the ACM, Vol. 22, 1979,
pp. 612--613.

\bibitem{SS}
R. Solovay, V. Strassen, ``A fast monte carlo test for primality",
SIAM journal of computing, vol. 6, pp. 84--85, 1977.

\bibitem{WC81} 
M. Wegman and J. Carter, ``New hash functions and their
use in authentication and set equality", {\em J. Comput. Syst. Sci.} 22
(1981), 265--279.

\bibitem{Wiener}
M. Wiener.  Cryptanalysis of short RSA secret exponents.  {\it IEEE
Transactions on Information Theory}, 36(3):553-558, 1990.

\bibitem{Y86}
A. Yao, ``How to generate and exchange secrets'', FOCS 1986, pp. 162--167.

\end{thebibliography}


\end{document}


