JPH09298536A - Digital signature system and information communication system using the same - Google Patents

Abstract

PROBLEM TO BE SOLVED: To keep the anonymity of a specified signer by generating signature information by using private information peculiar for each user and a public parameter. SOLUTION: A specifier (i) calculates z-j into which a public key v-j of a certain user, namely, a specified signer (j) is converted by using a random number r-j, finds the signature corresponding to z-j and registers it in a public database. The specified signer (j) confirms a prescribed expression is to be established and confirms the signatures [(y-j, e-j), z-j] registered by the specifier (i) is correspondent to himself/herself. Concerning a message m(j), the specified signer (j) selects a secret random number r(j), performs prescribed calculation and sends [(y-j, e-j), z-j] and [(y(j), e(j), m(j)] to a party as signatures. A verifier who receives these signatures, confirms the prescribed expression and confirms the signatures corresponding to the message m(j) are generated by the specified signer (j) selected by the specifier (i).

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a digital signature system and an information communication system using the digital signature system.

[0002]

2. Description of the Related Art With the development and widespread use of computers and communication networks, functions such as social activities can be realized on the networks. However, it is possible to easily understand who did what, when, where, and what they did. In order to counter it, anonymous processing is used to realize various functions on the network and protect privacy. A method is being considered.

By using public key cryptography, which will be described later, the sender can send the communication contents only to the intended receiver, and the receiver can surely confirm who is the sender of the communication. . By using a zero-knowledge proof, which will be described later, it is possible to prove to a third party that a user holds certain confidential information without revealing the secret. Information and communication systems that apply these are Masahiro MAMBO, Eiji OKAMOTO,
"A method to publicly specify a signer with hidin
g identity, The 18th Symposium on Information Theo
ry and Its Applications "(October 1995). This is called" MO system "in the following.

The public key cryptography, then the zero-knowledge proof, and then the MO system will be described in detail below.

[Public Key Cryptography] Public key cryptography is an encryption method in which the encryption key and the decryption key are different, and the encryption key is disclosed and the decryption key is kept secret, and has the following features. (1) Since the encryption key and the decryption key are different and the encryption key can be disclosed, it is not necessary to secretly distribute the encryption key, and the key can be easily distributed. (2) Each user only needs to disclose the encryption key and keep only the decryption key secret. (3) It is possible to realize an authentication function (digital signature) for the receiver to confirm that the sender of the sent communication text is not an impostor and that the communication text has not been tampered with.

For the message (plaintext) M, the public encryption key k
Let E (kp, M) be the encryption operation using p, and use the secret decryption key ks
Letting D (ks, M) be the decryption operation using, the public key cryptographic algorithm first satisfies the following two conditions. (1) The calculation of E (kp, M) is easy when the encryption key kp is given, and the calculation of D (ks, M) is easy when the decryption key ks is given. (2) If you do not know the decryption key ks, even if you know the encryption key kp, the calculation procedure of the encryption operation E, and the encryption C = E (kp, M), determining the plaintext M is Difficult to calculate.

In addition to the above (1) and (2), the following conditions
By satisfying (3), secret communication can be realized. (3) E (kp, M) can be defined for all plaintexts M, and the following equation holds. D (ks, E (kp, M)) = M

That is, since the encryption key kp is open to the public,
Anyone can calculate E (kp, M), but D (ks, E (k
Only the person who remembers the secret decryption key ks can calculate p, M)) to obtain the plaintext M.

On the other hand, in addition to the above (1) and (2), the following condition (4)
By satisfying, the authentication communication (digital signature) can be realized. (4) D (ks, M) can be defined for all plaintexts M, and the following equation holds. E (kp, D (ks, M)) = M

That is, D (ks, M) can be calculated only by the person who remembers the secret decryption key ks, and the false key by another person.
Even if D (ks', M) is calculated using ks' and an attempt is made to impersonate the person who remembers the secret decryption key ks, E (kp, D (ks', M)) ≠
M, the recipient can know that the received information is incorrect.

Similarly, even if D (ks, M) is tampered with, E (kp,
Since D (ks, M) ') ≠ M, the recipient can know that the received information is incorrect. This D (ks, M) is M
Is called a "digital signature".

Typical public key cryptosystems are listed below.
RSA encryption (R.
L. Rivest, A. Shamir and L. Adleman: "A method of
obtaining digital signatures and public key crypto
systems ", Comm. of ACM, 1978), R cipher (M. Rabin:" Di
gitalized signatures and public-key cryptosystem
s ", MIT / LCS / TR-212, Technical Report MIT, 1979), W
Cryptography (HC Williams: "Amodification of the RSA pub
lic-key encryption procedure ", IEEE Trans. Inf. Th
eory, IT-26, 6, 1980).

Further, as a system capable of performing only secret communication,
CR cipher (B. Chor and RL Rivest: "A knapsack type p
ublic key cryptosystem based on arithmetric in fin
itefield ", Proc. Crypto 84), M encryption (RJ McEliece:
"A public-key cryptosystem based on algebraic cod
ing theory ", DSN Progress Rep., Jet PropulsionLa
b., 1978), E encryption (TE ElGamal: "A public key cryp
tosystem and a signature scheme based on discretre
logarithms ", IEEE Transaction on Information Theo
ry, Vol. IT-31, No.4, pp.469-472, 1985).

S-encryption is a method that allows only authenticated communication.
(A. Shamir: "A fast signature scheme", Report MIT /
LCS / TM-107, MIT laboratory for computer science, C
ambridge, Mass., 1978), L cipher (K. Lieberherr: "Unif
orm complexity and digitalsignature ", Lecture Note
s in Computer Science 115 Automata, Language and Pr
ogramming, Eigtht Colloquium Acre, Israel, 1981),
GMY encryption (S. Goldwasser, S. Micali and A. Yao: "Stro
ng signature schemes ", ACM Symp. on Theory of Comp
uting, 1983), GMR encryption (S. Goldwasser, S. Micali and
RL Rivest: "A 'paradoxical' solution to the si
gnature problem ", ACM Symp. on Foundation of Compu
ter Science, 1984), E-cipher (TE ElGamal: "A public
key cryptosystem and a signature scheme based on
discretre logarithms ", IEEE Transaction on Informa
tion Theory, Vol.IT-31, No.4, pp.469-472, 1985),
OS Cryptography (Okamoto, Shiraishi: "Digital Signature Scheme by Polynomial Arithmetic", IEICE (D), J68-D, 5, 1985; T. Okamoto and
A. Shiraisi: "A fast signature scheme based on qua
dratic inequalities ", IEEE Symp. on Theory of Comp
uting, 1984),

Fiat-Shamir encryption (A. Fiat, A. Shamir: "H
ow to prove yourself: practicalsolutions of identi
fication and signature problems ", Proc. of CRYPTO '
86,1987), Schnorr cipher (CP Schnorr: "Efficient si
gnature generation by smart cards ", Journal of Cry
ptology, vol.4, pp.161-174, 1991).

As a specific example, the Schnorr cipher, which is a signature scheme in which the security of the security is based on the difficulty of obtaining the discrete logarithm, the security against forgery is extremely high, and the signature size is small, will be described. In the following description, a ^ b represents a to the bth power.

For example, when selecting a large prime number p and a large prime number q such that q | p-1 (q is a divisor of p-1), {1, 2, ..., q-
If one of 1} is α, then x that satisfies α ^ x≡u (mod p)
(= DL (u, α)) is the discrete logarithm in the Galois field GF (p), and it is considered difficult to efficiently find x given p, q, α, u. ing.

In the Schnorr encryption, a key authentication center (KAC: Key
Authentication Center) initializes the system.
The signer performs key generation and signature generation, and the certifier receives and confirms the signature. One-way hash functions are used in the system. The one-way hash function is a compression function that does not easily cause a collision. That is, it is difficult to input a value of an arbitrary length, output a value of a fixed length, and find different inputs that output the same value. Z is a set of integers, Zq
Is a set of integers between 0 and less than q.

System initialization (1) The key authentication center (KAC) has a large prime number p (≧ 2 ^ 512) and q (≧ 2 ^ 512).
2 ^ 140) and publish. However, it is q | p-1. (2) KAC selects and publishes α (≠ 1) such that α ∈ Zp and α ^ q = 1 (mod p). (3) KAC selects h: Zq × Z → {0,…, 2 ^ t-1} and publishes it. Here, t is called a "security parameter". (4) KAC selects a public key and a private key for its own signature, and publishes the public key (for example, Fiat-Shamir encryption).

A user (signer) who joins the key generation system selects an arbitrary integer s such that 0 <s ≦ q and calculates v = α ^ {-s} mod p.

The signer's private key is s and the public key is v. The certifier can verify the legitimacy of the signer's public key, for example, by KAC signing the signer's public key (eg, with the Fiat-Shamir cipher), or by signing the signer's public key in a public database. It can be confirmed by being registered.

Signature Generation (Signature for Message m) (1) The signer selects a random number r ∈ {1, ..., q}, and x = α ^ r (mo
Calculate dp). (2) The signer requests e = h (x, m). (3) The signer calculates y = r + s · e (mod q). (e, y)
Is the signature for message m.

Signature Verification The authenticator who has received the message m and the signature (e, y) confirms the validity of v by the above-mentioned method, and confirms the following equation. x '= α ^ y ・ v ^ e (mod p) e = h (x', m)

[Zero-knowledge proof] Zero-knowledge proof is that a prover proves a certain proposition to a verifier, and satisfies the following three conditions. (1) Completeness: If the proof is correct, the verifier accepts 1 or a probability close to 1 (overwhelming probability). (2) Soundness: If the proof is incorrect, the verifier rejects it with a probability of 1 or infinitely close to 1 (overwhelming probability). (3) Zero knowledge: If the proof is correct, no matter how the verifier behaves, no information other than the correctness of the proof can be leaked.

A certifier who knows a secret (numerical value)
Several zero-knowledge proof methods have been proposed to prove to a verifier that the secret is known without leaking any information regarding the secret, and it has been applied to identity certification and digital signatures, etc. Has become an important basic technology in.

As a concrete example, J. Boyar, D. Chau
m, I. Damard, T. Pedersen, "Convertible undeniable
signatures ", Proc. of CRYPTO'90, the certifier who knows z = DL (u, α) is DL (v, w) = DL (u, α) without revealing z We describe a zero-knowledge proof protocol that proves, where DL (u, α) means the discrete logarithm in the appropriate group (eg GF (p) above).
, Then α ^ {DL (u, α)} ≡ (mod p)).

Zero-knowledge proof protocol for proving DL (v, w) = DL (u, α) In the following, the prover is described as P (Prover) and the verifier is as V (Verifier). Both P and V know v, w, u, α. (1) The verifier V selects random numbers a and b (a, b ∈ Zq), ch = w ^ a
Find α ^ b and send ch to prover P. (2) The prover P chooses a random number t (t ∈ Zq), h1 = ch ・ α ^ t and h2
= Calculate h1 ^ z and send (h1, h2) to the verifier V. (3) The verifier V sends (a, b) to the prover P. (4) The prover P confirms ch = w ^ a · α ^ b and sends t to the verifier V. (5) The verifier V is h1 = w ^ a ・ α ^ {b + t} and h2 = v ^ a ・ u ^ {b + t}
Check.

[MO System] FIG. 1 is a diagram for explaining an MO system to which public key cryptography and zero-knowledge proof are applied. The MO system is a designated person, a plurality of users, and a signer selected from the users. It consists of a verifier who verifies the signature created by the signer. In the following description, a_b represents a state in which a subscript b is added to a.

In FIG. 1, "Public Values"
Is the data common to all systems described below,
(Public Database) "is a public database, arrows indicate acquisition, transmission, and reception of data, and numbers in parentheses indicate processing procedures. In addition, `` Signator (Specified Sig
“Ner)” represents the signer selected from the users by the “Specifier”, and “Verifier” represents the person who verifies the signature.

Step 0 (preparation): As data common to the system, the primes p and q (q | p-1), the element of Zp * and the order q α (α ^)
q ≡ 1 (mod p), Zp * is a set of integers that are relatively prime with Zq and p), one-way hash function h: Zq × Z → {0,…, 2 ^ t
-1} is prepared. It is assumed that these are registered in a public database that can be accessed by all users participating in the system and that is appropriately managed so that unwarranted tampering does not occur.

The designated person i has a public key v_i and a secret key s_i (v_i = α
^ {-s_i} mod p) is generated and the public key is registered in the public database. A user j who can be a signer generates a public key v_j and a private key v_j (v_j = α ^ {-s_j} mod p) and registers the public key in a public database. There are multiple users,
There can be multiple signers.

Step 1 (User designation and disclosure): Designator i
Selects a user from a plurality of users, that is, signer j (arrow 101 in FIG. 1), calculates z_j obtained by converting public key v_j of signer j using random number r, and signs z_j (Schnor
(a signature by r encryption) (procedure (1) shown in FIG. 1) and registered in the public database (arrow 102 shown in FIG. 1).

Specifically, the designated person i is a (secret) random number r (r
∈ Zq *), each parameter is calculated by the following equation, and the signature ((y_j, e_j, x), z_j) is registered in the public database. Note that r ∈ Zq * means that r is randomly selected from Zq *. x = α ^ r mod p z_j = {v_j} ^ r mod p e_j = h (x, z_j) y_j = r + e_j ・ s_i mod q

Step 2 (pickup of information): The user selects the designated person i from the contents registered in the public database.
It is confirmed as follows whether the signature ((y_j, e_j, x), z_j) registered by the user is for himself (procedure (2) shown in FIG. 1, arrow 103). That is, each user k confirms the following equation. e_j = h (α ^ {y_j} ・ {v_i} ^ {e_j} mod p, zj)… (1) z_j = x ^ {-s_k} mod q… (2)

It should be noted that the modulo value q of the equation (2) is incorrect, and it seems that the equation (3) should be correct.
o MAMBO, Eiji OKAMOTO, "A method to publicly speci
fy asigner with hiding identity ", The 18th Symposi
um on Information Theory and Its Applications "(Oc
tober 1995). z_j = x ^ {-s_k} mod p… (3)

All users can confirm that the equation (1) holds. In addition to that, signer j uses equation (2) or
It can be confirmed that (3) is also established, and it is understood that oneself has been selected as the designated person i.

On the other hand, another signer λ (s_λ ≠ s_j)
Reveals that Equation (2) or (3) does not hold with its own secret key s_λ, but it is unknown to which other signers Equation (2) or (3) holds. I don't know who else was chosen, because I don't know the private keys of other signers, eg s_j.

Step 3 (Signature Generation): The signer j generates a signature for the message m to be signed by the following signature method. The signer j selects a random number r_j (r_j ∈ Zq *) and calculates the following equation. x1 = α ^ {r_j} mod p x2 = {v_j} ^ {r_j} mod p

Then, the following equation is obtained. e '= h (x2, m) y =-(r_j-e') s_j mod q

Then, ((y_j, e_j, x), z_j, (y, e ', x
1), m) is sent as a signature to the necessary party (procedure (3) shown in FIG. 1, arrow 104).

Step 4 (Signature Confirmation): The confirmer receiving the above signature first confirms the above equation (1) and the following equation. e_j = h (z_j, α ^ {y_j} ・ {v_i} ^ {e_j} mod p)

Next, the following equation is confirmed (procedure shown in FIG. 1
(Four)). e '= h (m, x2) x2 = α ^ y ・ {v_j} ^ {e'} mod p… (4)

If the above can be confirmed, the signer j and the receiver (confirmer) DL (z_j, x) = DL (x2, x1) (=-s_
Perform zero-knowledge proof to prove j) (procedure shown in Fig. 1
(5), arrow 105). If the zero-knowledge proof is acceptable, the recipient convinces that the signature on m is the signature generated by the signer j selected by the designator i.

In the above MO system, a designated person i selects a certain signer j, the selected signer j can generate a signature anonymously, and the person who receives the signature can select the signature i selected by the designated person i. It can be confirmed that person j generated the signature, but
It is not possible to identify who the signer j is,
Is claimed. Due to the above properties, it is said that the MO system can be applied to welfare services and pay TV rating surveys.

That is, anyone can confirm that the welfare service and the audience rating survey are surely conducted, and the beneficiaries and the surveyees need the documents necessary for receiving the service (report of living condition). It is possible to submit a response to a survey or survey with an anonymous signature.

[0046]

However, the above-mentioned technique has the following problems. In other words, in the MO system, although the specified signer j confirms that the anonymously generated signature is valid, at that time, the public key of the signer j is required (equation (4) At v_j
Is used).

Further, since the above-mentioned zero-knowledge proof is used for confirmation, it is necessary to perform transmission and reception a plurality of times between the signer j and the confirmer, and it is also necessary to perform calculation for that purpose.

Further, since it is assumed that the communication network maintains anonymity no matter how many times it communicates with the same party, it is practical compared to a communication network which can maintain anonymity only once. The cost for converting to higher cost increases.

The present invention is intended to solve the above problems, and an object of the present invention is to provide a digital signature system capable of maintaining the anonymity of a signer.

Another object of the present invention is to provide an information communication system using a digital signature method, which can reduce the number of times of communication and do not have to perform calculations associated with a plurality of times of communication.

Another object of the present invention is to provide an information communication system using a digital signature system which can use a communication network capable of maintaining anonymity when performing communication at least once.

[0052]

The present invention has the following configuration as one means for achieving the above object.

In the digital signature system according to the present invention, a public information generating step of generating public information unique to each user from public parameters commonly used by each user and secret information unique to each user, and a predetermined information generating step. A signature generation step of generating signature information corresponding to the digital information by performing conversion using the secret information and the public parameter on the digital information, and a correspondence relationship between the digital information and the signature information, A determination step of determining using the public parameter and the public information; a new public parameter that can generate the signature information by converting the public parameter and the public information without converting the secret information; A public information conversion step.

A digital signature method in which the public key of each user is the result of index calculation using the secret key of each user as the exponent value for the bottom value commonly used by a plurality of users. A base generation step in which the result of performing exponential calculation with a random number as the exponent value for the base is used as a new base, and the result of performing exponential calculation with the random number as the exponent value for the public key of a predetermined user is the new public key. And a public key generation step in which the predetermined user generates a digital signature for arbitrary plaintext by using the private key of the predetermined user, and the base generation step and the public key generation step. Using the bottom and the public key,
And a confirmation step for confirming the validity of the digital signature generated in the signature generation step.

The information communication system according to the present invention includes a designating unit designating a generating unit for generating a digital signature,
An information communication system comprising a confirmation means for confirming whether or not a target digital signature is generated by the generation means designated by the designation means by using at least one digital signature system, One of the signature schemes is a digital signature scheme in which the public key of each user is the result of exponentiation with the secret key of each user as the exponent value for the base value commonly used by multiple users. , A base generation step in which the result of performing exponential calculation with the random number as the exponent value is used as a new base, and a result of performing exponential calculation with the random number as the exponential value in the public key of a predetermined user is updated. A public key generating step for making a public key; a signature generating step for the predetermined user to generate a digital signature for arbitrary plaintext using his / her private key; The digital signature method has a forming step and a confirmation step of confirming the validity of the digital signature generated in the signature generating step by using the base and the public key generated in the public key generating step. And

Further, by using the first digital signature method in which the security is based on the difficulty of obtaining the discrete logarithm,
Designating means for designating a signature generating means for generating a digital signature, obtaining means for obtaining a new bottom and a new public key by the second digital signature method according to any one of claims 5 to 7, and the obtaining. A first generation means for generating a first digital signature for the new public key obtained by the obtaining means by using the new base value obtained by the means, by the first digital signature scheme, The digital signature obtained by the first generation means is proof that the signature generation means having the private key corresponding to the new public key obtained by the acquisition means is designated.

Further, in order to specify the means for generating the signature, based on the specifying means for generating the first digital signature by the first digital signature method and the first digital signature generated by the specifying means. A signature generating means for generating a second digital signature by a second digital signature method, and a signature generating means for designating the second digital signature by the designating means based on the first and second digital signatures. And a confirmation unit that confirms whether or not the image is generated by.

[0058]

BEST MODE FOR CARRYING OUT THE INVENTION An information communication system according to an embodiment of the present invention will be described in detail below with reference to the drawings.

In the digital signature system according to the present invention, the public key and the base are converted by calculation using a random number as an exponent, but the digital signature system based on discrete logarithm is used by utilizing the property that the value of the secret key does not change. It is constructed and uses a normal digital signature scheme instead of the digital signature scheme using zero knowledge proof in MO system.

According to the information communication system using the digital signature system of the present invention having such a configuration, the signature can be confirmed without the need of the public key of the signer. In addition to being able to maintain it, the zero-knowledge proof allows the signature to be verified by simply sending a digital signature from the signer to the confirmer without sending and receiving multiple times between the signer and the confirmer. It is possible to reduce the number of times and eliminate the calculation required for multiple communication. Furthermore, it is possible to use a communication network that can maintain anonymity when performing at least one communication without using a communication network that maintains anonymity even when communicating with the same party many times. it can.

[0061]

First Embodiment FIG. 2 is a diagram for explaining a digital signature system according to the present invention and an information communication system using the digital signature system, and FIG. 3 is a flowchart showing an outline of a processing flow relating to a digital signature.

Step 0 (Preparation): Same as MO system.

Step 1 (User designation and disclosure): Designator i
Selects a user from a plurality of users, that is, the signer j (arrow 201 shown in FIG. 2), and uses the public key v_j of the signer j as a random number r_j.
Z_j which is converted by using
(orr encryption signature) (procedure (1) shown in FIG. 2) and registered in the public database (arrow 202 shown in FIG. 2).

Specifically, the designated person i is a (secret) random number r_j.
Select (r_j ∈ Zq *), find each parameter by the following equation,
Register the signature ((y_j, e_j), z_j) in the public database. x_j = α ^ {r_j} mod p z_j = {v_j} ^ {r_j} mod p e_j = h (x_j, z_j) y_j = r_j + e_j ・ s_i mod q

Step 2 (information pickup): Signer j
From the contents registered in the public database,
Check whether or not the signature ((y_j, e_j), z_j) registered by you is for yourself (procedure shown in Fig. 2
(2), arrow 203). That is, each user confirms the following equation. e_j = h (α ^ {y_j} ・ {v_i} ^ {e_j} mod p, z_j)… (5) z_j = (α ^ {y_i} ・ {v_i} ^ {e_j} mod p) ^ {-s_k} mod p… (6)

Here, x_j = α ^ {y_j} · {v_i} ^ {e_j} mod
Since p holds, x_j will be used hereafter to simplify the notation.

All users can confirm that the equation (5) holds. In addition to that, the signer j can confirm that the expression (6) is also established, and it can be seen that the signer j is selected as the designated person i.

On the other hand, for other signers λ (assuming s_λ ≠ s_j), it is understood that the formula (6) does not hold with its own secret key s_λ, but the formula (6) does not correspond to any other signer. I don't know who else was chosen, because I don't know (if I don't know the private key of another signer, eg s_j).

Step 3 (Signature Generation): The signer j generates a signature for the message m (j) to be signed by the following signature method. Signer j chooses a secret random number r (j) (r (j) ∈ Zq
*), Calculate the following formula. x (j) = {x_j} ^ {r (j)} mod pe (j) = h (x (j), m (j)) y (j) = r (j) + e (j) ・ s_j mod q

Then, (((y_j, e_j), z_j), ((y (j), e
(j)), m (j))) is sent as a signature to the necessary party (procedure (3) shown in FIG. 2, arrow 204).

Step 4 (Signature Confirmation): The confirmer receiving the signature first confirms the equation (5) and then the following equation (procedure (4) shown in FIG. 2). e (j) = h ({x_j} ^ {y (j)} ・ {z_j} ^ {e (j)} mod p, m (j))

If the above can be confirmed, the receiver (confirmer) is convinced that the signature for the message m (j) is the signature generated by the signer j selected by the designator i.

The signature ((y_j, e_j), z_j) of the designator i for z_j obtained by converting the public key of the signer j can be regarded as an anonymous public key certificate.

In the above embodiment, the designator, the signer, and the confirmer can be realized on an information processing device having the capability of information processing and communication, for example, a personal computer. Communication among the designated person, the signer, and the confirmer can be realized by operating a public database or a service that enables anonymous communication on a network such as the Internet.

Then, the above calculation is performed by a device such as a personal computer, and communication is performed on a communication network in which the above service can be used to execute each of the above steps to obtain information using a digital signature. A communication system can be constructed. Of course, not only in the Internet but also in an environment separated from the outside, for example, in a company, it is possible to construct the information communication system using the digital signature by constructing the communication network and the service using the information processing device.

In the above, the anonymous public key certificate is
Although the example of handing over to the signer by registering in the public database has been explained, if many other users do not need to directly confirm whether or not the specified person is actually specifying the signer, the specified person The anonymous public key certificate may be passed directly to the designated signer.

As described above, the information communication system using the digital signature of the present embodiment does not require the public key of the signer unlike the MO system, so that the anonymity can be maintained. Further, since it is not necessary to perform the transmission and reception with the confirmer a plurality of times, it is possible to loosen the requirements for the prerequisite anonymous communication network and reduce the practical cost. Further, since the efficiency of the number of times of communication and the amount of calculation can be improved, it is easy for the user to use and the burden on the user can be reduced.

[0078]

[Second Embodiment] An information communication system according to a second embodiment of the present invention will be described below. In the second embodiment, the same components as those in the first embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted.

In the above-described embodiment, the public key certificate for z_j is generated by using the signature of Schnorr encryption,
The signature of the Schnorr cipher was applied to the message m_j with p, q, x_j, z_j as the public key and s_j as the private key. On the other hand, in the second embodiment, instead of the signature of the Schnorr cipher, the E cipher (TE ElGamal:
"A public key cryptosystem and a signature scheme
based on discretre logarithms, IEEE Transaction on
Information Theory, Vol. IT-31, No. 4, pp.469-47
2, 1985) is applied.

Only the points different from the first embodiment will be described below.

Step 3 (Signature Generation): Signer j generates a signature for message m (j) to be signed by the following method. Signer j chooses a secret random number k (j) (k (j) ∈ Zq *),
Calculate the following formula. r (j) = {x_j} ^ {k (j)} mod ps (j) = (m (j) + s_j ・ r (j)) ・ k (j) ^ {-1} mod (p-1)

Then, (((y_j, e_j), z_j), ((r (j), s
(j)), m (j))) is sent as a signature to the required party.

Step 4 (Signature Confirmation): The confirmer receiving the above signature first confirms the equation (5), and then the following equation. {x_j} ^ {m (j)} ≡ {z_j} ^ {r (j)} ・ r (j) ^ {s (j)} (mod p)

If the above can be confirmed, the receiver (confirmer) is convinced that the signature for the message m (j) is the signature generated by the signer j selected by the designator i.

[0085]

[Third Embodiment] Hereinafter, an information communication system according to a third embodiment of the present invention will be described. In the third embodiment, the same components as those in the first embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted.

In the above-described first and second embodiments, the public key certificate for z_j is generated using the signature of the Schnorr cipher and the message m_j is generated by the Schnorr cipher or
The example of applying the E-cipher has been described. Similarly, NIST (National Institute of Standard a
DSA (Digital Signature Al
gorthm: Eiji Okamoto, Introduction to Cryptography, Kyoritsu Shuppan, pp.136
-138) can be used for the message m_j.

P, q, x_j, and z_j are used as public keys, and s_j is used as a secret key.

Step 3 (Signature Generation): Signer j generates a signature for message m (j) to be signed by the following method. Signer j chooses a secret random number k (j) (k (j) ∈ Zq *),
Calculate the following formula. r (j) = ({x_j} ^ {k (j)} mod p) mod qs (j) = k (j) ^ {-1} ・ (H (m (j))-s_j ・ r (j) ) mod q

Then, (((y_j, e_j), z_j), ((r (j), s
(j)), m (j))) is sent as a signature to the required party.

Step 4 (Signature Confirmation): The confirmer who receives the above signature first confirms the equation (5), and 0 <r (j) <q, 0 <s
(j) After confirming <q, perform the following processing. w = (s (j))-1 mod q u1 = H (m (j)) ・ w mod q u2 = r (j) ・ w mod qv = ({x_j} ^ {u1} ・ {z_j} ^ { u2} mod p) mod q

Then, from the above calculation results, v = r (j) is confirmed, and if confirmed, the receiver can make a signature for m (j) by the signature generated by the signer j selected by the designated person i. Convinced that

[0092]

[Fourth Embodiment] An information communication system according to a fourth embodiment of the present invention will be described below. In the fourth embodiment, the same components as those in the first embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted.

In the above-mentioned first to third embodiments,
The example has been described in which the public key certificate for z_j is generated using the signature of the Schnorr cipher and the Schnorr cipher, the E cipher, or the DSA is applied to the message m_j. On the other hand, instead of the signature of the Schnorr cipher, it is also possible to apply the E cipher to the generation of the public key certificate for z_j. However, x_j
And z_j can be guaranteed to satisfy the relation of
Note that the signature applies. x_j = α ^ {r_j} mod p z_j = {v_j} ^ {r_j} mod p

Specifically, it is as follows. Designated person
i chooses a secret random number r_j for the signer j (r_j ∈ Z
q *), calculate the following formula. x_j = α ^ {r_j} mod p z_j = {v_j} ^ {r_j} mod p S_j = (z_j + s_i ・ x_j) ・ {r_j} ^ {-1} mod (p-1)

Then, ((x_j, S_j), z_j) is the public key certificate. The validity of the public key certificate can be confirmed by the following equation. α ^ {z_j} ≡ {v_i} ^ {x_j} ・ {x_j} ^ {S_j} (mod p) z_j = {x_j} ^ {-S_j} mod p

[0096]

[Fifth Embodiment] An information communication system according to a fifth embodiment of the present invention will be described below. Note that, in the fifth embodiment, configurations that are substantially the same as in the first embodiment are assigned the same reference numerals, and detailed description thereof is omitted.

In the above-described fourth embodiment, the example in which the E-cipher is applied instead of the signature of the Schnorr cipher to the generation of the public key certificate for z_j has been described. On the other hand, Schno
It is also possible to apply DSA instead of rr cipher or E cipher. However, note that the signature is applied so that it can be guaranteed that x_j and z_j satisfy the relation of the following equation. x_j = α ^ {r_j} mod p z_j = {v_j} ^ {r_j} mod p

Specifically, it is as follows. Designated person
i chooses a secret random number r_j for the signer j (r_j ∈ Z
q *), calculate the following formula. x_j = α ^ {r_j} mod p z_j = {v_j} ^ {r_j} mod p S_j = {r_j} ^ {-1} ・ (H (z_j)-s_i ・ x_j) mod q

Then, ((x_j, S_j), z_j) is the public key certificate. The validity of the public key certificate can be confirmed as follows. First, after confirming 0 <x_j <p, 0 <S_j <q, the following processing is performed. w = {S_j} ^ {-1} mod q u1 = H (z_j) ・ w mod q u2 = x_j ・ w mod qv = α ^ {u1} ・ {v_i} ^ {u2} mod p

Then, confirm v = x_j. The validity of the public key certificate can be confirmed by the following equation. z_j = {x_j} ^ {-S_j} mod p

[0101]

[Other Embodiments] Even if the present invention is applied to a system including a plurality of devices (for example, a host computer, an interface device, a reader, a printer, etc.), an apparatus (for example, a copying machine) Machine, facsimile machine, etc.).

Further, an object of the present invention is to supply a storage medium storing program codes of software for realizing the functions of the above-described embodiments to a system or an apparatus, and to provide a computer (or a CPU or M
Needless to say, this can also be achieved by the PU) reading and executing the program code stored in the storage medium. In this case, the program code itself read from the storage medium implements the functions of the above-described embodiment, and the storage medium storing the program code constitutes the present invention. Examples of the storage medium for supplying the program code include a floppy disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM,
CD-R, magnetic tape, non-volatile memory card, ROM, etc. can be used.

Moreover, not only the functions of the above-described embodiments are realized by executing the program code read by the computer, but also the OS (operating system) running on the computer based on the instructions of the program code. It is needless to say that this also includes a case where the above) performs a part or all of the actual processing and the processing realizes the functions of the above-described embodiments.

Further, after the program code read from the storage medium is written in the memory provided in the function expansion card inserted in the computer or the function expansion unit connected to the computer, based on the instruction of the program code, It goes without saying that a case where the CPU included in the function expansion card or the function expansion unit performs some or all of the actual processing and the processing realizes the functions of the above-described embodiments is also included.

When the present invention is applied to the above-mentioned storage medium, the storage medium stores the program code corresponding to the above-mentioned flow chart. Briefly, the memory maps of FIGS. 4A and 4B will be described. Each module shown in the example will be stored in the storage medium. That is, at least the program code of each module of “public information generation”, “signature generation”, “discrimination” and “conversion”, or each module of “bottom generation”, “public key generation”, “signature generation” and “confirmation” is stored. It may be stored in the medium.

[0106]

As described above, according to the present invention,
A digital signature scheme that maintains the anonymity of the signer can be provided.

Further, it is possible to provide the information communication system using the digital signature method in which the number of times of communication is reduced and the calculation associated with a plurality of times of communication is not required.

Further, it is possible to provide an information communication system using a digital signature method using a communication network capable of maintaining anonymity when performing communication at least once.

[Brief description of drawings]

FIG. 1 is a conceptual diagram of an MO system,

FIG. 2 is a diagram for explaining a communication system using a digital signature according to the present invention,

FIG. 3 is a flowchart showing an outline of the flow of processing relating to a digital signature,

FIG. 4A is a diagram showing an example of a memory map of a storage medium storing a program code according to the present invention;

FIG. 4B is a diagram showing an example of a memory map of a storage medium storing a program code according to the present invention.

Claims (16)

[Claims] 1. A public information generating step of generating public information unique to each user from public parameters commonly used by each user and secret information unique to each user; and a secret information in predetermined digital information. A signature generating step of generating signature information corresponding to the digital information by performing conversion using the information and the public parameter; and a correspondence relationship between the digital information and the signature information, the public parameter and the public information. And a conversion step of converting the public parameter and the public information without converting the secret information into a new public parameter and public information capable of generating the signature information, A digital signature system characterized by having. 2. The public information generating step according to claim 1, wherein the public information is generated so that it is difficult to obtain the secret information from the public parameter and the public information. Digital signature scheme. 3. The signature generation step generates signature information corresponding to predetermined digital information using the secret information and the public parameter converted in the conversion step. Digital signature scheme described in. 4. The discriminating step discriminates a correspondence relationship between the digital information and the signature information by using the public parameter and public information converted in the converting step. Digital signature scheme described. 5. A digital signature system in which a result obtained by performing exponential calculation with a secret key of each user as an exponent value for a bottom value commonly used by a plurality of users is a public key of each user, wherein: A base generation step in which a new base is the result of exponential calculation with a random number as the exponent value for the base, and a new public key is the result of exponential calculation with the random number as the exponent value for the public key of a given user. And a public key generation step in which the predetermined user generates a digital signature for arbitrary plaintext by using the private key of the predetermined user, and the base generation step and the public key generation step. A digital signature system, which comprises a confirmation step for confirming the validity of the digital signature generated in the signature generation step using the generated base and the public key. 6. The digital signature system according to claim 5, wherein security is based on the difficulty of obtaining the discrete logarithm. 7. Schnorr signature scheme and / or ElGamal
7. The digital signature system according to claim 6, wherein it is difficult to obtain the discrete logarithm by using a signature system and / or a DSA system. 8. Designating means for designating a generating means for generating a digital signature, and using at least one digital signature method, whether or not the target digital signature is generated by the generating means designated by the designating means. An information communication system comprising a confirmation means for confirming whether the digital signature scheme is one of the digital signature schemes.
An information communication system characterized by being a digital signature system described in any one of 1. 9. A designating means for designating a signature generating means for generating a digital signature by using a first digital signature method in which security is based on the difficulty of obtaining a discrete logarithm, and claim 5 An acquisition unit that obtains a new base and a new public key by the second digital signature method described in any one of Item 7, and a new base value that is obtained by the acquisition unit. A first generation means for generating a first digital signature for the new public key by the first digital signature method, wherein the digital signature obtained by the first generation means is
An information communication system, characterized in that it is proof that a signature generation means having a secret key corresponding to the new public key obtained by the acquisition means has been designated. 10. The apparatus further comprises second generating means for generating a second digital signature for arbitrary plaintext by using the new base and the new public key obtained by the obtaining means. The information communication system according to claim 9. 11. A first confirmation means for confirming the validity of the first digital signature by using a public key of the first digital signature method, and the validity is confirmed by the first confirmation means. Second confirmation means for confirming the authenticity of the second digital signature using the bottom and public key, and the target digital signature based on the confirmation results obtained by the first and second confirmation means. 11. The information communication system according to claim 10, further comprising: a determination unit that determines whether or not is generated by the signature generation unit designated by the designation unit. 12. The Schnorr signature method and / or the ElGamal signature method and / or the DSA method is used as the first digital signature method.
13. The information communication system according to claim 11. 13. A designation means for generating a first digital signature according to a first digital signature method for designating a means for generating a signature, and based on the first digital signature generated by the designation means. A signature generating means for generating a second digital signature by a second digital signature method, and a signature generating means for designating the second digital signature by the designating means based on the first and second digital signatures. And a confirmation means for confirming whether or not the information communication system is generated by the information communication system. 14. A computer-readable memory storing a program code relating to a digital signature, wherein public information unique to each user is obtained from public parameters commonly used by each user and secret information unique to each user. A code of a public information generating step to be generated, and a code of a signature generating step for generating signature information corresponding to the digital information by applying conversion using the secret information and the public parameter to predetermined digital information, A code of a determination step of determining the correspondence between the digital information and the signature information using the public parameter and the public information, and converting the public parameter and the public information without converting the secret information. , New public parameters and public information that can generate the signature information. A computer-readable memory, characterized in that it comprises a code conversion step of the. 15. A program code of a digital signature method in which a result obtained by performing exponential calculation with a secret key of each user as an exponent value for a bottom value commonly used by a plurality of users is a public key of each user is stored. A computer readable memory, wherein the base generation step has a new base that is the result of exponential calculation using a random number as the exponent value for the base, and the random number is exponential for the public key of a predetermined user. A code of a public key generation step in which a new public key is a result of index calculation as a value, and a signature generation step in which the predetermined user generates a digital signature for arbitrary plaintext by using his / her own private key. And the bottom and the public key generated by the bottom generation step and the public key generation step, the digital code generated in the signature generation step. A computer-readable memory, characterized in that it comprises a code confirmation step of confirming the validity of the name. 16. A computer readable memory in which a program code of an information communication system using a digital signature system is stored, wherein a first digital signature system is based on the security of difficulty of obtaining discrete logarithm. Obtaining a new bottom and a new public key by the code of the specifying step for specifying the signature generating means for generating the digital signature, and the second digital signature method according to any one of claims 5 to 7. Using the code of the step and the new base value obtained in the obtaining step, a first generation for producing a first digital signature for the new public key obtained in the obtaining step by the first digital signature scheme. A computer readable memory, comprising: