Unlike other access control systems based on biometric features, keystroke analysis has not led to techniques providing an acceptable level of accuracy. The reason is probably the intrinsic variability of typing dynamics, versus other---very stable---biometric characteristics, such as face or fingerprint patterns. In this paper we present an original measure for keystroke dynamics that limits the instability of this biometric feature. We have tested our approach on 154 individuals, achieving a False Alarm Rate of about 4% and an Impostor Pass Rate of less than 0.01%. This performance is reached using the same sampling text for all the individuals, allowing typing errors, without any specific tailoring of the authentication system with respect to the available set of typing samples and users, and collecting the samples over a 28.8-Kbaud remote modem connection.

We study the learnability of multiplicity automata in Angluin's exact learning model , and we investigate its applications. Our starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function to the rank of its Hankel matrix. With this theorem in hand, we present a new simple algorithm for learning multiplicity automata with improved time and query complexity, and we prove the learnability of various concept classes. These include (among others): -The class of disjoint DNF, and more generally satisfy- O (1) DNF. -The class of polynomials over finite fields. -The class of bounded-degree polynomials over infinite fields. -The class of XOR of terms. -Certain classes of boxes in high dimensions. In addition, we obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2). While multiplicity automata are shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, we study the limitations of this method. We prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulas or even k -term DNF for k = ω(log n ) or satisfy- s DNF formulas for s = ω(1). These results are proven by exhibiting functions in the above classes that require multiplicity automata with super-polynomial number of states.

We present a related family of authentication and digital signature protocols based on symmetric cryptographic primitives which perform substantially better than previous constructions. Previously, one-time digital signatures based on hash functions involved hundreds of hash function computations for each signature; we show that given online access to a timestamping service, we can sign messages using only two computations of a hash function. Previously, techniques to sign infinite streams involved one such one-time signature for each message block; we show that in many realistic scenarios a small number of hash function computations is sufficient. Previously, the Diffie Hellman protocol enabled two principals to create a confidentiality key from scratch: we provide an equivalent protocol for integrity, which enables two people who do not share a secret to set up a securely serialised channel into which attackers cannot subsequently intrude. In addition to being of potential use in real applications, our constructions also raise interesting questions about the definition of a digital signature, and the relationship between integrity and authenticity.

We consider the problem of identifying the behavior of an unknown automaton with multiplicity in the field Q of rational numbers (Q-automaton) from multiplicity and equivalence queries. We provide an algorithm which is polynomial in the size of the Q-automaton and in the maximum length of the given counterexamples. As a consequence, we have that Q-automata are probably approximately correctly learnable (PAC-learnable) in polynomial time when multiplicity queries are allowed. A corollary of this result is that regular languages are polynomially predictable using membership queries with respect to the representation of unambiguous nondeterministic automata. This is important since there are unambiguous automata such that the equivalent deterministic automaton has an exponentially larger number of states.

A system that performs automated concept acquisition from examples and has been specially designed to work in noisy environments is presented. The learning methodology is aimed at the target problem of finding discriminant descriptions of a given set of concepts and uses both examples and counterexamples. The learned knowledge is expressed in the form of production rules, organized into separate clusters, linked together in a graph structure. Knowledge extraction is guided by a top-down control strategy, through a process of specialization. The system also utilizes a technique of problem reduction to contain the computational complexity. Several criteria are proposed for evaluating the acquired knowledge. The methodology has been tested on a problem in the field of speech recognition and the experimental results obtained are reported and discussed.<>

Typing rhythms are the rawest form of data stemming from the interaction between users and computers. When properly sampled and analyzed, they may become a useful tool to ascertain personal identity. Moreover, unlike other biometric features, typing