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 trends⁸ 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

$$\frac{{m \choose c}}{2} + \sum_{i = 0}^{c-1} {m \choose i}$$ (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).

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.