Encoding Scheme

We review the encoding scheme of Bleichenbacher presented in [1]. That scheme focuses on the particular secret sharing scheme we use to populate the $m \times 2$ table described in Section 2 and from which the key $K$ is reconstructed. We quickly found in the implementation of this technique on the resource-constrained IPAQ that the secret sharing schemes suggested in [15] would not suffice. That paper suggests three different schemes. One is sufficiently resource efficient for our purposes but also has potential security weaknesses (see [15, Sections 5.1-5.2], [2]), and while the other two address this weakness [2], they are simply too computationally intensive during reconstruction to permit the degree of error correction we require. Therefore, to achieve sufficiently inexpensive reconstruction, we use a secret sharing scheme that permits fast reconstruction and that appears to be secure for our purposes.

We emphasize that the type of security we require for our secret sharing scheme is different from the typical security definition of a secret sharing scheme. The latter definition is, informally, that an adversary not possessing a sufficient set of shares be unable to reconstruct the secret. In our case, however, the adversary who captures the device is in possession of all shares in the table, and so clearly possesses enough shares to reconstruct the secret. Our security requirement is rather that the adversary be unable to efficiently find a sufficient set of valid shares in the table, i.e., a set containing a valid share from each row of the table and no invalid (random) elements. Ideally, the best the adversary could do would be to repeatedly try reconstruction with a randomly chosen set containing one element from each row. However, because the invalid shares are placed according to an unknown distribution determined by the biometric features of the user--and not uniformly at random--it is impossible to formally reduce the security of such a scheme to a well-known cryptographic problem. (Obviously there are distributions that would leave the scheme trivially breakable.) As such, until we find a better way to model security, we are stuck with heuristically secure schemes; the approach described in this section is one. Nevertheless, we will comment in detail about our current knowledge of the security of this scheme in Section 4.4.