\relax 
\@writefile{toc}{\contentsline {section}{\numberline {1}Executive Summary}{2}}
\citation{MWB98}
\citation{FS86}
\citation{FFS88}
\citation{FH96}
\citation{GQ88}
\citation{OO88}
\citation{OS90}
\citation{G97}
\citation{Shamir}
\citation{F89}
\citation{DF91}
\citation{DDFY}
\citation{FGMY97}
\citation{Tal}
\citation{P}
\@writefile{toc}{\contentsline {part}{I\hspace  {1em}Algorithms for Generating Shared RSA keys}{4}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Introduction}{4}}
\newlabel{intro}{{2}{4}}
\citation{Y86}
\citation{GMW}
\citation{BGW}
\citation{CCD}
\citation{FMY98}
\citation{BGW}
\citation{Cocks97}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Communication and privacy model}{5}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Overview}{6}}
\newlabel{overview}{{3}{6}}
\@writefile{toc}{\contentsline {paragraph}{Notation}{6}}
\@writefile{toc}{\contentsline {paragraph}{Performance issues}{6}}
\citation{D50}
\citation{SS}
\citation{Rabin}
\@writefile{toc}{\contentsline {paragraph}{Generation of shares}{7}}
\newlabel{factor}{{3.1}{7}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Distributed primality test}{7}}
\newlabel{test}{{4}{7}}
\newlabel{testtrue}{{4.1}{8}}
\newlabel{zeroknow}{{4.2}{10}}
\citation{BGW}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}An alternative to Step (4)}{11}}
\newlabel{alternative}{{4.1}{11}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Distributed computation of $N$}{11}}
\newlabel{compute}{{5}{11}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}The BGW method}{11}}
\newlabel{BGW}{{5.1}{11}}
\citation{BGW}
\citation{BF97}
\newlabel{BGW-sim}{{5.1}{12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}BGW Modulo non primes}{13}}
\newlabel{BGW-noprime}{{5.2}{13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}Sharing the final outcome}{13}}
\newlabel{modified}{{5.3}{13}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Trial division}{14}}
\newlabel{trial}{{6}{14}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Shared generation of public/private keys}{14}}
\newlabel{keygen}{{7}{14}}
\citation{Be86}
\citation{F89}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.1}Small public exponent}{15}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2}Arbitrary public exponent}{15}}
\newlabel{large-e}{{7.2}{15}}
\citation{FGMY97}
\citation{FMY98}
\citation{Bea90}
\citation{Tal}
\citation{MWB98}
\newlabel{eqn1}{{1}{16}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3}$t$-out-of-$k$ sharing}{16}}
\newlabel{t-out-of-k}{{7.3}{16}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Optimizations}{17}}
\newlabel{opt}{{8}{17}}
\citation{BH98}
\citation{FMY98}
\citation{BBBG}
\@writefile{toc}{\contentsline {section}{\numberline {9}Robustness}{18}}
\newlabel{robustness}{{9}{18}}
\citation{BH98}
\citation{MWB98}
\citation{Gor}
\citation{DF91}
\citation{GJKR96}
\citation{Cocks97}
\citation{ElGamal}
\@writefile{toc}{\contentsline {section}{\numberline {10}Summary and open problems}{19}}
\citation{Coppersmith}
\citation{F89}
\citation{Shamir}
\citation{G97}
\@writefile{toc}{\contentsline {part}{II\hspace  {1em}Generating a Product of Three Primes With \\ an Unknown Factorization}{21}}
\@writefile{toc}{\contentsline {section}{\numberline {11}Introduction}{21}}
\citation{BF97}
\citation{Cocks97}
\citation{BF97}
\citation{BF97}
\citation{BGW}
\citation{CCD}
\citation{Y86}
\citation{BF97}
\citation{BF97}
\citation{BGW}
\@writefile{toc}{\contentsline {section}{\numberline {12}Motivation}{22}}
\citation{Wiener}
\citation{NFS}
\citation{BF97}
\citation{Cocks97}
\citation{FMY98}
\citation{BF97}
\citation{BGW}
\@writefile{toc}{\contentsline {section}{\numberline {13}Preliminaries}{24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {13.1}Communication and Privacy Model}{24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {13.2}Generation of $N$}{24}}
\newlabel{sec:computeN}{{13.2}{24}}
\citation{BF97}
\@writefile{toc}{\contentsline {subsection}{\numberline {13.3}Sharing of $(p-1)(q-1)(r-1)$ and $(p+1)(q+1)(r+1)$}{25}}
\@writefile{toc}{\contentsline {subsection}{\numberline {13.4}Comparison Protocol}{25}}
\newlabel{sec:hash}{{13.4}{25}}
\@writefile{toc}{\contentsline {section}{\numberline {14}The Probabilistic Primality Test}{26}}
\newlabel{sec:main}{{14}{26}}
\newlabel{fact:simple}{{14.1}{27}}
\newlabel{thm:main}{{14.2}{27}}
\citation{GP87}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.1}Step 3: Testing that $N = p^{\alpha } q^{\beta } r^{\gamma }$}{29}}
\newlabel{sec:three}{{14.1}{29}}
\citation{BG84}
\newlabel{lem:count}{{14.3}{30}}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.2}Implementing a Fermat Test with No Information Leakage}{31}}
\newlabel{sec:fermat}{{14.2}{31}}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.3}Step 4: Zero-Knowledge Test that $\mathop {\mathgroup \symoperators gcd}(N, p+q+r) = 1$}{31}}
\newlabel{sec:gcd}{{14.3}{31}}
\citation{Cocks97}
\@writefile{toc}{\contentsline {section}{\numberline {15}Extensions}{32}}
\@writefile{toc}{\contentsline {section}{\numberline {16}Conclusions and Open Problems}{32}}
\citation{Gr97}
\bibcite{AGY95}{1}
\bibcite{Bea90}{2}
\bibcite{BGW}{3}
\bibcite{Be86}{4}
\bibcite{BBBG}{5}
\bibcite{BG84}{6}
\bibcite{BF97}{7}
\bibcite{BH98}{8}
\bibcite{CW79}{9}
\bibcite{CCD}{10}
\bibcite{Cocks97}{11}
\bibcite{Coppersmith}{12}
\bibcite{D50}{13}
\bibcite{DDFY}{14}
\bibcite{D}{15}
\bibcite{DDB96}{16}
\bibcite{DF91}{17}
\bibcite{ElGamal}{18}
\bibcite{FNW96}{19}
\bibcite{FFS88}{20}
\bibcite{FS86}{21}
\bibcite{F89}{22}
\bibcite{FGMY97}{23}
\bibcite{FMY98}{24}
\bibcite{FH96}{25}
\bibcite{G97}{26}
\bibcite{GJKR96}{27}
\bibcite{GMW}{28}
\bibcite{Gor}{29}
\bibcite{Gr97}{30}
\bibcite{GQ88}{31}
\bibcite{NFS}{32}
\bibcite{ECM}{33}
\bibcite{MWB98}{34}
\bibcite{OO88}{35}
\bibcite{OS90}{36}
\bibcite{P}{37}
\bibcite{GP87}{38}
\bibcite{Rabin}{39}
\bibcite{Tal}{40}
\bibcite{Shamir}{41}
\bibcite{SS}{42}
\bibcite{WC81}{43}
\bibcite{Wiener}{44}
\bibcite{Y86}{45}