Authentication method and system employing secret functions...

Details Authentication method and system employing secret functions... Authentication method and system employing secret functions...

1998-08-21

2003-11-18

Hayes, Gail (Department: 2131)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C380S028000, C380S030000, C380S286000, C713S156000, C713S159000, C713S171000, C713S173000, C713S180000

Reexamination Certificate

active

06651167

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to information security techniques. More particularly, the present invention relates to a method and a system for authentication whose basis for security resides in the difficulty in solving annihilator determining problems, wherein system users are granted a prover's function based on secret information while the secret information itself is being hidden.
2. Description of the Related Art
Decryption keys for public key cryptosystems, signature keys for signature systems and authentication keys for authentication systems are all characteristic information that authenticates those who possess these items of secret information.
Described below is a typical authentication method proposed by Guillou and Quisquater in “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory” (Advances in Cryptology EUROCRYPT '87, C. G. Guenther (ed.), Springer-Verlag, pp. 123-128).
FIG. 1
shows how this authentication method works.
In
FIG. 1
, it is assumed that n stands for a composite number which is difficult to factorize; G for a multiplicative group (Z
Z)* of the ring of residue classes of rational integers modulo n; p for a prime number not dividing the Carmichael function &lgr;(n) of n; F
p
for the finite field with p-elements; D for a space of commitments; &pgr; for a function from G to D; I&egr;G for public verification information; and x&egr;G for authentication characteristic information satisfying Ix
p
=1.
Those who possess authentication characteristic information x may carry out the following proverr's operations:
1. Generate a random number k&egr;G and transmit a commitment r=&pgr;(k
p
).
2. Transmit a response s=kx
c
in reply to a given challenge c&egr;F
p
.
Any party who knows verification information I can verify the prover's operations by performing the following verifier's operations to make sure that the prover indeed possesses the authentication characteristic information:
1. Upon receipt of a commitment r, transmit a randomly generated challenge c&egr;F
p
to the prover.
2. Check that the returned response s satisfies r=&pgr;(s
p
I
c
)
The method above is built on the assumption that those who possess the secret information will keep it undisclosed. Such confidentiality makes it possible to implement encrypted statements that may be decrypted, signatures that may be generated, and authenticating procedures that may be executed, by only those who have the secret information.
The above method may be employed uniquely if those who possess the secret information will suffer disadvantages in case they disclose the information. A typical situation to which the method may apply is one in which secret information, kept by each individual, is the characteristic information that authenticates the individual in question.
In such cases, the characteristic information plays the role of keys to one's home or one's seal for official approval. In fact, it is easy to realize such keys or individuals' seals in the form of digital information as a direct application of the above-described cryptgraphic techniques. Illustratively, the lock to one's home may be constituted as a verifier according to the Guillou-Quisquater method. The lock of the home is opened only if the verification is successful. In that case, the possession of authentication characteristic information x is exactly equivalent to the custody of the key to one's home.
In contrast to the situation above where disclosure of authentication characteristic information harms the individual's interests as is the case with the key to one's home, there are circumstances in which the disclosure of the information can benefit the individual. The latter situation involves individuals possessing characteristic information that grants them rights or qualifications to receive specific services.
In such cases, unlike the earlier situation where individuals use characteristic information to authenticate themselves, the characteristic information for granting rights or qualifications cannot be distributed to those who are entitled to such privileges, the distributed information being putatively used to verify the possession of the characteristic information. Because the disclosure of characteristic information does not harm the interests of those who possess the information, they can wrongly pass it on to third parties from whom they may receive rewards in return.
Under these circumstances, conventional public key cryptosystems do not simply utilize the above-described public key cryptgraphy techniques for authentication. Instead, the techniques have been practiced in the form of three typical methods:
(1) A first conventional method involves individuals possessing secret characteristic information that is due them, while a verifier for verifying whether any individual has specific rights or qualifications retains information about the individuals and the secret characteristic information owned by the individuals. According to this method, disclosure of the characteristic information harms individuals' interests. As such, the method is suitable for authenticating rights and qualifications granted to individuals.
(2) A second conventional method involves individuals possessing secret characteristic information that is due to them, while a verifier for verifying whether any individual has specific rights or qualifications retains public information about the individuals as well as public information corresponding to the secret characteristic information owned by the individuals. According to this method, disclosure of the characteristic information also harms individuals' interests. As such, the method is also suitable for authenticating rights and qualifications granted to individuals.
(3) A third conventional method works as follows: a party that grants rights or qualifications furnishes each of the recipients of these rights or qualifications with a signature generated by use of characteristic information owned by the privilege-granting party. A verifier verifies the signature to authenticate the demanded rights or qualifications. An example of this method is discussed by D. Chaum in “Online Cash Checks” (Advances in Cryptology EUROCRYPT '89, J. J. Quisquater, J. Vandewalle (ed.), Springer-Verlag, pp. 288-293).
This method is free from problems associated with leaks of characteristic information because those who are to prove the possession of the rights or qualifications do not retain the characteristic information.
The first conventional method above requires the verifier to retain a list of those who possess the rights or qualifications granted to them. The requirement poses a storing and administrative burden on the verifier and necessitates provision of a high-performance verification device. Because the verifying device cannot be made independently of those who grant the specific rights or qualifications, constant exchanges of information are required between the verification device and the privilege-granting party.
Since the verifier retains individuals' characteristic information, the individuals to be authenticated by this method are vulnerable to wrongful leaks of such characteristic information.
The second characteristic method above also requires the verifier to retain a list of those who possess the rights or qualifications granted to them. The requirement poses a storing and administrative burden on the verifier and necessitates provision of a high-performance verification device. Likewise, because the verifying device cannot be made independently of those who grant the specific rights or qualifications, constant exchanges of information are required between the verification device and the privilege-granting party.
Where the third conventional method above is in use, distributed signature information may be used by anyone. This requires that the signature be protected against duplicati

Affiliated with

Also associated with

Rating

Authentication method and system employing secret functions... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Authentication method and system employing secret functions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Authentication method and system employing secret functions... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3169981