Method and device for authentication

Details Method and device for authentication Method and device for authentication

1999-02-01

2003-05-20

Peeso, Thomas R. (Department: 2131)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S168000, C713S175000, C380S042000, C380S028000, C705S057000

Reexamination Certificate

active

06567916

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to information security techniques, and more particularly, to a method and a device that make it possible to hide private information itself while providing system users with prover functions based on the private information in an authentication code system that founds safety on the difficulty of an annihilator determination problem.
2. Prior Art
Decryption keys in the prior art public key cryptography, signature keys in signature, authentication keys in authentication are characteristic information for authenticating the holding of these pieces of private information. As an example, a description will be made of an authentication code system based on an authentication system proposed in “A practical zero-knowledge protocol fitted to security Microprocessor minimizing both transmission and Memory”, Advances in Cryptology EUROCRYPT '88 (Lecture Notes in Computer Science v.330), C. G. Guenther (ed.), Springer-Verlag pp. 123-128 by Guillou and Quisquater.
FIG. 1
explains the flow of thee authentication code system.
Let n be a composite number that is difficult to factor into prime factors, G be a multiplicative group (Z
Z)* of a residue class ring of rational integers modulo n, p be a prime number that does not divide Carmichael function &lgr;(n) of n, R be a space of commitments, &pgr; be a function from G to R, C be a space of challenge, S be a space of message, &phgr; be a mapping from a set-theoretic product C×S of C and S into F
p
(F
p
denotes the finite field of p-elements), I&egr;G be a public verification information, and x&egr;G satisfying Ix
p
=1 be an authentication characteristic information.
A holder of characteristic information x can send any message M&egr;S safely because pretending and tampering are prevented by performing the operation of a prover
200
as described below.
(1) Generate a random number k&egr;G and send a commitment r=&pgr;(k
p
).
(2) Compute an exponent C=&phgr;(&khgr;,M) by a given challenge &khgr; and a message M to be sent and send the message M and a response s=kx
C
.
Anyone who can know verification information I can verify the operation of the prover
200
by performing the operation of a verifier
100
as described below, and can assure himself that the prover
200
holds authentication characteristic information and a sent message is not tampered.
(1) After the commitment r is given, send the challenge &khgr; generated at random to the prover
200
.
(2) Make sure that the given message M and response s satisfy the following relation.
r
=&pgr;(
s
p
I
&phgr;(&khgr;,M)
  [Expression 2]
These techniques are developed on the assumption that holders of the above-mentioned private information do not publicize it. Therefore, this allows ciphertext that can be decrypted by only persons holding these pieces of private information, signature that can be generated by only persons holding these pieces of private information, and authentication that makes it impossible for others to impersonate the holders of these pieces of private information.
Accordingly, the above-mentioned techniques can be used in only situations in which exposure of these pieces of private information is disadvantageous to the holders of them. A typical example of such situations is found in a case where the above-mentioned private information is held by only specific individuals and is characteristic information for authenticating the individuals.
In this case, the above-mentioned characteristic information plays a role similar just, to a home lock and an individual's seal. Practically, the construction of a lock and seal in the actual life as digital information can be easily implemented as a direct application of these cryptographic methods. For example, if a home lock is configured so that it is used as a verifier in the above-mentioned Guillou-Quisquater system and is unlocked only when the verification succeeds, the holding of authentication characteristic information x will be equivalent to the holding of a home lock.
3. Problems of the Prior Art
In contrast to the above-mentioned individual's home lock case where the exposure of authentication characteristic information is disadvantageous to the individual, there exist cases where the exposure is advantageous to the exposer. These are cases where an holder of characteristic information has the right and qualification to receive specific services. In these cases, an approach cannot be taken which distributes characteristic information representing rights and qualifications to persons having the rights and qualifications and verifies that they hold the characteristic information, as is the above-mentioned case of authenticating individuals. This is because the characteristic information is passed to a third party not having the rights and qualifications since the exposure of the characteristic information is not disadvantageous to the holder of them, so that an advantage can be illegally obtained from the third person.
Hence, heretofore, three types of methods described below have been employed in place of authentication methods employing the above-mentioned public key cryptgraphic techniques without modifications.
(1) A first method is that individuals hold private characteristic information belonging to the individuals and a party to verify the holding of rights and qualifications holds individuals having the rights and qualifications and private characteristic information of the individuals. This method can be used for authentication of rights and qualifications since the leak of characteristic information would be disadvantageous to individuals.
(2) A second method is that individuals hold private characteristic information belonging to the individuals and a party to verify the holding of rights and qualifications holds individuals having the rights and qualifications and public information corresponding to private characteristic information of the individuals. This method can be used for authentication of rights and qualifications since the leak of characteristic information would be disadvantageous to individuals.
(3) A third method is that a grantor of rights and qualifications passes a signature created from characteristic information held by the grantor to a grantee of a right and qualification and a verifier authenticates the right and qualification by verifying the signature. An example of this method is found in “Online Cash Checks”, Advances in Cryptology EUROCRYPT '89 (Lecture Notes in Computer Science v. 434), J.-J. Quisquater, J. Vandewalle (ed.), Springer-Verlag, pp. 288-293 by D. Chaum.
According to this method, a problem with the leak of characteristic information will not occur since a party to prove the possession of right and qualification has no characteristic information.
However, with the first method, a verifier must hold a list of holders of right and qualification. This imposes the burden of storing and managing the list on the verifier, entailing a high-performance verification device. Also, since the verification device cannot be manufactured independently of the grantor of rights and qualifications, information must be exchanged at all times between the verification device and the grantor of rights and qualifications. Furthermore, since the verifier has individuals' characteristic information, individuals authenticated by this method will have a risk of the characteristic information being illegally leaked by the verifier.
With the second method, a verifier must hold a list of holders of rights and qualifications. This imposes the burden of storing and managing the list on the verifier, entailing a high-performance verification device. Also, since the verification device cannot be manufactured independently of the grantor of rights and qualifications, information must be exchanged at all times between the verification device and the grantor of rights and qualifications.
With the third method, since distributed signature

Affiliated with

Also associated with

Rating

Method and device for authentication does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and device for authentication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for authentication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3057349