\begin{table*}[t]
\begin{center}
\begin{tabular}{|r||r|c|c|r|r|r|r||c|c|c|}
\hline
& Sieving & {BGW} & {trial div.} & 
	\multicolumn{2}{c|}{prime test} & \multicolumn{2}{c||}{iterations} & 
	total & net & number of \\
\cline{5-8}
& time & time & time & time & num & time & num & time & traffic &  threads\\
\hline
 512 bit & 39.9  & 55.7 & 2.4 & 37.6   & 36.4 & 77.2  & 119  & 0.15  min 
	& 0.180 Mb &  2 \\
1024 bit & 362.4 & 82.6 & 2.3 &  637.2 & 49.1 & 696.9 &  130 &  1.51 min 
	& 1.162 Mb & 6 \\
2048 bit & 369.3 & 470.9 & 3.6 & 4177.3 & 233.9 & 2198.0 & 495 & 18.13 min 
	& 7.48 Mb &  6 \\
\hline
\end{tabular}
\end{center}
\caption{Shared key generation time among three servers.} \label{maintab}
\end{table*}

We measured the performance of distributed key generation in a number
of environments. First, we measured the performance of our
implementation for a number of common RSA key sizes. Table~\ref{maintab} 
summarizes our results when running the system on three servers.  Note
that all of the measurements, except for network traffic, are given as
an average per thread.  For example, Table~\ref{maintab} shows that
when computing a 512-bit modulus, each thread spent an average of
55.7ms per iteration executing the BGW protocol.  All times are in
milliseconds, unless otherwise noted. Network traffic measurements are
given for the entire key-generation process, and reflect the total
load on the network.  The same amount of traffic is sent as is
received, so only one statistic is given in the table.

We used 333MHz Pentium II's running Solaris 2.5.1. The servers are
connected by a 10-Megabit Ethernet.  Communication between the servers is
protected by SSL, and the optimal (largest) sieving bound is used.

The first column measures the time for distributed sieving for both $p$
and $q$ (Section~\ref{sieving}).  The second column measures the average
time per iteration for the BGW protocol, which is used four times in
sieving and once in the distributed computation of $N$
(Section~\ref{compute}). Next we measure the average time per iteration of
trial division with a bound of 15,000. The next two columns give both the
average running time of the primality test and number of times it was
executed.  Following this is the number of iterations until a modulus is
found and the total average running time per iteration.  Finally, the
average network traffic per key generation is given in megabytes. The
timings are averaged over 20 executions of the algorithm.  Note that the
total time to generate a 1024-bit key is approximately 90 seconds.

We do not give the time to generate a sharing of the signing exponent $d$
once the modulus is found (Section~\ref{keygen}) since it is negligible
compared to the rest of the computation.  These times ranges from 20ms for a
512-bit key to 500ms for a 2048-bit key.

Experimentally, 2 threads per server is optimal for a 512-bit key and
6 threads per server is optimal for a 1024-bit key.  For 2048 bits, 6 threads
also appears to be optimal.

There is a large differences between the 1024-bit key and the 2048-bit
key in the number of primality tests and the number of iterations.
This difference is much smaller between the 512-bit key and the
1024-bit key because the 512-bit key uses 2 threads per server, while
the other two use 6 threads per server.  Since the numbers given are
the average {\em per thread}, the differences between the 512-bit key
and the 1024-bit key are actually quite large.  For example, the
512-bit key requires an average of 238 iterations overall $(238 = 119
\cdot 2)$, while the 1024-bit key requires an average of 780
iterations overall $(780 = 130 \cdot 6)$.

%Increasing the number of bits in the key has two effects.  First, the time
%per iteration is larger, because the calculations are longer.  Second, the
%number of iterations is larger, because primes are more sparse among
%larger numbers.  These two effects amplify each other, so increasing the
%number of bits in the key causes performance to decrease dramatically.

It is interesting to note that for a 1024 bit key the number of
primality tests is about a third of the number of iterations.  Trial
division up to 15000 is able to eliminate two thirds of the candidates
without a primality test.  Normally, trial division is much more
effective.  However, due to the distributed sieving, the effect of
trial division is diminished. Nevertheless, eliminating two thirds of
the candidates is significant. Note that, as expected, the effect of
trial division is smaller for the 2048 bit modulus (only 1 in 2 moduli
are filtered out by it).


\paragraph{Fixed key, varying conditions}
In Table~\ref{numserverstab} we fix the key size to 1024 bits and study
our system's behavior under different conditions. We generate a shared key
among different numbers of servers: 3,4 and 5. All servers run 6 threads.

Running time is measured when all communication is sent in the clear and
when SSL is used to secure communication. Performance is measured over a
wide area network (WAN), and when all servers run on a single machine.  In
all these experiments, the trial division bound is set as in the previous
table.  Again, all measurements are in milliseconds unless otherwise
noted.

\begin{table*}[p]
\begin{center}
\begin{tabular}{|r|l||c|c|c|c|c|c|c|c|}
\hline
&     & Sieve & BGW  & trial div. & prime test & time per  & total \\
& SSL & time & time & time       & time       & iteration & time  \\
\hline
3 Servers & No  & 326  & 413   & 2.2 &  628 & 695  & 1.51 min \\
3 Servers & Yes & 362  & 83    & 2.3 &  637 & 697  & 1.51 min \\
4 Servers & No  & 689  & 861   & 1.5 & 2035 & 1707 & 3.70 min \\
4 Servers & Yes & 804  & 1017  & 1.9 & 2173 & 1909 & 4.14 min \\
5 Servers & Yes & 1466 & 1731  & 1.9 & 2013 & 2589 & 5.61 min \\
\hline
WAN       & Yes & 774  & 1012 & 6.3 & 1626  & 1704 & 5.69 min \\
\hline
Local     & No  & 263 & 334  & 2.7 & 1702 & 1014 & 2.20 min \\
Local     & Yes & 267 & 337  & 3.3 & 1899 & 1115 & 2.42 min \\
\hline
\end{tabular}
\end{center}
\caption{The effect of changing the number and locality of servers} \label{numserverstab}
\end{table*}

The first five rows show the results from running the algorithm on
different numbers of servers, with and without SSL enabled.  Disabling SSL
results in a small increase in performance which grows as the number of
servers increases.  Increasing the number of servers results in a
substantial decrease in performance.  This is due to an increase in
synchronization time, an increase in the distributed sieving time, and an
increase in network traffic. We note that the two extra servers used for
experiments with four and five servers are older and much slower than the
other three.

The line labeled ``WAN'' is especially interesting.  The three servers
involved were two computers at Stanford and one at the University of
Wisconsin-Madison.  We have thus performed the first transcontinental,
distributed RSA key generation.  This takes an average of about 5.7
minutes.  We were stymied in our wish to perform the first
intercontinental, distributed RSA key generation by US export laws.

\comment {
Much of the program's time is spent in the communications package (COM).
This is the result of both network latencies and synchronization.  When
the system is run on separate machines much more time is spent in COM than
when all processes are run on the same machine.  This discrepancy is
caused by network latency.  However, even when all processes are run on
the same machine (local) a large portion of the time is spent in COM.
Also, when the number of servers is increased, more time is spent in COM.

In COM, the servers spend time waiting for data from the other servers
instead of performing calculations.  This delay is due to synchronization.
The synchronization delay happens because the Boneh-Franklin algorithm is
built in a series of steps, and all servers must finish a step before any
of the servers can proceed to the next step.  As the number and separation
of servers increases, the servers are more and more likely to have to wait
for each other.  The last table illustrates that multi-threading reduces
the synchronization penalty.
}

\paragraph{Effect of sieving}
To demonstrate the effectiveness of distributed sieving we measured the
algorithm's running time on a single thread with different sieving bounds.
Clearly, a larger sieving bound is better. The results in
Table~\ref{sievingtab} are the times for generating a 512-bit modulus on
three servers with communication protected by SSL.  Sieving improves
performance by more than a factor of 10 for a 1024 bit modulus.

\begin{table*}[tp]
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|c||r|}
\hline
& Sieving & {trial div.} & 
	\multicolumn{2}{c|}{prime test} & \multicolumn{2}{c||}{iterations} & 
	total \\
\cline{4-7}
& time & time & time & num & time & num & time \\
\hline
Sieve 150 & 22.6 & 1.8 & 36.1 & 89 & 46.8 & 288 & 14.0 sec   \\
Sieve 50  & 19.1 & 1.0 & 30.7 & 99 & 43.8 & 607 & 26.6 sec \\
No sieve  & N/A  & 1.4 & 34   & 149 & 11  & 10794 & 117.0 sec   \\
\hline
\end{tabular}
\end{center}
\caption{The effect of sieving on running time}\label{sievingtab}
\end{table*}

The table shows how sieving dramatically reduces the number of iterations
until a key is found. The larger the number, the more effective sieving
becomes.  Therefore, the key generation program automatically finds the
largest acceptable sieving bound for each key size, given the constraint
that $M < p$ (Section~\ref{sieving}).


\comment{

Increasing the sieving bound increases performance, but the increase in
performance becomes much less as the sieving bound grows.  This effect
occurs since smaller primes sieve out more composites than do larger
primes.

Next, we experimented with the trial division bound.  In contrast to
sieving, where we wanted to use the largest sieving bound possible, there
is an optimal bound for trial division.  Doing trial division with too
many primes will not weed out many composites and will waste time with
useless calculations.  Doing trial division with too few primes will cause
too many primality tests to be executed, drastically slowing the search
for a good moduli.  These results are summarized in Table~\ref{trialdivtab}.

\begin{table*}[tp]
\begin{center}
\begin{tabular}{|r||c|c|c|c|c|c||c|c|}
\hline
& \multicolumn{2}{c|}{trial div.} & 
	\multicolumn{2}{c|}{prime test} & \multicolumn{2}{c||}{iterations} & 
	total & net \\
\cline{2-7}
& time & num & time & num & time & num & time & traffic \\
\hline
Trial div. 15000 & 2.2 & 1432 & 201.3 & 531.3 & 315.7 & 1432.0 & ??? & ???   \\
Trial div. 5000  &  &  &  &  &  &  &  &    \\
No trial div.    &  &  &  &  &  &  &  &    \\
\hline
\end{tabular}
\end{center}
\caption{The effect of trial division on key generation time} \label{trialdivtab}
\end{table*}

}

\begin{table*}[tp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
         & BGW  & trial div. & prime test &  \multicolumn{2}{c|}{iterations}
	& total \\
\cline{5-6}
threads/serv. & time & time       & time       & time & num  & time \\
\hline
one   & 46.5 & 2.2 & 201.3 & 319.5 & 1102 & 5.87 min \\
four  & 67.6 & 2.2 & 414.5 & 529.3 &  365 & 3.22 min \\
five  & 77.1 & 2.2 & 527.2 & 622.7 &  185 & 1.92 min \\
six   & 82.6 & 2.3 & 637.2 & 696.9 &  130 & 1.51 min \\
seven & 87.5 & 2.5 & 810.8 & 781.4 &  129 & 1.68 min \\
\hline
\end{tabular}
\end{center}
\caption{The effect of multiple threads}\label{threadstab}
\end{table*}

\paragraph{Multi-threading}
As discussed in Section~\ref{parallel}, to reduce the time wasted on
synchronization it makes sense to run multiple threads on each of the
servers. While one thread is waiting to synchronize with its peers, other
threads can execute. Table~\ref{threadstab} shows that running several
threads in parallel results in a large decrease in running time. As
expected, each iteration takes longer, but fewer iterations are required
until one of the threads finds a modulus.  We generated the 1024-bit keys
among three servers with SSL enabled.

Multithreading is most beneficial when synchronization takes a lot of
time.  This is most obvious in the WAN trials and in the trials with 5
servers.  When running these tests single-threaded, key generation was
very choppy; bursts of calculations were followed by periods of
waiting.  When running multithreaded, key generation proceeds
smoothly, making much better use of the servers' processors.  On the
WAN, generating a 1024-bit key with a single thread took 26.5 minutes,
while it took only 5.7 minutes using 6 threads per server.


