Check out the new USENIX Web site. next up previous
Next: Security Up: Encoding Scheme Previous: Key reconstruction


Performance

For performance measurements we choose to benchmark key reconstruction on a 206 MHz StrongArm and a 500 MHz Ultra II. The first processor is that currently available in the IPAQ$^{\rm TM}$, on which our current implementation runs. The second processor is in line with the current trends8 in the hand-held market, and thus, allows us to forecast expected performance on future PDAs. Our performance benchmarks consists of a collection of C/C++ modules cross-compiled for the ARM, comprising of signal processing code, an enhanced version of cryptolib1.2 [11] updated by Daniel Bleichenbacher, and a matrix manipulation package newmatv9.0 [5] for implementing the segmentation algorithms outlined in [16].

To test the performance of our key reconstruction routines we devised the following experiment. First, an $m \times 2$ table of shares of the key $K$ is generated as outlined in Section 2, i.e., as a user's key regeneration table would be initialized in practice. Then, $d$ rows of the table (features) are selected at random to be distinguishing, and one element of each of these $d$ rows is perturbed randomly--as if the user were consistent in utilizing the other element of this row (see Section 2). Finally, a feature descriptor $b$ is chosen with the property that $c
\le c_{\rm max}$ of the $d$ distinguishing features (chosen at random), say $b(i_1),\ldots,b(i_c)$, are ``errors'', i.e., are set to select the randomly perturbed elements of rows $i_1,\ldots,i_c$. The key reconstruction process performs a number of reconstructions that depends on $c$ in its attempts to correct for such errors; the number of reconstructions performed in the worst case is shown in expression (2) of Section 2. Our benchmark is the amount of time required to reconstruct the key $K$ on average, which is a rough measure of the time required to perform

\begin{displaymath}
\frac{{m \choose c}}{2} + \sum_{i = 0}^{c-1} {m \choose i}
\end{displaymath} (5)

secret sharing reconstructions and test each for correctness. Note that for $c = c_{\rm max}$, (5) is less than (2) by ${m \choose c}/2$ since on average, reconstruction succeeds after searching half of the feature descriptors that correct $b$ on exactly $c$ locations.

Figure 2: Key reconstruction performance for $m \in \{60, 70, 80\}$. Depicted are average (of $50$ executions) elapsed times for key reconstruction on the IPAQ (left) and a 500 Mhz processor which reflects upcoming PDA processor trends (right).
\begin{figure*}
\begin{center}
\leavevmode \epsfxsize =3.2in \epsfbox{IPAQPerf...
...vevmode \epsfxsize =3.2in \epsfbox{UltraPerf.eps}
\end{center}
\end{figure*}

Our results for this benchmark, shown in Figure 2, are significantly less than multiplying (5) by the time to perform and test a single reconstruction in our secret sharing scheme. The reason is due to the significant optimizations that can be achieved as described in Section 4.2.


next up previous
Next: Security Up: Encoding Scheme Previous: Key reconstruction
fabian 2002-08-28