frequencies or common pairs of letters, which reduces conscious recognition of the embedded repeating sequence. 2

Let Σ denote the set of all possible secret keys, namely, the set of 30-character sequences corresponding to Euler cycles in Figure 2. The number of Euler cycles in this graph can be computed using the BEST theorem11 (where the number of spanning trees of the K6 graph is 64 by Cayley’s formula, and every vertex’s in-degree is 5, so Πv (deg (v)– 1)! is 246), which gives

keys =Σ= 64 · 246 ≈ 237.8.

Hence, the learned random secret has about 38 bits of entropy, which is far more than the entropy of standard memorized passwords.

Training. Users learn a random 30-item secret key k ∈ Σ
by playing the SISL task in a trusted environment. To train
users, we experimented with the following procedure:
• While performing the SISL task the trainee is presented
with the 30-item secret key sequence repeated three
times followed by 18 items selected from a random
other sequence (subject to the constraint that there will
be no back-to-back repetitions of the same cue), for a
total of 108 items.

• This sequence is repeated five times, so that the trainee is presented with a total of 540 items.

• At the end of this sequence, there is a short pause in the SISL task and then the entire sequence of 540 items (including the pause at the end) is repeated six more times.

During the entire training session, the trainee is presented with 7 × 540 = 3780 items, which takes approximately 30–45 minutes to complete. After the training phase completes, the trainee runs through the authentication test described next to ensure that training succeeded. The system records the final playing speed that the user achieved.

repeating sequence on 80% of the trials. The task is designed to keep each user at (but not beyond) the limit of his or her abilities by gradually varying the speed of the falling circles to achieve a hit rate of about 70%. Knowledge of the embedded repeating sequence is assessed by comparing the performance rate (percent correct) during times when the cues follow the trained sequence to that during periods when the cues follow an untrained sequence.

All of the sequences presented to the user are designed to prevent conspicuous, easy-to-remember patterns from emerging. Specifically, training as well as random sequences are designed to contain every ordered pair of characters exactly once with no character appearing twice in a row (thus the sequence length must be 6 × 5 = 30). The result is that while the trained sequence is performed better than an untrained sequence, the participant usually does not consciously recognize the trained sequence. In order to confirm this in experimental work, after SISL participants are typically asked to complete tests of explicit recognition in which they specify how familiar various sequences look to them.

Compared to the original SISL task using 4 keys, our version increases the space of possible sequences from only 256 to over 240 billion. In addition, the gap we introduced in the middle of the visual display makes it easier to associate a column with the correct hand—left or right—responsible for that column.

The SISL task is delivered to users as a Flash application via a Web browser. Participants navigate to our Web site, www.brainauth.com, and are presented with a consent form. Once they agree to participate, the applet downloads a random training sequence and starts the task. Upon completion of the training and test trials, the explicit recognition test is administered, and results are uploaded to the server. Once we describe our authentication system, we will return to describe how the SISL applet functions in the bigger scheme of our experiments with multiple users.

3. THE BASIC AUTHENTICATION SYSTEM
USING IMPLICIT LEARNING

The SISL task provides a method for storing a secret key within the human brain that can be detected during authentication, but cannot be explicitly described by the user. Such a system avoids the problem that people can be persuaded to reveal their password and can form the basis of a coercion-resistant authentication protocol. If the information is compromised, a new identifying sequence can be trained as a replacement—resulting in a change of password.

The identification system operates in two steps: training followed by authentication. In the training phase, the secret key learned by the user is as in the expanded SISL task, namely, a sequence of 30 characters over the set S = {s, d, f, j, k, l}. We only use 30-character sequences that correspond to an Euler cycle in the graph shown in Figure 2 (i.e., a cycle where every edge appears exactly once). These sequences have the property that every non-repeating bigram over S

(such as ‘sd’, ‘dj’, and ‘fk’) appears exactly once. In order to
anticipate the next item (e.g., to show a performance advan-
tage), it is necessary to learn associations among groups
of three or more items. This eliminates learning of letter
sf
l
kj
d
Figure 2. The secret key we generate is a random 30-character
sequence from the set of Euler cycles in this directed graph.
The resulting sequence contains all bigrams exactly once, excluding
repeating characters.