Initialization

Here we do not describe the secret sharing scheme is its full generality, but rather describe how it is instantiated for our particular purposes. When a device is initialized for a user, the device first selects a random $(m-1)$-element column vector $\underline{s}\in \mathbb{Z}_{p}^{m-1}$ for $p$ a prime. Here, $p$ can be small; $p = 2^{31}-1$ is a suitable choice, so that arithmetic on $32$-bit processors is very fast. The vector $\underline{s}$ is a secret vector, the recovery of which is necessary to obtain the key $K$. For example, $K$ can be defined as $K = h(\underline{s})$ for $h$ a one-way function, or $K$ can be encrypted with $h(\underline{s})$.

The second step in initialization is to generate a random $2m \times (m-1)$ matrix $\underline{U}= (u_{ij})_{0 \le i < 2m, 0 \le j < m-1}$ where each $u_{ij} \in \mathbb{Z}_{p}$. $\underline{U}$ is a data structure that is stored in addition to the table, though if $\underline{U}$ is generated pseudorandomly, then storing the seed of the pseudorandom process is sufficient for $\underline{U}$ to be regenerated when needed. The $2m$-element table $\underline{t} = (t_0, t_1, \ldots, t_{2m-1})^T \in \mathbb{Z}_{p}^{2m}$ is then generated as $\underline{t}\equiv_p \underline{U}\underline{s}$ (where ``$\equiv_p$'' denotes equivalence modulo $p$). That is, $\underline{t}$ is the table as described in Section 2; intuitively, the element in the $i$-th ``row'' and $j$-th ``column'' for $0 \le i < m$ and $j \in \{0,1\}$ is $t_{2i+j}$.

To complete initialization, $\underline{s}$ is deleted, and $\underline{U}$ (or the seed needed to regenerate it), the table $\underline{t}$, and prime $p$ are stored for the next key regeneration attempt. In addition, $y = h'(\underline{s})$ is stored for some (different) one-way and collision-resistant function $h' \neq h$, so that when $\underline{s}$ is reconstructed, it can be recognized as correct.

After a sufficient number of successful key reconstructions (see Section 4.2), the table $\underline{t}$ is ``hardened'' as described in Section 2: if over a number of successful key reconstructions, each induced feature descriptor $b$ is consistent on the $i$-th feature (i.e., $b(i)$ is usually the same, as specified more precisely in Section 5), then element $t_{2i+(1-b(i))}$ is assigned to be a random element of $\mathbb{Z}_p$. This should usually not affect reconstruction for the correct user, since that user typically selects $t_{2i+b(i)}$.