Digital signature method and communication system
Abstract
A system for enabling verified or verifiable communications while maintaining anonymity, in which a common public parameter, such as a prime number, and a registered signature are changed, respectively, by a specifier and a signer to provide a digital signature which accompanies a message sent from the signer to a verifier.
Term
Term ended
Projected expiry passed 25 April 2017, 9.4 years ago.
- Priority
- Filed
- Published
- Projected expiry
- Today
31 claims: 13 independent, 18 dependent
- 1A digital signature method comprising:(a) a first step for generating public information based on a common public parameter and an uncommon secret parameter;(b) a second step for converting the common public parameter and the public information for use in obtaining a signature for a message;(c) a third step for generating the signature, based on a common public parameter and the uncommon secret parameter;and (d) a fourth step for confirming the relationship between the signature and the message based on the converted public information and the converted common public parameter.
- 5A digital signature method according to any of claims 1 and 2, wherein said second step further comprises converting the common public parameter and the public information into a new common public parameter and new public information, and wherein said third step is performed based on the new common public parameter, the new public informaiton and the uncommon secret parameter.
- 6An information communication system comprising:(a) means for generating a digital signature based on a digital signature method;and (b) means for confirming whether or not a given signature was generated by said generating means.
- 9An information communication system comprising:(a) specifying means for specifying a signature generating means by using a first signature method;(b) obtaining means for obtaining a base and a public key by using a second signature method;and (c) signature generating means for generating a first digital signature by using said base and said public key based on the first signature method, said signature generating means having a secret key corresponding to said public key generated by said obtaining means, wherein said digital signature verifies said signature generating means.
- 13An information communication system comprising:(a) means for generating a first digital signature based on a first digital signature method;(b) means for generating a second digital signature by using said first digital signature based on a second digital signature method;and (c) a means for confirming the authenticity of said second digital signature by using said first digital signature and said second digital signature.
- 16A computer readable memory having following program codes:(a) a first program code for generating public information based on a common public parameter and an uncommon secret parameter;(b) a second program code for converting the common public parameter and public information;(c) a third program code for generating a signature for a message, based on the common public parameter, the public information, and the uncommon secret parameter;and (d) a fourth program code for confirming the relationship between the signature and the message based on the converted public information and the converted common public parameter.
- 18A computer readable memory storing:(a) a specifying program code for specifying a signature generating means by using a first signature method;(b) a program obtaining code for obtaining a base and a public key by using a second signature method;and (c) a signature generating program code, which has a secret key corresponding to the public key generated by said program obtaining code, for generating a first digital signature by using the base and the public key based on the first signature method, wherein said digital signature verifies said signature generating program code.
- 19A digital signature method comprising:(a) a step for generating a digital signature by a group member;(b) a step for confirming, by using a public key of said group, whether or not said digital signature is generated by a group member;and (c) a step for revealing a member who generated said digital signature.
- 26A computer readable memory having following program codes:(a) a program code for generating a digital signature by a group member;(b) a program code for confirming whether or not said digital signature is generated by group member, by using a public key of said group;and (c) a program code for revealing a member who generates said digital signature.
- 27A digital signature method in which the result of an exponential operation with a first base and a secret key of a member as an exponent is a first public key of said member, said method comprising:(a) a first step for generating a second base by carrying out an exponential operation with a first base and a random number as an exponent;(b) a second step for generating a second public key by carrying out an exponential operation with a first public key and said random number as an exponent;(c) a third step for generating a first digital signature on a message by using a secret key of user;and (d) a fourth step for confirming the authenticity of said first digital signature by using said second base and said second public key.
- 30A digital signature method in which the result of an exponential operation with a first base and a secret key of a member as an exponent is a first public key of said member, said method comprising:(a) a first step for generating a second base by carrying out an exponential operation with a first base and a random number as an exponent;(b) a second step for generating a second public key by carrying out an exponential operation with a first public key and said random number as an exponent;(c) a third step for generating a first digital signature for optional information by using a secret key of user;(d) a fourth step for confirming the authenticity of said first digital signature by using said second base and said second public key;(e) a fifth step for generating a second digital signature on said second public key by a special user;and (f) a sixth step for revealing a signer based on a third signature which is generated based on said first digital signature and said second digital signature.
- 31A computer readable memory having program codes for information communication in which the result of an exponential operation with a first base and a secret key of member as exponent is a first public key of a member, said program codes including:(a) a first program code for generating a second base by carrying out an exponential operation with a first base and a random number as an exponent;(b) a second program code for generating a second public key by carrying out an exponential operation with a first public key and said random number as an exponent;(c) a third program code for generating a first digital signature for optional information by using the secret key of a user;(d) a fourth program code for confirming the authenticity of said first digital signature by using said second base and said second public key;(e) a fifth program code for generating a second digital signature on said second public key by a special user;and (f) a program-code for revealing a signer based on a third signature which is generated based on said first digital signature and said second digital signature.
Independent claims13
280 paragraphs in 4 sections, as filed
BACKGROUND OF THE INVENTION
Field of the Invention
This invention relates to a digital signature method and to an information communication system.
Related Background Art
Computers and computer networks have recently come into wide use; and because of this they can be implemented in a manner to carry out social activity. However, in this situation, there is a problem of invasion of individual privacy.
One method for carrying out social activity while protecting privacy is that of maintaining anonymity.
By using public key cryptography, a sender can send information only to an intended receiver, and the receiver can be certain of the identity of the sender.
By using a technique known as "zero knowledge proof", it is possible for one person who has information to prove to another person that he/she has certain information while the information itself remains confidential.
An information communication system which uses such technique is described in a publication by Masahiro Mambo and Eiji Okamoto entitled "A Method to Publicly Specify a Signer with Hiding Identity", (The 18th Symposium on Information Theory and its Applications - October 1995).
In this specification, the above described information communication system is referred to as the "MO System".
Also in this specification, cryptographic techniques such as "Public Key Cryptography", "Zero Knowledge Proof", "MO System" and "Digital Signature Method" will be described below in order.
Public Key Cryptography
Public Key Cryptography is an encryption method wherein each user has an individual public encryption key, or algorithm, which is publicly available, as well as an individual secret decryption key, or algorithm, which is kept secret.
Public Key Cryptography has the following features: <ul id="ul0001" list-style="none"><li>(1) The public key is different from the secret key; and key delivery is easy, since there is no need to keep the public key secret;</li><li>(2) Each user's public key is open; but his own secret key is kept secret; and</li><li>(3) It is possible to realize a digital signature function which establishes that the sender is not a pretender and that the information has not been changed.</li></ul>
The encryption algorithm for the above mentioned public key cryptography satisfies the following two conditions (in the following conditions, the encryption process for encrypting a message M by using a public key Kp is denoted as E(Kp, M); and the decryption process for decrypting the message M by using a secret key Ks is denoted as D(Ks, M)): <ul id="ul0002" list-style="none"><li>(1) The encryption process E(Kp, M) can be carried out easily by the sender by using the receiver's public key Kp and the decryption process D(Ks, M) can be carried out easily by the receiver by using his secret key Ks.</li><li>(2) It will be computationally difficult for anyone to decrypt a ciphertext C = E(Kp, M) without the receiver's secret key Ks, even though he/she knows the receiver's public key Kp and the encryption algorithm to encrypt a message M. It is also possible, with the above conditions (1) and (2), plus another condition (3), to carry out a secret communication: </li><li>(3) For any message M, E(Kp, M) can be defined and<maths id="math0001" num=""><math display="block"><mrow><mtext>D(Ks,E(Kp, M)) = M.</mtext></mrow></math><img file="EP0804003A2_D0001.tif" /></maths> In carrying out secret communication, everyone can operate the encryption process E(Kp, M), since the receiver's public key Kp has been made public. Also, only the person who knows the secret key Ks can operate the decryption process D(Ks,E(Kp, M)) to obtain the message M. Furthermore, the above conditions (1) and (2) and another condition (4) will enable authentication (digital signature). </li><li>(4) For any message M, D(Ks, M) can be defined and.<maths id="math0002" num=""><math display="block"><mrow><mtext>E (Kp,D (Ks, M)) = M.</mtext></mrow></math><img file="EP0804003A2_D0002.tif" /></maths></li></ul>
In authentication, only the person who knows the secret key Ks can operate the decryption process D(Ks, M) and obtain the result value S = D(Ks, M). If someone were to try to carry out a decryption process D(Ks, M) by using a false secret key Ks', or if someone were to change S = D(Ks, M) to S' = D(Ks, M)', the receiver would recognize that the message which the receiver received must be incorrect. This is because the receiver would check against the message M:<maths id="math0003" num=""><math display="block"><mrow><mtext>E (Kp,D (Ks', M)) ≠ M;</mtext></mrow></math><img file="EP0804003A2_D0003.tif" /></maths> and<maths id="math0004" num=""><math display="block"><mrow><mtext>E (Kp, D (Ks, M)') ≠ M.</mtext></mrow></math><img file="EP0804003A2_D0004.tif" /></maths>
Public key cryptography which can be used for both secret communication and authentication includes "RSA Cryptography", which is described in a paper written by R.L. Rivest, A. Shamir and L. Adleman, entitled "A Method of Obtaining Digital Signatures and Public Key Cryptosystems", published in Communications of ACM, vol. 21, no. 2, pp. 120-26, 1978; and "ElGamal Cryptography", which is described in a paper written by T.E. ElGamal, entitled "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms:, published in IEEE Transactions on Information Theory, vol. IT-31, no. 4, pp. 469-72, 1985.
Public key cryptography which can be used for authentication includes the "Fiat-Shamir signature scheme," which is described in a paper written by A. Fiat and A. Shamir, entitled "How to Prove Yourself; Practical Solutions of Identification and Signature Problems," published in Proc. of CRYPTO '86, 1987; and the "Schnorr signature scheme," which is described in a paper written by C.P. Schnorr, entitled "Efficient Signature Generation by Smart Cards," published in Journal of Cryptology, vol. 4, pp. 161-174, 1991.
These techniques are also described in a book by Bruce Schneier, entitled "Applied Cryptography: Protocols, Algorithms, and Source Code in C" (second edition), published by John Wiley & Sons, Inc., which includes a broader and more detailed explanation of cryptography.
Zero Knowledge Proof
Zero Knowledge Proof means that a prover proves a proposition to a verifier under the following conditions: <ul id="ul0003" list-style="none"><li>(1) Completeness: If the proof is correct, the verifier accepts it with overwhelming probability, namely, nearly 100%;</li><li>(2) Soundness: If the proof is not correct, the verifier rejects it with overwhelming probability, namely, nearly 100%.</li><li>(3) Zero Knowledge: If the proof is correct, the prover does not release any information about the secret knowledge but only the correctness of the proof.</li></ul>
Several methods of Zero Knowledge Proof have been proposed, in which a prover having a secret can prove to a verifier that the prover knows the secret without revealing any information about the secret. Since these methods are applied to identification and/or digital signature schemes, Zero Knowledge Proof is considered to be a basic technique in the field of information security.
MO System
The MO system, as applied in connection with the above described Public Key Cryptography and Zero Knowledge Proof, will be described with reference to Fig. 1. This MO system consists of a specifier; a plurality of users; a signer who is specified by a user; and a verifier who verifies the signature of the specified signer.
In Fig. 1, "Public Information" means common data in the system, "Public Database" means an issued database, and each arrow represents the sending, receiving and obtaining of data. Numbers enclosed in brackets represent the order of procedure.
Step 0 - Preparation
The following notations and definitions are used in the specification. These notations are from elementary number theory relating to integers. Let Z be the set of integers, that is {...,-2, -1, 0, 1, 2, ...}, <i>Z</i><sub><i>p</i></sub> be {0, 1, ..., p-1}, and <i>Z</i><sub><i>p</i></sub>* be the set of integers which are elements in <i>Z</i><sub><i>p</i></sub> and relatively prime to p. For any integer a and any positive integer n, there are unique integers q and r such that 0 ≤ r < n and a = qn + r. The value r = a mod n is the remainder (or residue) of the division. a = b (mod n) means that (a mod n) = (b mod n). the order of α in <i>Z</i><sub><i>p</i></sub>* is defined as the least integer i > 0 such that α<sup>i</sup> = 1 (mod p).
First, prime numbers p and q, an element a in <i>Z</i><sub><i>p</i></sub>* of order q, and a hash function h are prepared, where q| (p-1) (i.e., q divides p-1), α<sup>q</sup> = 1 (mod p), and h : <i>Z</i><sub><i>p</i></sub> X <i>Z</i> → {0, 1, ..., 2<sup>t</sup>-1}, where t is a security parameter. These numbers are registered and managed so that each user can access the numbers in a manner such that they are not changed.
A specifier i generates a public key v<sub>i</sub> and a secret key s<sub>i</sub> (v<sub>i</sub> = a<sup>{-s<sub2>i</sub2>}</sup> mod p) and registers the public key v<sub>i</sub> into a public database. A user j, who can be a signer, generates a public key v<sub>j</sub> and a secret key s<sub>j</sub>(v<sub>j</sub> = a<sup>{-s<sub2>j</sub2>}</sup> mod p) and registers the public key v<sub>j</sub> in the public database. A plurality of users and signers can exist in this system.
Step 1 - Specifying and Making Known the User
The specifier i specifies a user, namely a signer j, from several users (denoted arrow 101 in Fig. 1) and obtains z<sub>j</sub> which is converted from the public key v<sub>j</sub> of the signer j by using a random number. The specifier i obtains a signature (signature by Schnorr signature scheme) on z<sub>j</sub> (procedure (1) in Fig. 1), and registers that signature into the public database (arrow 102 in Fig. 1).
In actuality, the specifier i selects a secret random number r Z<sub>q</sub><sup>∗</sup> and obtains the following parameters, by using the following equations. The specifier i then registers the signature ((y<sub>j</sub>, e<sub>j</sub>, x<sub>j</sub>), z<sub>j</sub>):<maths id="math0005" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext> = a</mtext></mrow><mrow><mtext>r</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0005.tif" /></maths><maths id="math0006" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>r</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0006.tif" /></maths><maths id="math0007" num=""><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = h(x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>, z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) ;</mtext></mrow></math><img file="EP0804003A2_D0007.tif" /></maths> and<maths id="math0008" num=""><math display="block"><mrow><msub><mrow><mtext>y</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = r + e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> · s</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0008.tif" /></maths>
Step 2 - Picking Up the Data
The user j picks up the registered signature from the database (procedure (2) and arrow 103) and confirms whether or not the signature ((y<sub>j</sub>, e<sub>j</sub>, x<sub>j</sub>), z<sub>j</sub>) is that of the user, by checking the following equations:<maths id="math0009" num="(1);"><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = h(a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> mod p, z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0804003A2_D0009.tif" /></maths> and<maths id="math0010" num="(2)."><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p</mtext></mrow></math><img file="EP0804003A2_D0010.tif" /></maths>
Any user can confirm the above equation (1). Furthermore, the signer j can confirm the above equation (2), and can recognize that the signer j has been specified by the specifier i.
On the other hand, another user k(≠ j) can, by using his own key Sk, recognize that the equation (2) is not valid, because Sk ≠ Sj. But the user k can not recognize who is specified, since the user k will not know which user's key makes equation (2) valid.
Step 3 - Generation of the Signature
The signer j makes his signature on a message M based on the following formulas:<maths id="math0011" num=""><math display="block"><mrow><mtext>x1= a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0011.tif" /></maths> and<maths id="math0012" num=""><math display="block"><mrow><msub><mrow><mtext>x2 = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0012.tif" /></maths>
Then the signer j obtains the following parameters e' and y as follows:<maths id="math0013" num=""><math display="block"><mrow><mtext>e' = h (x2, m) ;</mtext></mrow></math><img file="EP0804003A2_D0013.tif" /></maths> and<maths id="math0014" num=""><math display="block"><mrow><msub><mrow><mtext>y = - (r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>-e') s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> mod q.</mtext></mrow></math><img file="EP0804003A2_D0014.tif" /></maths>
Next, the signer j sends the parameter ((y<sub>j</sub>,e<sub>j</sub>,x<sub>j</sub>),z<sub>j</sub>, (y,e',x1),m) as his signature to an intended person (procedure (3) and arrow 104).
Step 4 - Verification of the Signature
The verifier, in the first instance, confirms the above equation (1) as well as the following equation:<maths id="math0015" num=""><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = h(z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>, a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p).</mtext></mrow></math><img file="EP0804003A2_D0015.tif" /></maths>
The verifier then confirms the following equation:<maths id="math0016" num=""><math display="block"><mrow><mtext>e' = h(m,x2)</mtext></mrow></math><img file="EP0804003A2_D0016.tif" /></maths><maths id="math0017" num="(3)"><math display="block"><mrow><msup><mrow><mtext>x2 = a</mtext></mrow><mrow><mtext>y</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{e'}</mtext></mrow></msup><mtext> mod p</mtext></mrow></math><img file="EP0804003A2_D0017.tif" /></maths>
The signer j then executes Zero Knowledge Proof with the verifier for proving the following equation (procedure (5) and arrow 105 in Fig. 1):<maths id="math0018" num=""><math display="block"><mrow><msub><mrow><mtext>log</mtext></mrow><mrow><mtext>xj</mtext></mrow></msub><msub><mrow><mtext> z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = log</mtext></mrow><mrow><mtext>x1</mtext></mrow></msub><msub><mrow><mtext> x</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> = -S</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>.</mtext></mrow></math><img file="EP0804003A2_D0018.tif" /></maths>
If the Zero Knowledge Proof is correct, the verifier can conclude that the signature on the message M was signed by the signer j.
In the above MO system, it is asserted that a specifier i specifies a signer j, and the specified signer j can generate his digital signature anonymously. In addition, the verifier who receives this signature will recognize that a signer j who was specified by the specifier i has generated the signature, but the verifier will not know the specific identity of the signer j.
Because of this feature, the MO system is especially applicable for the provision of welfare services and for audience rating investigations. In these cases, the occurrence of a request for a welfare service or the submission of an audience reaction is publicly verified by everyone. Nevertheless, the person making the welfare request or submitting the audience reaction remains anonymous. These statements are asserted in the publication by M. Mambo and E. Okamoto entitled "A Method to Publicly Specify a Signer With Hiding Identity", cited above.
Digital Signature Method
A description of the Digital Signature Method in relation to Public Key Cryptography and Zero Knowledge Proof is given in a paper entitled "Group Signatures" by D. Chaum and E. van Heyst, Proc. of EUROCRYPT '91, pp. 257-65 (1991). This method, which is referred to as "group signature", has the following features: <ul id="ul0004" list-style="none"><li>(1) Only members of the group can sign messages;</li><li>(2) The receiver of the signature can verify that it is a valid signature of that group, but cannot discover which member of the group made it; and</li><li>(3) In the case of a dispute later on, the signature can be "opened" (with or without the help of the group members) to reveal the identity of the signer.</li></ul>
The above-mentioned group signature is applicable to a bidding, or tender, system. In the tender system, the set of bidders forms a group, and each member makes a group signature on a message indicating the price, etc. The identity of the highest bidder is revealed but the remaining bidders are anonymous.
The known MO system has been subject to the following problems: <ul id="ul0005" list-style="none"><li>1. The MO system requires the public key of the specified signer when a signature is verified, although the signer made the signature anonymously. That is, the anonymity of the signer is not completely preserved. Furthermore, once the verifier confirms the signature, a plurality of communications between the verifier and the signer are still required; and</li><li>(2) The MO system is based on the assumption that the system is implemented over a network which can hide the identity of a sender/receiver who has a plurality of communications. Such a network is more expensive than a simple network which can hide the identity of a sender who makes only one transmission of a message.</li></ul>
There are four kinds of group signature methods in the above mentioned paper by Chaum et al.; one of them requires a special authority to open a group signature and others do not; it is easy to add a new member in another of the four, while it is not in the others; and each method has the same problem, namely, that the size of the public key of a group is linear in relation to the number of members. In another group signature method, which is described in a paper entitled "A Practical Group Signature" by S.J. Park, I.S. Lee and D.H. Won, published in Proc. of the 1995 Japan-Korea Workshop on Information Security and Cryptology, IV-3.00127 and pp. 127-33 (1995), the size of the public key of a group does not grow linearly with the number of members. In this method it is easy to add new members. However, this method always requires a special authority in order to open the signature.
SUMMARY OF THE INVENTION
This invention is made in this consideration of the above circumstances; and it is an object of the invention to provide a digital signature method and information communication system which can solve the above problems.
According to one aspect of the invention, there is provided a digital signature method which comprises a first step for generating public information based on a common public parameter and an uncommon secret parameter, a second step for converting the common public parameter and the public information, a third step for making a signature based on the common public parameter, the public information, and the uncommon secret parameter, and a fourth step for confirming the relationship between the signature and the corresponding message based on the converted public information and the converted common public parameter.
According to another aspect of the invention, there is provided an information communication system which comprises a means for making or generating a digital signature based on a digital signature method and a means for confirming whether or not a signature was generated by the generating means.
According to another aspect of the invention, there is provided an information communication system which comprises a specifying means for specifying a signature generating means by means of a first signature method, a means for obtaining a base and a public key by using a second signature method, and a generating means for making or generating a digital signature by using the base and the public key based on the first signature method, wherein the digital signature proves the signature generating means which has a secret key corresponding to the public key generated by the means for obtaining the base and the public key.
According to another aspect of the invention, there is provided an information communication system which comprises a means for generating a first digital signature based on a first digital signature method, a means for generating a second digital signature by using the first digital signature based on a second digital signature method, and a means for confirming the authenticity of the second digital signature by using the first digital signature and the second digital signature.
According to another aspect of the invention, there is provided a computer readable memory having the following program codes: a first program code for generating public information based on a common public parameter and an uncommon secret parameter; a second program code for converting the common public parameter and public information; a third program code for generating a signature based on the common public parameter, the public information, and the uncommon secret parameter; and a fourth program code for confirming the relationship between the signature and the corresponding message based on the converted public information and the converted common public parameter.
According to another aspect of the invention, there is provided a computer readable memory having following program codes: a specifying program code for specifying a signature generating means by using a first signature method; a base and public key obtaining program code for obtaining a base and a public key by using a second signature method; and a digital signature generating program code for generating a digital signature by using the base and the public key based on the first signature method, wherein the digital signature proves the signature generating program code which has a secret key corresponding to the public key generated by the base and public key obtaining program code.
According to another aspect of the invention, there is provided a digital signature method which comprises a step for generating a digital signature by a group member, a step for confirming, by using a public key of the group, whether or not the digital signature has been generated by group member, and a program code for revealing a member who has generated the digital signature.
According to another aspect of the invention, there is provided a computer readable memory having the following program codes: a program code for generating a digital signature by a group member; a program code for confirming, by using a public key of the group, whether or not the digital signature was generated by group member; and a program code for revealing the member who generated the digital signature.
According to another aspect of the invention, there is provided a digital signature method in which the public key of a member comprises the result of an exponential operation with a base and the secret key of the member as an exponent. This method comprises: a first step for generating a second base by performing a first exponential operation with a first base and a random number as an exponent; a second step for generating a second public key by performing a second exponential operation with a first public key and the random number as an exponent; a third step for generating a first digital signature on a message by using the secret key of a user; and a fourth step for confirming the authenticity of the first digital signature by using the second base and the second public key.
According to another aspect of the invention, there is provided a further digital signature method in which the public key of a member comprises the result of an exponential operation with a base and the secret key of the member as an exponent. This method comprises: a first step for generating a second base by performing an exponential operation with a first base and a random number as an exponent; a second step for generating a second public key by performing an exponential operation with a first public key and the random number as an exponent; a third step for generating a first digital signature on a message by using a secret key of a user; a fourth step for confirming the authenticity of the first digital signature by using the second base and the second public key; a fifth step for generating a second digital signature corresponding to the second public key by a special user; and a sixth step for revealing a signer based on a third signature which is generated based on the first and second digital signatures.
According to another aspect of the invention, there is provided a computer readable memory having program code for information communication in which a first public key of a member is the result of an exponential operation with a first base and an exponent comprising a secret key of the member. The memory contains the following program codes: a first program code for generating a second base by performing an exponential operation with the first base and a random number as an exponent; a second program code for generating a second public key by performing an exponential operation with the first public key and the random number as an exponent; a third program code for making a first digital signature on a message by using a secret key of a user, a fourth program code for confirming the authenticity of the first digital signature by using the second base and the second public key; a fifth program code for making a second digital signature corresponding to the second public key by a special user; and a sixth program code for revealing a signer based on a third signature which is made based on the first and second digital signatures.
BRIEF DESCRIPTION OF THE DRAWINGS
<ul id="ul0006" list-style="none"><li>Fig. 1 is a block diagram showing the MO system;</li><li>Fig. 2 is a block diagram showing an embodiment of a communication system according to the present invention;</li><li>Fig. 3 is a flow chart of digital signature procedure used in the present invention;</li><li>Fig. 4 is a memory map of the embodiment of Fig. 2;</li><li>Fig. 5 is a second memory map of the embodiment of Fig. 2;</li><li>Fig. 6 is a block diagram showing another embodiment of the present invention;</li><li>Fig. 7 is a flow chart for the embodiment of Fig. 6;</li><li>Fig. 8 is a block diagram showing a signature system according to the present invention;</li><li>Fig. 9 is a block diagram showing a group signature system according to the present invention;</li><li>Fig. 10 is a flow chart for the system shown in Fig. 9;</li><li>Fig. 11 is a memory map of the embodiment of Fig. 9; and</li><li>Fig. 12 is a second memory map of the embodiment of Fig. 9;</li></ul>
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Several embodiments of this invention will be described hereinbelow with reference to the Figures.
The digital signature of the first embodiment is based on discrete logarithms. In this embodiment a secret key is not changed but a public key and the base are changed by an exponential operation which uses a random number as an exponent.
In this embodiment an ordinary (non-interactive) digital signature scheme is used, whereas a digital signature scheme based on Zero Knowledge Proof is used in the MO system.
The information communication system of this embodiment, which has above described features, is able to maintain the anonymity of a signer, since a verifier can verify the signer's signature without using the public key of the signer.
In this embodiment, the number of required communications and operations which accompany each communication can be decreased, since the verifier can verify the signature of the signer without using Zero Knowledge Proof in which a plurality of communications is needed. All that is needed is one communication to send the signer's signature to the verifier.
In addition, this system can operate in a simple and inexpensive network.
First Embodiment
Fig. 2 shows an information communication system as applied for carrying out a digital signature method according to a first embodiment of the invention. Fig. 3 is a flow chart which shows the operations performed in connection with the digital signature method. The first embodiment will be described with reference to Fig. 2 and Fig. 3.
Step 0 - Preparation
At first, prime numbers p and q such that q|(p-1), an element a in <i>Z</i><sub><i>p</i></sub>* of order a, and a one-way hash function h : <i>Z</i><sub><i>p</i></sub> × <i>Z</i> → {0, ..., 2<sup>(t-1)</sup>)}, are prepared. These numbers, which comprise a common public parameter, are registered and managed so that every user can access them and so that they cannot be changed.
The specifier i generates a public key v<sub>i</sub> and a secret key s<sub>i</sub>(v<sub>i</sub> = a<sup>{-s <sub2>i</sub2> }</sup>mod p) and registers the public key v<sub>i</sub> in the public database. The user j, who can be a signer, generates a public key v<sub>j</sub> and a secret key s<sub>j</sub>(v<sub>j</sub> = a<sup>{-s<sub2>j</sub2>}</sup> mod p) ; and registers the public key v<sub>j</sub> into a public database. A plurality of users and signers can exist in this system.
Step 1 - Specifying a User
The specifier i specifies a user (signer) j, from the several users (arrow 201 in Fig. 2); and obtains z<sub>j</sub> which is converted from the public key v<sub>j</sub> of the signer j by using a random number. The specifier then gets a signature, for example by Schnorr signature scheme (procedure (1) in Fig. 2), and registers that signature as public information into the public database (arrow 202 in Fig. 2) .
More concretely, the specifier i selects a secret random number r from Zq‡ and obtains the following parameters by using the following equation, and registers the signature ((y<sub>j</sub>, e<sub>j</sub>), z<sub>j</sub>) :<maths id="math0019" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0019.tif" /></maths><maths id="math0020" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0020.tif" /></maths><maths id="math0021" num=""><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = h(x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>, z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>);</mtext></mrow></math><img file="EP0804003A2_D0021.tif" /></maths> and<maths id="math0022" num=""><math display="block"><mrow><msub><mrow><mtext>y</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> + e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> · s</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0022.tif" /></maths>
Step 2 - Picking Up the Data
The user (signer) j confirms whether or not the signature ((y<sub>j</sub>,e<sub>j</sub>),z<sub>j</sub>) is for the user based on the database by checking following equations (procedure (2), arrow 203 in Fig. 2):<maths id="math0023" num="(4); "><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = h(a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> mod p, z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0804003A2_D0023.tif" /></maths> and<maths id="math0024" num="(5)."><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = (a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p</mtext></mrow></math><img file="EP0804003A2_D0024.tif" /></maths>
Thereafter, a<sup>{y<sub2>j</sub2>}</sup> · (v<sub>i</sub>)<sup>{e<sub2>j</sub2>}</sup> mod p will be denoted as x<sub>j</sub>, since the following equation is valid:<maths id="math0025" num=""><math display="block"><mrow><mtext>a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> mod p = x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>.</mtext></mrow></math><img file="EP0804003A2_D0025.tif" /></maths>
Any user can confirm the above equation (4).
Furthermore, the signer i can confirm the above equation (5); and recognize that signer i has been specified as the signer.
On the other hand, another signer can recognize that the equation (5) is not valid by using his own key. However, such other signer can not recognize who has been specified, since the other signer does not know which key of user made the equation (5) valid.
Step (3) - Generating the Signature
The signer j makes his signature on a message m(j) based on the following formulas; and the signer selects a secret random number (j) and carries out the following equations:<maths id="math0026" num=""><math display="block"><mrow><msub><mrow><mtext>x(</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>) = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0026.tif" /></maths><maths id="math0027" num=""><math display="block"><mrow><mtext>e(j) = h(x(j), m(j));</mtext></mrow></math><img file="EP0804003A2_D0027.tif" /></maths> and<maths id="math0028" num=""><math display="block"><mrow><msub><mrow><mtext>y(j) = r(j) + e(j) · s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> mod q.</mtext></mrow></math><img file="EP0804003A2_D0028.tif" /></maths>
Next, the signer j sends the parameter (((y<sub>j</sub>, e<sub>j</sub>), z<sub>j</sub>), ((y(j), e(j), m(j))) as his signature to an intended person (procedure (3) and arrow 204).
Step 4 - Verifying the Signature
The verifier confirms the above equation (4) as well as the following equation (procedure (4) in Fig. 2):<maths id="math0029" num=""><math display="block"><mrow><msub><mrow><mtext>e(j) = h(x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>y(j)</mtext></mrow></msup><msub><mrow><mtext> · z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>e(j)</mtext></mrow></msup><mtext> mod p, m(j)).</mtext></mrow></math><img file="EP0804003A2_D0029.tif" /></maths>
If the above is correct, the verifier can conclude that the signature for the message m(j) was signed by the signer who was specified by the specifier i.
Here, we explain the notion of public key certificates. A trusted user, called the certification authority (CA), makes a signature on a message indicating the public key or a user, the identity of the user, and all the validation date, etc. The digital signatures by CA are called "public key certificates." If one needs to confirm a public key of a user, then one can verify the authenticity by confirming the public key certificate by means of the public key of CA.
In this embodiment the digital signature made by the specifier on a (converted) public key of user is considered as a kind of public key certificate. The difference from the ordinary public key certificate is the anonymity of the certificate user.
It will be appreciated that the signature ((y<sub>j</sub>, e<sub>j</sub>), z<sub>j</sub>) on z<sub>j</sub>, whish is converted from v<sub>j</sub> of the public key of the signer j, is called an anonymous public key certificate. The notion and precise description of anonymous public key certificates are set out later.
In this embodiment, each procedure of the signer, specifier and verifier will be carried out in the same apparatus which has a capability for operation and communication like a personal computer. Also, communications between the signer, the specifier and the verifier can be carried out by using a public database and a service for anonymous communication on a network such as the Internet.
The information communication system with digital signature of this embodiment will be carried out by the above described information processing apparatus which is capable of executing each of the above steps.
The network used with this embodiment does not have to be the Internet. A so called "intranet" can be used as well.
In this embodiment, the anonymous public key certificate may be sent directly from the specifier to the signer, so long as it is not necessary for each user to confirm the specifier's specification.
As mentioned above, since the information communication system of this embodiment does not need the public key of the signer, the anonymity of the signer can be maintained.
Also, since a plurality of communications between the verifier and signer are not required, the system can be implemented over a simple and less expensive network then that of MO system. Therefore the proposed system can be constructed at low cost.
In addition, since the number of communications and operations is decreased, it becomes easier for the user.
Second Embodiment
The second embodiment of this invention, which is shown in Figs. 6 and 7, will now be described.
Those parts of this embodiment which are the same as in the first embodiment will be omitted from the following description.
Instead of the Schnorr signature scheme, the digital signature used in this embodiment will be ElGamal cryptography, which is described in "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" by T.E. ElGamal <u>(IEEE Transaction Theory,</u> vol. IT-31, no. 4, pp. 469-72, 1985).
Step 0 - Preparation
This step is the same as step 0 of the first embodiment.
Step 1 - Specifying a User
This step is the same as Step 1 of the first embodiment.
Step 2 - Picking Up the Data
This step is the same as step 2 of the first embodiment.
Step 3 - Generating the Signature
A signer j generates his signature for a message m(j) based on the following formulas. Also, the signer j selects a secret random number k(j) from Zq‡ and carries out the following equations:<maths id="math0030" num=""><math display="block"><mrow><msub><mrow><mtext>r(j) = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{k(j)}</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0030.tif" /></maths> and<maths id="math0031" num=""><math display="block"><mrow><msub><mrow><mtext>f(j) = {m(j) + s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext> · r(j)} · k (j)</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext> mod (p - 1).</mtext></mrow></math><img file="EP0804003A2_D0031.tif" /></maths>
Next, the signer j sends the parameter (((y<sub>j</sub>,e<sub>j</sub>),z<sub>j</sub>), ((r(j), f(j)),m(j))) as his signature to a specified person.
Step 4 - Verification of the Signature
The verifier confirms the above equation (4) and the following equation:<maths id="math0032" num=""><math display="block"><mrow><msub><mrow><mtext>(x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>) </mtext></mrow><mrow><mtext>{m(j)}</mtext></mrow></msup><msub><mrow><mtext> ≡ (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{r(j)}</mtext></mrow></msup><msup><mrow><mtext> · r(j)</mtext></mrow><mrow><mtext>{f(j)}</mtext></mrow></msup><mtext> (mod p).</mtext></mrow></math><img file="EP0804003A2_D0032.tif" /></maths>
If the above equation is correct, the verifier can conclude that the signature for the message m(j) was signed by a signer who was specified by the specifier i.
Third Embodiment
The third embodiment of this invention will be described next.
Those parts of this embodiment which are the same as the first embodiment will be omitted from the following description.
DSA, which is proposed as the standard of digital signature, and which is described in Bruce Schneier, "Applied Cryptography: Protocols, Algorithms, and Source Code", second edition, John Wiley & Sons, Inc., is used for the digital signature in this embodiment.
In this embodiment, p,q,x<sub>j</sub>,z<sub>j</sub> are used as public key, and s<sub>j</sub> is used as secret key.
Step 0 - Preparation
This step is the same as step 0 of the first embodiment.
Step 1 - Specifying and Making Known the User
This step is the same as step 1 of the first embodiment.
Step 2 - Picking Up the Data
This step is the same as step 2 of the first embodiment.
Step 3 - Generation of the Signature
The signer makes his signature on a message m(j) based on the following formulas. The signer j selects a secret random number k(j) from Zq‡; and carries out the following equations:<maths id="math0033" num=""><math display="block"><mrow><msub><mrow><mtext>r(j) = ((x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{k(j)}</mtext></mrow></msup><mtext> mod p) mod q;</mtext></mrow></math><img file="EP0804003A2_D0033.tif" /></maths> and<maths id="math0034" num=""><math display="block"><mrow><msup><mrow><mtext>f(j) = k(j)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><msub><mrow><mtext> · (h(m(j))-s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> · r(j)) mod q.</mtext></mrow></math><img file="EP0804003A2_D0034.tif" /></maths>
Next, the signer j sends the parameter (((y<sub>j</sub>,e<sub>j</sub>),z<sub>j</sub>), ((r(j), f(j),m(j))) as his signature to a specified person.
Step 4 - Verification of the Signature
The verifier confirms the above equation (4), 0 < r(j) < q, 0 < f(j) < q and the following equations:<maths id="math0035" num=""><math display="block"><mrow><msup><mrow><mtext>w = f(j)</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext> mod q;</mtext></mrow></math><img file="EP0804003A2_D0035.tif" /></maths><maths id="math0036" num=""><math display="block"><mrow><mtext>u1 = h(m(j)) · w mod q;</mtext></mrow></math><img file="EP0804003A2_D0036.tif" /></maths><maths id="math0037" num=""><math display="block"><mrow><mtext>u2 = r(j) · w mod q;</mtext></mrow></math><img file="EP0804003A2_D0037.tif" /></maths> and<maths id="math0038" num=""><math display="block"><mrow><msub><mrow><mtext>v = ((x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{u1}</mtext></mrow></msup><msub><mrow><mtext> · (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{u2}</mtext></mrow></msup><mtext> mod p) mod q.</mtext></mrow></math><img file="EP0804003A2_D0038.tif" /></maths>
If the above equations are correct, the verifier can conclude that the signature on the message m(j) has been made by a signer who was specified by the specifier i.
Fourth Embodiment
The fourth embodiment of this invention will now be described.
Those parts of this embodiment which are the same as in the previous embodiment will be omitted from the following description.
In this embodiment, the above mentioned ElGamal cryptography is used for generating an anonymnous public key certificate of z<sub>j</sub> instead of the Schnorr signature scheme.
Nevertheless, it should be noted that the following equations must be valid:<maths id="math0039" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0039.tif" /></maths> and<maths id="math0040" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0040.tif" /></maths>
More concretely, the specifier i selects a random number r<sub>j</sub> from Z<sub>q</sub>* and carries out the following equations:<maths id="math0041" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0041.tif" /></maths><maths id="math0042" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>= (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0042.tif" /></maths> and<maths id="math0043" num=""><math display="block"><mrow><msub><mrow><mtext>f</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> + s</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> · x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>) · (r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><mtext> mod (p-1)</mtext></mrow></math><img file="EP0804003A2_D0043.tif" /></maths>
Also in this embodiment, the parameter ((x<sub>j</sub>,f<sub>j</sub>),z<sub>j</sub>) is the certification of the public key.
The authenticity of the anonymous public key certifice is proved by confirming the following equations:<maths id="math0044" num=""><math display="block"><mrow><mtext>a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{z </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> ≡ (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{x </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{f</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>}</mtext></mrow></msup><mtext> (mod p);</mtext></mrow></math><img file="EP0804003A2_D0044.tif" /></maths> and<maths id="math0045" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0045.tif" /></maths>
Fifth Embodiment
The fifth embodiment of this invention will be described next.
Those parts of this embodiment which are the same as in the previous embodiment will be omitted from the following description.
In this embodiment, the above described DSA is used for generating an anonymous public key certificate of z<sub>j</sub> instead of the Schnorr signature scheme and the ElGamal cryptography.
Nevertheless, it should be noted that the following equations are valid:<maths id="math0046" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0046.tif" /></maths> and<maths id="math0047" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0047.tif" /></maths>
More concretely, the specifier i selects a secret random number r<sub>j</sub> from Z<sub>q</sub>* and carries out the following equations:<maths id="math0048" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0048.tif" /></maths><maths id="math0049" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0049.tif" /></maths> and<maths id="math0050" num=""><math display="block"><mrow><msub><mrow><mtext>f</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><msub><mrow><mtext> · (h(z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>)-s</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> · x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) mod q.</mtext></mrow></math><img file="EP0804003A2_D0050.tif" /></maths>
Again in this embodiment, the parameter ((x<sub>j</sub>,f<sub>j</sub>),z<sub>j</sub>) is the anonymous public key certificate.
The authenticity of certification of the public key will be proved by confirming 0 < x<sub>j</sub> < p, 0 < f<sub>j</sub> < q and the following equations:<maths id="math0051" num=""><math display="block"><mrow><msub><mrow><mtext>w = (f</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><mtext> mod q;</mtext></mrow></math><img file="EP0804003A2_D0051.tif" /></maths><maths id="math0052" num=""><math display="block"><mrow><msub><mrow><mtext>u1 = h(z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) · w mod q;</mtext></mrow></math><img file="EP0804003A2_D0052.tif" /></maths><maths id="math0053" num=""><math display="block"><mrow><msub><mrow><mtext>u2 = x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> · w mod q;</mtext></mrow></math><img file="EP0804003A2_D0053.tif" /></maths> and<maths id="math0054" num=""><math display="block"><mrow><msup><mrow><mtext>v = a</mtext></mrow><mrow><mtext>{u1}</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{u2}</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0054.tif" /></maths>
The authenticity of the anonymous public key certificate is proved by confirming the following equation:<maths id="math0055" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0055.tif" /></maths>
As described above, this invention provides a digital signature method which maintains the anonymity of the signer.
In a system using this invention, the number of communications is decreased; and correspondingly, the number of operations is also decreased.
This system can be utilized on a simple and inexpensive network which only requires maintaining anonymity with respect to one transmission of a message; and the system does not require an expensive network which requires maintaining anonymity with respect to many transmissions of message(s) from/to a user.
The Sixth Embodiment
The digital signature method of this embodiment is based on anonymous public key certificates. The method is used for group signatures. In this embodiment, the specifier is a trusted authority ZA, specified signers are members, and a digital signature based on an anonymous public key certificate is a group signature.
The anonymous public key certificates have the following features: <ul id="ul0007" list-style="none"><li>1. The certification authority (CA) converts, using a random number, the common public parameter and the public key of the certificate user. CA makes a signature on the converted public key.</li><li>2. Since the same relationship holds between the converted public key and the original public key with respect to the secret key, the certificate user can make a signature on a message using the anonymous public key certificates and the secret key.</li><li>3. The receiver who received the anonymous public key certificates and the signature by the certificate user can verify that the converted parameter and public key are certified by CA. Using the certified parameter and public key, the verifier also verify that the digital signature on the message is genuine.</li><li>4. We call the anonymous public key certificates by CA, together with the signature by the corresponding user, an anonymous signature because it is hard to identify the signer from the signature.</li></ul>
As mentioned above, the specifier is the authority ZA and the user who is specified by the specifier (i.e., the signer) is the member. Thus the public key of the specifier is the public key of the group, and the anonymous signature by the signer is the group signature.
Next, the method to reveal a signer will be described.
The authority ZA can record the relationship between the members and the certificate. Therefore, the authority ZA can identify the signer of a group signature.
On the other hand, it is possible to confirm whether or not a particular member is the signer by checking the equality of the secret key which is used for the group signature and the secret keys of each of the members. Accordingly, it is possible to obtain the identity of the signer by requesting the proof of inequality of each member. This is because it is possible to prove that the secret key of each member who is not the signer is different from the secret key which used for the group signature.
Anonymous public key certificates will now be described, followed by a description of the group signature with which it is utilized.
Anonymous Public Key Certificates
Anonymous public key certificates will be described with reference to Figs. 6 and 7.
The system of anonymous public key certificates consists of a certifiction authority, a plurality of users, a certificate user who utilizes an anonyumouis public key certificate and a verifier who verifies the signature of the certificate user.
This system is utilized with a network over which identifying the sender or the receiver of communictaion is difficult. (In this specification, such a network will be called an "anonymous communication network".)
In Fig. 6, the term "Public Information" means a common database in the system and the term "Public Database" means an issued database. The arrows in Fig. 6 represent the sending, receiving and obtaining of data and the numbers enclosed in brackets represent steps in an order of procedure. The term "user" refers to the particular one of the users who utilizes an anonymous public key certificate. The term "verifier" refers to the person who verifies the signature made by the user.
Step 0 - Preparation
At first, prime numbers p and q such that q|(p-1), an element a of <i>Z</i><sub><i>p</i></sub>* of order q (i.e., a<sup>q</sup> ≡ 1(mod p)) and a one-way hash function h : <i>Z</i><sub><i>p</i></sub> × <i>Z</i> → {0, ..., 2<sup>(t-1)</sup>}, are prepared. These numbers are registered and managed so that every user can access them and so that they cannot be changed.
The certification authority i generates a public key v<sub>i</sub> and a secret key s<sub>i</sub>(v<sub>i</sub> = a<sup>{-s</sup><sub>i</sub><sup>}</sup> mod p) and registers the public key v<sub>i</sub> into the public database together with the identity. The user j, who can be a signer, generates a public key v<sub>j</sub> and a secret key s<sub>j</sub>(v<sub>j</sub> = a<sup>{-s</sup><sub>j</sub><sup>}</sup> mod p) ; and registers the public key v<sub>j</sub> into a public database together with the identity. A plurality of users and signers can exist in this system.
Step 1 - Issue of Certificate
The certification authority i specifies a user (signer) j, from the several users (arrow 101 in Fig. 12); and obtains z<sub>j</sub> which is converted from the public key v<sub>j</sub> of the signer j by using a random number. The certification authority then makes a signature on that, for example using the Schnorr signature scheme (procedure (1) in Fig. 1), and sends that signature to the user j (arrow 102 in Fig. 1).
More concretely, the certification authority i selects a secret random number r from Z<sub>q</sub>* and obtains the following parameters by using the following equation, and registers the signature ((y<sub>j</sub>, e<sub>j</sub>, x<sub>j</sub>), z<sub>j</sub>):<maths id="math0056" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0056.tif" /></maths><maths id="math0057" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0057.tif" /></maths><maths id="math0058" num=""><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = h (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> , z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) ;</mtext></mrow></math><img file="EP0804003A2_D0058.tif" /></maths> and<maths id="math0059" num=""><math display="block"><mrow><msub><mrow><mtext>y</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> + e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> · s</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0059.tif" /></maths>
Step 2 - Generation of the Signature
The user j receives the signature ((y<sub>j</sub>, e<sub>j</sub>), z<sub>j</sub>) and confirms the following equations:<maths id="math0060" num="(6);"><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = h(a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>) </mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> mod p,z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0804003A2_D0060.tif" /></maths> and<maths id="math0061" num="(7)."><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = (a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>) </mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p) </mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p</mtext></mrow></math><img file="EP0804003A2_D0061.tif" /></maths>
The user j makes his signature on the message m(j) based on the following formulas; and the user j selects a secret random number (j) and carries out the following equations:<maths id="math0062" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext>· (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0062.tif" /></maths><maths id="math0063" num=""><math display="block"><mrow><msub><mrow><mtext>x(j) = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>) </mtext></mrow><mrow><mtext>{r(j)}</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0063.tif" /></maths><maths id="math0064" num=""><math display="block"><mrow><mtext>e(j) = h(x(j),m(j));</mtext></mrow></math><img file="EP0804003A2_D0064.tif" /></maths> and<maths id="math0065" num=""><math display="block"><mrow><msub><mrow><mtext>y(j) = r(j) + e(j) · s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> mod q.</mtext></mrow></math><img file="EP0804003A2_D0065.tif" /></maths>
Next the user j sends the parameter ((y<sub>j</sub>,e<sub>j</sub>),z<sub>j</sub>), ((y(j),e(j)),m(j))) as his signature to an intended person (procedure (3) and arrow 103 in Fig. 1).
Step 3 - Verification of the Signature
The verifier first confirms the above equation (6) and the following equation (procedure (4) in Fig. 1):<maths id="math0066" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0066.tif" /></maths> and<maths id="math0067" num=""><math display="block"><mrow><msub><mrow><mtext>e(j) = h ((x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{y(j)}</mtext></mrow></msup><msub><mrow><mtext> · (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>) </mtext></mrow><mrow><mtext>{e(j)}</mtext></mrow></msup><mtext> mod p,m (j)) .</mtext></mrow></math><img file="EP0804003A2_D0067.tif" /></maths>
If the above is correct, the verifier can conclude that the signature on the message m(j) is that of a user j who received an anonymous public key certificate from the certification authority.
The above described anonymous public key certificates have following features: <ul id="ul0008" list-style="none"><li>(1) Only the certification authority can specify the user j, and the proof of specification is the certificate (digital signature generated by the certification authority i);</li><li>(2) The specified signer can anonymously generate the signature by using the certificate and the secret key of the signer;</li><li>(3) The receiver can confirm the authenticity of the anonymous signature by using the public key of the specifier i; and</li><li>(4) It will be very difficult to distinguish the signer j by use of the anonymous signature, and forgery of the anonymous signature is very difficult.</li></ul>
Group Signature Based on Anonymous Public Key Certificate
The system of group signature based on anonymous public key certificate is shown in Fig. 8. In this system a plurality of users can anonymously communicate each other over an anonymous communication network.
In this system there is a public database which can be accessed by the trusted authority ZA and users j, k, v. The public keys of each of the users and the common parameter are registered with the database. This database is properly managed so as to prevent unfair action such as alteration.
In Fig. 8 the group public key is denoted as v<sub>{ZA}</sub>. The group consists of members including users j and k. The users j, k, obtain anonymous public key certificates (y<sub>j</sub>, e<sub>j</sub>, z<sub>j</sub>) (y<sub>k</sub>, e<sub>k</sub>, z<sub>k</sub>) which are issued by the authority ZA, respectively, and they each generate a signature part (e.g., (y(j), e(j), m) for user j) based on their own anonymous public key certificates. The users send the group signature ((y<sub>j</sub>, e<sub>j</sub>, z<sub>j</sub>), y(j), e(j), z(j)) to another user v over the anonymous communication network.
The user v verifies the anonymous public key certificate (y<sub>j</sub>, e<sub>j</sub>, z<sub>j</sub>) by using the group public key V<sub>{ZA}</sub>, and obtains certified values. The user v can confirm the authenticity of the group signature by verifying y(j), e(j), z(j) with these values.
Next a concrete embodiment will be described with reference to Figs. 9 and 10.
Fig. 9 shows the system which is applied to group signature based on anonymous public key certification.
Fig. 10 shows the flow chart of a procedure related to the method of group signature. Figs. 11 and 12 are memory maps for the system of Fig. 9. In this system, the user j who receives an anonymous public key certificate from the authority ZA generates the group signature, and the verifier, who receives the group signature, confirms it as the group signature.
Step 0 - Preparation
This is the same as Step 0 previously described.
Step 1 - Issue of Certificates to Members
The authority authorizes the user as a member of the group; and obtains z<sub>j</sub> which is converted from the public key v<sub>j</sub> of the signer j by using a random number r<sub>j</sub>. The authority also makes the signature using the Schnorr signature scheme (procedure (1) in Fig. 9) and sends the signature directly to the user j (procedure (2) and arrow 402 in Fig. 9).
In a concrete example, the authority ZA selects a secret random number r from Z<sub>q</sub>* and obtains the following parameters by using the following equation, and sends the certificate ((y<sub>j</sub>, z<sub>j</sub>) :<maths id="math0068" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0068.tif" /></maths><maths id="math0069" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0069.tif" /></maths><maths id="math0070" num=""><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = h (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> , z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) ;</mtext></mrow></math><img file="EP0804003A2_D0070.tif" /></maths> and<maths id="math0071" num=""><math display="block"><mrow><msub><mrow><mtext>y</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> + e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> · s{ZA} mod q.</mtext></mrow></math><img file="EP0804003A2_D0071.tif" /></maths>
Step 2 - Generation of the Group Signature
The user j receives the signature (y<sub>j</sub>, e<sub>j</sub>, z<sub>j</sub>) and confirms the following equations:<maths id="math0072" num="(8);"><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = h(a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> · (v{ZA})</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> mod p, z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0804003A2_D0072.tif" /></maths> and<maths id="math0073" num="( )."><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = (a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> · (v{ZA})</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p) </mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p</mtext></mrow></math><img file="EP0804003A2_D0073.tif" /></maths>
The user (member) j makes his signature on the message m(j) based on the following formula; and then the user j selects a secret random number(j) and carries out the following equations given below.
Since x<sub>j</sub> = a<sup>{y<sub2>j</sub2>}</sup> · (v{ZA})<sup>{e<sub2>j</sub2>}</sup> mod p holds in the above equations, a<sup>{y<sub2>j</sub2>}</sup> · (v{ZA})<sup>{e<sub2>j</sub2>}</sup> mod p will be denoted as x<sub>j</sub> in the following equations:<maths id="math0074" num=""><math display="block"><mrow><msub><mrow><mtext>x(j) = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{r(j)}</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0074.tif" /></maths><maths id="math0075" num=""><math display="block"><mrow><mtext>e(j) = h(x(j), m(j));</mtext></mrow></math><img file="EP0804003A2_D0075.tif" /></maths> and<maths id="math0076" num=""><math display="block"><mrow><msub><mrow><mtext>y(j) = r(j) + e(j) · s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> mod q.</mtext></mrow></math><img file="EP0804003A2_D0076.tif" /></maths>
Next, the signer j sends the parameter ((y<sub>j</sub>, e<sub>j</sub>, z<sub>j</sub>), ((y(j), e(j)), m(j))) as his signature to an intended person (procedure (3) and arrow 403 in Fig. 9).
Step 3 - Verification of the Signature
Firstly, the verifier confirms the above equation (8) and the following equation (procedure (4) in Fig. 4):<maths id="math0077" num=""><math display="block"><mrow><msub><mrow><mtext>e(j) ) = h((x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{y(j)}</mtext></mrow></msup><msub><mrow><mtext> · (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{e(j)}</mtext></mrow></msup><mtext> mod p, m(j)).</mtext></mrow></math><img file="EP0804003A2_D0077.tif" /></maths>
If the above is correct, the verifier can conclude that the signature on message m(j) is the group signature signed by a member who is permitted by the authority.
Methods to Reveal the Signer of the Group Signature
Revealing the signer of the group signature will be realized by following two methods respectively. In the following description, the group signature is ((e<sub>k</sub>, y<sub>k</sub>, z<sub>k</sub>), e(k), y(k), m), the signer is the user (member) k and the random number which corresponds to z<sub>k</sub> generated by the authority ZA is r<sub>k</sub>.
Method 1 - Revealing by the Authority
Because the authority can record the random number which is used for generating the certificate, the authority can also distinguish which member corresponds to z<sub>k</sub> in the certificate when a group signature was given. Therefore, the authority can recognize that the signer is member k, and that the random number is r<sub>k</sub> = log<sub>vk</sub> z<sub>k</sub>.
The authority proves that the secret key corresponding to the public key of the certifier is the secret key corresponding to the public key of the member. That is, the authority proves following equation by using Zero Knowledge Proof protocol for proving the equality of discrete logarithms:<maths id="math0078" num=""><math display="block"><mrow><msub><mrow><mtext>log</mtext></mrow><mrow><mtext>vk</mtext></mrow></msub><msub><mrow><mtext> z</mtext></mrow><mrow><mtext>k</mtext></mrow></msub><msub><mrow><mtext> = log x</mtext></mrow><mrow><mtext>k</mtext></mrow></msub><mtext>.</mtext></mrow></math><img file="EP0804003A2_D0078.tif" /></maths>
In this equation, x<sub>k</sub> = a<sup>{y<sub2>k</sub2>}</sup> · (v<sub>i</sub>) <sup>{e<sub2>k</sub2>}</sup> mod p.
Also, the public key of the member is registered together with the identity on the public database.
Zero Knowledge Proof protocol for proving for log<sub>vk</sub> z<sub>k</sub> = log<sub>a</sub> x will be described next. <ul id="ul0009" list-style="none"><li>(1) The prover P sends v<sub>k</sub> to the verifier V.</li><li>(2) The verifier V selects random numbers r1 and r2 from Z<sub>q</sub>* and carries out the equation ch = (v<sub>k</sub>)<sup>r1</sup> · a<sup>r2</sup>. The verifier V sends its result to the prover P.</li><li>(3) The prover P selects a random number t (from Z<sub>q</sub>*<sup>),</sup> and carries out the equations h1 = ch · a<sup>t</sup> and h2 = (h1)<sup>{r<sub2>k</sub2>}</sup>. The prover P then sends the results to the verifier V.</li><li>(4) The verifier V sends (r1, r2) to the prover P.</li><li>(5) The prover P confirms ch = (v<sub>k</sub>)<sup>r1</sup> · a<sup>r2</sup>, and sends t to the verifier V.</li><li>(6) The verifier V confirms h1 = (v<sub>k</sub>)<sup>r1</sup> · a<sup>{r2 + t}</sup> and h2 = (z<sub>k</sub>)<sup>r1</sup> · (x<sub>k</sub>) <sup>{r2 + t}</sup>.</li></ul>
The above protocol is one example; and other protocols may also be used in carrying out a proof.
Method 2 - Disavowal by Each of the Members
Another proof can be carried out, by means of which each member proves that the group signature to be examined was not generated by one of the members.
The member j (prover P) proves to the verifier V that the secret key corresponding to z<sub>k</sub> used for the group signature is different from the member's secret key (s<sub>j</sub> = log<sub>xj</sub> z<sub>j</sub>). That is, the equation (log<sub>a</sub> v<sub>j</sub> ≠ log<sub>xk</sub> z<sub>k</sub>) is proven by using the following protocol PL.
The protocol PL is executed under the assumption that both the prover P and verifier V know p, q, a, v<sub>i</sub>, v<sub>j</sub>, z<sub>k</sub> and x<sub>k</sub> = a<sup>{y<sub2>k</sub2>}</sup> · (v<sub>k</sub>)<sup>{e<sub2>k</sub2>}</sup> mod p and have agreed on a parameter d.
In this protocol PL, BC(r, R) is referred to as the bit-commitment to bit r using random input R.
If someone selects 0 or 1, and computes the bitcommitment with a random input R and sends the commitment to another person, then that other person can not know which is selected (0 or 1) unless the other person obtains the random number R. Once a bit is committed, the commitment can not be changed. An example of this is described in an article entitled "Practical and Provably Secure Release of a Secret and Exchange of a Signature" by I.B. Damgard, Proc. of EUROCRYPT 93, pp. 207-17 (1994).
Zero knowledge proof protocol for proving log<sub>a</sub> v<sub>j</sub> ≠ log<sub>xk</sub> z<sub>k</sub> will be described next.
In the following description, "mod p" will be omitted at times, to simplify the equations; however, one skilled in the art will understand that modular arithmetic is used, where it is used. <ul id="ul0010" list-style="none"><li>(1) The verifier V selects a random number e (from Z<sub>q</sub>*<sup>)</sup> and B from (0, 1), carries out the following equations:<maths id="math0079" num=""><math display="block"><mrow><msup><mrow><mtext>if B = 0, (r1,r2) = (a</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><msub><mrow><mtext>, (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><mtext>);</mtext></mrow></math><img file="EP0804003A2_D0079.tif" /></maths> and<maths id="math0080" num=""><math display="block"><mrow><msub><mrow><mtext>if B = 1, (r1,r2) = ((x</mtext></mrow><mrow><mtext>k</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><msub><mrow><mtext>, (z</mtext></mrow><mrow><mtext>k</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><mtext>).</mtext></mrow></math><img file="EP0804003A2_D0080.tif" /></maths> The result of this operation is then sent to the prover P. </li><li>(2) The prover P confirms whether r1<sup>{-sj}</sup> ≡ r2 (mod p) is invalid or not. If it is invalid, then r is 1. On the other hand, if it is valid, then r is 0. Accordingly, the prover P sends g = BC(r,R) to the verifier V.</li><li>(3) The verifier V sends e to the prover P.</li><li>(4) The prover P confirms that (r1,r2) = (a<sup>e</sup>, (v<sub>j</sub>)<sup>e</sup>) or (r1,r2) = ((x<sub>k</sub>)<sup>e</sup>, (z<sub>k</sub>)<sup>e</sup>). If neither is invalid, the prover P makes ans = stop. If either is valid then ans = R. Then the prover P sends the ans to the verifier V.</li><li>(5) If ans = stop, the verifier V quits the protocol. If ans = R, the verifier V confirms that BC(B,R) = g.</li><li>(6) The procedure (1) ∼ (5) is repeated d times.</li></ul>
The above-described protocol is only one example; and other protocols may also be used to establish the proof.
The receiver who has the group signature to be examined may use either method 1 or method 2 at his option. Initially, the receiver may use method 1 automatically, and then use method 2 if the authority does not execute method 1 well. Alternatively, the receiver may initially use method 2, and then use method 1 if any problem occurs (for example, the receiver can not contact with any members).
If there are a plurality of groups, a plurality of authorities corresponding, respectively, to each group may be established. Also, one authority may represent all groups. In any case, the above method will be able to carry out the group signature method.
In the above described embodiment, the authority, the specifier, the verifier, the group member and the receiver will be able to carry out the above procedures on any apparatus, such as a personal computer, which is capable of processing information and which is capable of communicating. Also, communications among the signer, the specifier, the authority, the member, the verifier, and the receiver may be carried out by using the service of an anonymous communication system such as the Internet.
An information communication system having a digital signature according to this embodiment employs an information operating apparatus, as above described, for carrying out each of the above steps, and a communication network. In this embodiment, the network is not limited to the Internet; a so-called intranet can be used in place of the Internet.
Also in this embodiment, the anonymous public key certificate is sent by the authority directly to the member. In other situations, the receiver and the member may access the public database in which the certificate is registered.
As mentioned above, this embodiment makes use of the new group signature system in which each member can prove whether or not the signature being used is their own signature.
Furthermore, in this system, the data length of the group's public key is not proportional to number of members. For example, on the assumption that a prime number is 688 bits, a security parameter t of a one way hash function is 70 bits and the public key size of the group signature (according to Park) is 1676 bits.
On the other hand, the public key size of the above described embodiment for the same group is 1108 bits (about 34% decrease from Park's data size).
Therefore, a system based on this embodiment can be used at low cost, since there is a reduction of the amount of data to be dealt with as well as flexibility for revealing the signer.
In this embodiment, the authority can reveal the signer of the signature; and each member can prove disavowal. Therefore, if one of them does not work well, the remainder can be availabe to reveal the signer of the signature. So as a whole, the system based on this embodiment will be convenient for use, and will be flexible.
Furthermore, it is easy to add a new member to the group; and accordingly it is easy to manage the system.
The Seventh Embodiment
The seventh embodiment will now be described. A description of those parts of this embodiment which are the same as in the previous embodiment will be omitted.
In the previous embodiment, the anonymous public key certificate corresponding to z<sub>j</sub> was generated based on the Schnorr signature scheme. And p,q,x<sub>j</sub>,z<sub>j</sub> was public key, s<sub>j</sub> was secret key and the Schnorr signature scheme was applied to the message m(j).
However, in this embodiment, ElGamal Cryptography, instead of the Schnorr signature scheme, will be applied to the message m(j).
The features of this embodiment which are different from those of the previous embodiment are described below.
Step 2 - Generation of the Group Signature
The signer j makes his signature on a message m(j) based on the following formula; and he selects a secret random number k(j) from <i>Z</i><sub><i>p</i></sub>* according to the following equations:<maths id="math0081" num=""><math display="block"><mrow><msub><mrow><mtext>r(j) = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{k(j)}</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0081.tif" /></maths> and<maths id="math0082" num=""><math display="block"><mrow><msub><mrow><mtext>f(j) = (h(m(j)) + s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext> · r(j)) · k(j)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><mtext> mod (p-1).</mtext></mrow></math><img file="EP0804003A2_D0082.tif" /></maths>
Next, the signer j sends the parameter ((y<sub>j</sub>, e<sub>j</sub>), z<sub>j</sub>, r(j), f(j), m(j)) as his signature to an intended person.
Step 3 - Verification of the Signature
The verifier confirms the following equations in order:<maths id="math0083" num=""><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = h(a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> . (v{ZA}</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>(e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> )</mtext></mrow></msup><msub><mrow><mtext> mod p, z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>);</mtext></mrow></math><img file="EP0804003A2_D0083.tif" /></maths> and<maths id="math0084" num=""><math display="block"><mrow><msub><mrow><mtext>(x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>(h(m(j))</mtext></mrow></msup><msub><mrow><mtext> ≡ (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{r(j)}</mtext></mrow></msup><msup><mrow><mtext> · r(j)</mtext></mrow><mrow><mtext>(fj)</mtext></mrow></msup><mtext> (mod p) .</mtext></mrow></math><img file="EP0804003A2_D0084.tif" /></maths> If the above is correct, the verifier can conclude that the signature for the message m(j) was signed by the signer j.
The Eighth Embodiment
The eighth embodiment will be described next. In the following, a description of those parts of this embodiment which are the same as in the previous embodiment will be omitted.
In the previous embodiment, the anonymous public key certificate of z<sub>j</sub> was generated based on the Schnorr signature scheme or ElGamal cryptography; and the Schnorr signature acheme or ElGamal cryptography was applied to the message m(j).
However, in this embodiment, DSA (Digital Signature Algorithm), which is proposed as the digital signature standard at NIST (National Institute of Standard and Technology), is used for the message m(j).
In this embodiment, p, q, x<sub>j</sub>, z<sub>j</sub> represent the public key and s<sub>j</sub> represents the secret key.
Step 2 - Generation of the Group Signature
The signer j makes his signature on a message m(j) based on the following formula; and the signer j selects a secret random number k(j) from Zq‡ and carries out the following equations:<maths id="math0085" num=""><math display="block"><mrow><msub><mrow><mtext>r(j) = ((x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{k(j)}</mtext></mrow></msup><mtext> mod p) mod q;</mtext></mrow></math><img file="EP0804003A2_D0085.tif" /></maths> and<maths id="math0086" num=""><math display="block"><mrow><msup><mrow><mtext>f(j) = (k(j))</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><msub><mrow><mtext> · (h(m(j)) - s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> · r(j))) mod q.</mtext></mrow></math><img file="EP0804003A2_D0086.tif" /></maths>
Next, the signer j sends the parameter ((y<sub>j</sub>, e<sub>j</sub>), z<sub>j</sub>), (r(j), f(j), m(j))) as his signature to a predetermined person.
Step 3 - Verification of the Signature
The verifier confirms the following equation:<maths id="math0087" num=""><math display="block"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = h(a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{y </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>ZA</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{e </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> mod p, z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>).</mtext></mrow></math><img file="EP0804003A2_D0087.tif" /></maths>
Then, the verifier confirms 0 < r(j) < q and 0 < f(j) < q, and carries out the following equations:<maths id="math0088" num=""><math display="block"><mrow><msup><mrow><mtext>w = (f(j))</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><mtext> mod q;</mtext></mrow></math><img file="EP0804003A2_D0088.tif" /></maths><maths id="math0089" num=""><math display="block"><mrow><mtext>u1 = h(m(j)) · w mod q;</mtext></mrow></math><img file="EP0804003A2_D0089.tif" /></maths><maths id="math0090" num=""><math display="block"><mrow><mtext>u2 = r(j) . w mod q;</mtext></mrow></math><img file="EP0804003A2_D0090.tif" /></maths> and<maths id="math0091" num=""><math display="block"><mrow><msub><mrow><mtext>v = ((x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{u1}</mtext></mrow></msup><msub><mrow><mtext> · (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{u2}</mtext></mrow></msup><mtext> mod p) mod q;</mtext></mrow></math><img file="EP0804003A2_D0091.tif" /></maths> and the verifier confirms v = r(j). If the above equations are correct, the receiver can conclude that the signature for the message m(j) was signed by the member who was permitted by the authority.
The Ninth Embodiment
The ninth embodiment of this invention is described below.
A description of those parts of this embodiment which are the same as in the previous embodiment, is omitted.
In this embodiment, the above mentioned ElGamal cryptography is used to generating an anonymous public key certificate of z<sub>j</sub> instead of the Schnorr signature scheme.
Nevertheless. it should be noted that the following equations are valid:<maths id="math0092" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0092.tif" /></maths> and<maths id="math0093" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0093.tif" /></maths>
Step 1 - Issue of Certificates to Members
In a concrete example, the authority selects a secret random number rj from Z<sub>q</sub>* for the member and carries out the following equations:<maths id="math0094" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0094.tif" /></maths><maths id="math0095" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0095.tif" /></maths> and<maths id="math0096" num=""><math display="block"><mrow><msub><mrow><mtext>f</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> + s</mtext></mrow><mrow><mtext>ZA</mtext></mrow></msub><msub><mrow><mtext> · x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>) · (r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><mtext> mod (p-1).</mtext></mrow></math><img file="EP0804003A2_D0096.tif" /></maths>
In this embodiment, the parameter (x<sub>j</sub>, f<sub>j</sub>, z<sub>j</sub>) is the certificate of the public key.
Step 2 - Verification of the Certification
The right of the certification of public key is proved by confirming the following equations:<maths id="math0097" num=""><math display="block"><mrow><mtext>a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{z </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> ≡ (v</mtext></mrow><mrow><mtext>ZA</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{x </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><msub><mrow><mtext> · (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{f </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> (mod p);</mtext></mrow></math><img file="EP0804003A2_D0097.tif" /></maths> and<maths id="math0098" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0098.tif" /></maths>
The Tenth Embodiment
The tenth embodiment of this invention is described below.
A description of those parts of this embodiment which are the same as in the previous embodiment, is omitted.
In this embodiment, above mentioned DSA is used for generating a certificate of a public key for z<sub>t</sub> instead of the Schnorr signature scheme and ElGamal cryptography methods.
Nevertheless, it should be noted that the following equations are valid:<maths id="math0099" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0099.tif" /></maths> and<maths id="math0100" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0100.tif" /></maths>
Step 1 - Issue of Certificates to Members
In a concrete example, the authority selects a secret random number r<sub>j</sub> from Zq‡ for the member j and carries out the following equations:<maths id="math0101" num=""><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> = a</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0101.tif" /></maths><maths id="math0102" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (v</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{r </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p;</mtext></mrow></math><img file="EP0804003A2_D0102.tif" /></maths> and<maths id="math0103" num=""><math display="block"><mrow><msub><mrow><mtext>f</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (r</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><msub><mrow><mtext> · (h(z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext>)-s</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> · x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) mod q.</mtext></mrow></math><img file="EP0804003A2_D0103.tif" /></maths>
Also, in this embodiment, the parameter (x<sub>j</sub>, s<sub>j</sub>, z<sub>j</sub>) is the certificate of the public key.
Step 12 - Verification
The authenticity of the certification of the public key is verified by confirming 0 < x<sub>j</sub> < p, 0 < f<sub>j</sub> < q and the following equations:<maths id="math0104" num=""><math display="block"><mrow><msub><mrow><mtext>w = (f</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{-1}</mtext></mrow></msup><mtext> mod q;</mtext></mrow></math><img file="EP0804003A2_D0104.tif" /></maths><maths id="math0105" num=""><math display="block"><mrow><msub><mrow><mtext>u1 = h(z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) · w mod q;</mtext></mrow></math><img file="EP0804003A2_D0105.tif" /></maths><maths id="math0106" num=""><math display="block"><mrow><msub><mrow><mtext>u2 = x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> · w mod q;</mtext></mrow></math><img file="EP0804003A2_D0106.tif" /></maths> and<maths id="math0107" num=""><math display="block"><mrow><msup><mrow><mtext>v = a</mtext></mrow><mrow><mtext>{u1}</mtext></mrow></msup><msub><mrow><mtext> · (v</mtext></mrow><mrow><mtext>ZA</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>{u2}</mtext></mrow></msup><mtext> mod p,</mtext></mrow></math><img file="EP0804003A2_D0107.tif" /></maths> and v = x<sub>j</sub> is confirmed.
The authenticity of certificate of public key is verified by confirming the following equation:<maths id="math0108" num=""><math display="block"><mrow><msub><mrow><mtext>z</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><msub><mrow><mtext> = (x</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext></mtext></mrow><mrow><msub><mrow><mtext>{-s </mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> }</mtext></mrow></msup><mtext> mod p.</mtext></mrow></math><img file="EP0804003A2_D0108.tif" /></maths>
Another Embodiment
This invention can be used not only for a system which is comprised of several kinds of apparatuses, for example, a host computer, a reader, a printer and an interface, but also an apparatus such as a fax machine or a copying machine, etc.
In the previously described embodiments, each step for a process may be executed by a software program stored in some medium such as a floppy disk, a hard disk, an optical disc, a magnetic optical disc, a CD-ROM, a CD-R, a magnetic tape, a non-volatile memory, a ROM, etc.
In such a case, the information of at least the issued information generating module, the signature generating module, the recognition module, the changing module, or base generating module, the public key generating module, the signature generating module and the confirmation module is stored in a medium shown as Figs. 11 and 12.
An apparatus, such as a computer, reads out the software program from the medium and executes steps based on the software program or the software program within the operating system of the apparatus.
Moreover, the software program which is read out from the medium, may be written in the memory of an expansion card or an expansion unit connected with the computer. In such case, the CPU of the expansion card or the expansion unit may execute the above mentioned steps based on the software program.
As seen from the above, this embodiment employs the group signature method as well as the new group signature system based on the group signature method in which the data length of the public key of the group is not linear in relation to the number of members. Therefore, a system based on the embodiment is convenient, and is of minimal cost, because the size of the data to be dealt with is reduced and because the system achieves flexibility for revealing the signer.
In this embodiment, the authority can reveal the signer of the signature; and each member can prove disavowal. Thus, as a whole, a system based on this embodiment is convenient and flexible. Furthermore, this embodiment permits a group signature and a new group signature system based on the group signature method in which it is easy to add a new member to the group. Therefore, management of this system is easy.
Contents4
119 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18 Sheet 19 Sheet 20 Sheet 21 Sheet 22 Sheet 23 Sheet 24 Sheet 25 Sheet 26 Sheet 27 Sheet 28 Sheet 29 Sheet 30 Sheet 31 Sheet 32 Sheet 33 Sheet 34 Sheet 35 Sheet 36 Sheet 37 Sheet 38 Sheet 39 Sheet 40 Sheet 41 Sheet 42 Sheet 43 Sheet 44 Sheet 45 Sheet 46 Sheet 47 Sheet 48 Sheet 49 Sheet 50 Sheet 51 Sheet 52 Sheet 53 Sheet 54 Sheet 55 Sheet 56 Sheet 57 Sheet 58 Sheet 59 Sheet 60 Sheet 61 Sheet 62 Sheet 63 Sheet 64 Sheet 65 Sheet 66 Sheet 67 Sheet 68 Sheet 69 Sheet 70 Sheet 71 Sheet 72 Sheet 73 Sheet 74 Sheet 75 Sheet 76 Sheet 77 Sheet 78 Sheet 79 Sheet 80 Sheet 81 Sheet 82 Sheet 83 Sheet 84 Sheet 85 Sheet 86 Sheet 87 Sheet 88 Sheet 89 Sheet 90 Sheet 91 Sheet 92 Sheet 93 Sheet 94 Sheet 95 Sheet 96 Sheet 97 Sheet 98 Sheet 99 Sheet 100 Sheet 101 Sheet 102 Sheet 103 Sheet 104 Sheet 105 Sheet 106 Sheet 107 Sheet 108 Sheet 109 Sheet 110 Sheet 111 Sheet 112 Sheet 113 Sheet 114 Sheet 115 Sheet 116 Sheet 117 Sheet 118 Sheet 119
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| DE19919909C2 | Cited by | Germany | Search report |
| CN110009349A | Cited by | China | Search report |
| FR2950213A1 | Cited by | France | Search report |
| WO2004104797A1 | Cited by | World Intellectual Property Organization (WIPO) | International search |
| US8689000B2 | Cited by | United States of America | Applicant |
| US7203316B1 | Cited by | United States of America | Applicant |
| WO2011030069A1 | Cited by | World Intellectual Property Organization (WIPO) | International search |
| DE19919909A1 | Cited by | Germany | Search report |
| WO2004104797A1 | Cited by | World Intellectual Property Organization (WIPO) | International search |
6 members in 3 offices
Priority claims8
| Document | Office | Kind | Date |
|---|---|---|---|
| 10822596 | Japan | – | |
| 10822596 | Japan | A | |
| 10822696 | Japan | – | |
| 10822696 | Japan | A | |
| 10822596 | – | – | – |
| 10822696 | – | – | – |
| JP19960108225 | – | – | – |
| JP19960108226 | – | – | – |
Members6
| Document | Office | Kind | |
|---|---|---|---|
| EP0804003A2This record | European Patent Office (EPO) | A2 | |
| JPH09298536A | Japan | A | |
| JPH09298537A | Japan | A | |
| EP0804003A3 | European Patent Office (EPO) | A3 | |
| US6154841A | United States of America | A | |
| JP3513324B2 | Japan | B2 |
8 legal events, as the office reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | |
|---|---|---|
| Application withdrawnWithdrawn18W | 18W | |
| Information on the status of an ep patent application or granted ep patentGrantedSTATUS: THE APPLICATION HAS BEEN WITHDRAWNSTAA | STAA | |
| First examination report despatched17Q | 17Q | |
| Request for examination filed17P | 17P | |
| Designated contracting statesAK | AK | |
| Search report despatchedORIGINAL CODE: 0009013PUAL | PUAL | |
| Designated contracting statesAK | AK | |
| Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI | PUAI |
Numbers
- Publication
- 0804003
- Publication, DOCDB
- 0804003
- Publication, EPODOC
- EP0804003
- Application
- 97302857
- Application, DOCDB
- 97302857
- Application, EPODOC
- EP19970302857
Titles3
- German
- Verfahren zur digitalen Unterschrift und Kommunikationssystem
- English
- Digital signature method and communication system
- French
- Procédé de signature numérique et système de communication
Classification
- CPC, 4
- H04L9/3218
- H04L9/3013
- H04L9/3255
- H04L2209/42
- IPC, 1
- H04L9 32
Designated states1
- Contracting states, 1
- United Kingdom