From: nobody@cypherpunks.ca (John Anonymous MacDonald)
Date: Tue, 10 Dec 1996 23:27:49 -0800 (PST)
To: cypherpunks@toad.com
Subject: [Crypto Patent] Authentication "scheme"
Message-ID: <199612110718.XAA04680@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain


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]