Just snatched off the newspool... Anitro --------------------------------------------------------------------------- Scheme for authentication of at least one prover by a verifier Source: MicroPatent MicroPatent via Individual Inc. : Abstract: A new procedure for authentication of at least one prover by a verifier, the authentication being based on public and secret key cryptographic techniques and making use of a zero-knowledge protocol. In addition, this protocol is established using the problem of constrained linear equations and finds applications in cryptography. This procedure uses a published matrix M of dimension m.times.n where coefficients are chosen at random from the integers from 0 to d-1, where d is generally a prime number close the square of a number c. The "prover" authenticates itself to a "verifier" by performing hashing functions based on a randomly chosen vector U of dimension m and a randomly chosen vector V of dimension n, the results of which are called commitments and are sent to the prover. The prover then chooses one of several predefined functions and requests that the verifier perform this one predefined function. When the verifier receives a result of the predefined function, it compares the result with the commitments to determine if the prover has provided a correct set of responses. The procedure also can be repeated for other random vectors U and V for increased security. Ex Claim Text: Method for authenticating a prover by a verifier based on a cryptographic technique using a secret key, a public key and a zero-knowledge protocol, the method comprising the steps of: a) generating a secret key, including at least one vector S of dimension n having coordinates chosen from a set X, b) generating a matrix M of dimensions m.times.n whose coefficients are chosen at random from integer values from 0 to d-1, where d is a prime integer close to the square of a number c, c) generating a public key comprising at least one vector P such that P=g(M(S)), where g is a function defined by said set X and a subgroup G of a set of integers (1, 2, . . . d-1) and which associates an element g(x) of G to each coordinate x of the at least one vector P such that x is described uniquely as a product of g(x) and an element k(x) of X; d) generating at least two random vectors by the prover; e) generating plural commitments by applying a cryptographic hash function to functions of S, M and the at least two random numbers; f) exchanging plural messages between the prover and the verifier based on said public key and said secret key; and g) authenticating the prover by the verifier based on said plural messages, said public key and said secret key. Patent Number: 5581615 Issue Date: 1996 12 03 Inventor(s): Stern, Jacques [12-09-96 at 14:42 EST, Copyright 1996, MicroPatent]