JPH11338346A - Anonymous communication method and apparatus and program recording medium - Google Patents

Abstract

(57) [Summary] [Problem] Voting message m by electronic voting, for example_jRun
The verification processing amount does not depend on the number of nodes to be replaced.
You. SOLUTION: Sender S_jIs m_jTo encrypt the bulletin board 1
1 and the encrypted message E₀₁, ..., E_1nNo
De P₁To P₁Is E_iIs a random number r_iAnd randomize
Further random substitution E_ij= E '_{1Ri (j)}And E₁₁~ E_1nTo
P_TwoTo each P _iPerforms the same processing sequentially, and the last P
_mIs E_m1, ..., E_mnTo the bulletin board. P_iIs E_mj= R
(E_{0Ri (j)}, R '_j) R ’_jAnd the replacement P_iExists
A proof Pp is created in cooperation, and if Pp is invalid, each P
_iIs all r used in the calculation_jAnd P_iAnd P_i-1Received from
Publish all the values you did. If the published value matches the normal calculation
If a node that does not match is found, the
Repeat the process once again. If Pp is correct, it will be published.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an anonymous communication method applied to communication capable of verifying a result while maintaining anonymity when, for example, conducting a questionnaire survey or voting via a telecommunication device. The present invention relates to the device and the program recording medium.

[0002]

2. Description of the Related Art At present, voting using a physical medium, that is, a ballot paper, keeps anonymity by putting a ballot paper in an opaque ballot box so that the ballot box cannot be opened until counting. By locking the key, loss is prevented, and at the time of counting, counting is performed under the supervision of multiple people to maintain the validity of the result.

In a system via a telecommunication device,
As a method that can verify the validity of the result while maintaining the anonymity, for example, the paper “Receipt-free mix-type voti
ng scheme-a practical solution to the implementati
on of a voting booth- ”, Eurocrypt'95, vol.950 of
There is a method shown in LNCS, page 393-403, Springer-Verlag.

According to this method, a set of encrypted messages is partially decrypted by each node, and after being replaced at random, is sent to the next node, and the same processing is sequentially performed until the last node. By doing so, a decoding result that is finally randomly substituted is obtained. In this method, each node creates a certificate certifying the validity of each operation, thereby proving the anonymity as a whole and the validity of the result. That is, each node proves by the zero-knowledge proof that the output of the node is a random permutation of the partial decoding result of the input of the node without revealing the actual permutation order. Anonymity is maintained as long as the random permutation used by each node is kept secret.

[0005]

According to the above conventional method,
The verifier must sequentially verify the zero-knowledge proof by each node, and the amount of calculation required for the verification increases in proportion to the number of nodes. In an election via an electronic communication device, it is expected that many general voters who do not have a powerful electronic computer will be verifiers, so that it is desired that the amount of calculation required for verification be small.

According to the present invention, the amount of calculation required for verification is kept constant irrespective of the number of nodes, and a verifier having a less powerful computer environment can perform verification in a short time.

[0007]

[MEANS FOR SOLVING THE PROBLEMS] An anonymous communication network is randomly placed.
Exchange node device P₁~ P_mAnd decryption node device D₁~ D_kOr
It consists of. Each decoding node device D_iIs the public key KP_iAnd
And secret key KS_iHold. Predefined encryption key synthesis function
Regarding FP () and decryption key synthesis function FS (), KP
= FP (KP₁, ..., KP_k), KS = FS (KS₁,
…, KS_kPublic encryption of KP and KS
Key and decryption key. Message sender device S_jIs Messe
Page m_jIs encrypted by KP and sent to the bulletin board device. Posted
The display panel device sends messages according to conditions such as a predetermined deadline.
The deadline for accepting applications is closed. The bulletin board device is an encrypted message
The E₀₁, ..., E_0n Random replacement node with signature
Place P ₁Send to Random replacement node device P₁Is in advance
The determined randomization function R () is E_iAnd random number r_iIn order
Next input, output E '₁₁, ..., E '_1nGet. More run
Dam replacement function R_iBy E_1j= E '_{1Ri (j)}As order
And its output E₁₁, ..., E_1nThe following along with the signature
Node device P_TwoSend to Each random replacement node device
Performs the above-described processing, and the last random replacement node device P_m
Is the output E_m1, ..., E_mnTo the bulletin board device.

Next, each node device P _i has E _mj = R (E
_{0Ri '(j), r j} ') comprising a random number r _j 'substituted R _i' is created in collaboration proof Pp of the presence. If the proof Pp is invalid, each node device _Pi publishes all random numbers r _j and R _i used in the calculation and all values received from the _immediately preceding node device P _i-1 . If a node device that refuses disclosure or a node value whose published value does not pass a normal calculation is found, the node device is excluded and the process after the message reception deadline is repeated again. If the certification Pp is correct, the certification Pp is disclosed to the bulletin board device.

The decryption node device verifies the published proof Pp, and if the proof Pp is invalid, finds an invalid node device by means similar to the above, and causes the random replacement node device to execute the calculation again. If proof Pp is correct, the decoding node device D _i by the decryption key KS _i of each node device, E
_m1, ..., decodes the E _mn, D _i1, ..., get a D _in. Each decoding node device combines the outputs of all the decoding node devices by a function C () to obtain one decoding result D ₁ ,..., D _n . After disclosing D ₁ ,..., D _n to the bulletin board device, each decryption node device cooperates to prove that the combined decryption result is equivalent to the decryption result using the decryption key KS. This proof Pd after being verified by the node devices D _i, is published in the bulletin board apparatus.

The external verifiers are E ₀₁ ,..., E _0n , E _m1 ,
_{..., E mn, D 1,} ..., to get the D _n from the bulletin board system, P
Verify that p and Pd are correct.

[0011]

DESCRIPTION OF THE PREFERRED EMBODIMENTS ElGamal as an encryption function
An embodiment of the present invention will be described using encryption. FIG. 1 shows the system configuration of this embodiment. As common parameters,
Large prime p such that p = 2q + 1 for large prime q
And the origin g of the subgroup G _q created by _q is disclosed. All calculations in the following description take mod p unless otherwise specified. Each decoding node device D
_i (i = 1, 2,..., m) are a secret key X _i and a public key Y
to generate the _i = g ^ X _i. A ^ B represents the A ^B. From the public key Y _i for all decoding node device _{D i, Y = Y 1 ·} Y 2 ...
Create and publish encryption key Y as Y _m. At this time, the decryption key X corresponding to the encryption key Y is X = X ₁ + X ₂ +... + X _m
As long as the mod q, and the total decoding node device D _i does not reveal the private key X _i, which decode the node device D _i nor learned the value of the decryption key X.

Each message sender device S_j(J = 1,
2, ..., n) is the message m_j<P is G_qElements of
And a random number r_0jE using_0j= (M_0j,
G_0j) = (M_j・ Y ＾ r_0j, G ＾ r_0j) And calculate
Message m_jAnd send it to the bulletin board device 11
You. The bulletin board device 11 is a sender device S_jAuthentication
Sender device S determined _jOnly receives write requests from
Attach. All data E written_0jIs released sequentially
It is. Anyone can perform read access to bulletin board device 11
Data E_0jIs the bulletin board device 11
The entity that performed the read access with the signature
(Read requester).

[0013] It is assumed that n messages have been posted at the time when the reception of the message is closed according to a predetermined rule. The random permutation node device P _i (i = 0,
, M) perform the following random replacement procedure. As shown in FIGS. 2 and 3, the random replacement node device P
₁ is an E ₀₁ ,
.., E _0n are read (S1) and initialized to i = 1. The device P ₁ generates a random number r _1j from the random number generation unit 202 and calculates E ′ _1j = (M _0j · Y ・ r _1j , G _0j · g ・ r _1j ) (1) in the randomization unit 203. To randomize the data (M _0j , G _0j ). Further, a random permutation function R _{1 is} generated by the random permutation unit 204.
In replacement order 'to _1j E _1j = E' encrypted data E as _{1Ri (j) ··· (2)} , the output E _11, ..., the signature the signature portion 205 of the device P ₁ and E _1n for this give and sent from the transmission unit 206 to the next node P _2. Hereinafter, each random permutation node P _i generates a random number r _ij (S3), and E ′ _ij = (M _{i−1, j} · Y r _ij , G _{i−1, j} · g r _ij ) -(3) is calculated (S4). Further, the order is _switched by the random permutation function R _i as E _ij = E ′ _{iRi (j)} (4) (S5).
6), the outputs E _i1 ,..., E _in are sent together with the signature to the next node P _{i + 1} (S7), i is incremented by 1, and the process returns to step S3 (S8).

Each of the random permutation node devices P _i performs the above processing, and the last random permutation node device P _m sends the outputs E _m1 ,..., E _mn to the bulletin board device 11 (S9).
Next, the random replacement node device P _i proved cooperate P
Perform the following proof procedure to issue p: That issue cooperatively proof Pp of having the correct processing (random permutation process shown in FIG. 3) without the device P _i is for each fraud.

Device P₁Is a random number t_1j, And T ′_1j= (M_0j・ Y @ t_1j, G_0j・ G @ t_1j) (5) is calculated. Furthermore, a random permutation function w₁By T_1j= (U_1j, V_1j) = T '_{1, w1 (j)} .. (6) the order is changed and the output T₁₁, ..., T_1nThe equipment
P_TwoSend to Similarly, device P_iIs T '_ij= (U_{i-1, j}・ Y @ t_ij, V_{i-1, j}・ G @ t_ij) (7) is calculated, and a random replacement function w is calculated._iSwap order by
The output obtained is sent to the next device P._{i + 1}Send to Last node device
Place P_mIs T_m1, ..., T_mnIs sent to the bulletin board device 11.
That is, the random number r_ijInstead of t_ijAnd the replacement function R_iof
Instead, the replacement function w _iUsing the same laser as shown in FIG.
Perform random replacement processing.

Here, the permutation synthesis w′i (j) is wi · w
i + 1 ... wm (j), especially w'i (j)
Is w1 ・ W2 .., Wm (j), if all T _mj are created correctly, then t _j = t _{1, w1 ... wm (j)} + t _{2, w2 ... wm (j)} +. + T _{m, wm (j)} (8), U _mj = M _{0, w ′ (j)} · Y ＾ t _j (9) and V _mj = G _{0, w ′ (j)} · g ＾ t _j (10) holds.

The establishment of (9) can be explained as follows. Ma
, Random replacement node device P₁The output of U_1,j = M_{O, w1 (j)}・ Y @ t_{1, w1 (j)} And the following node device P_TwoThe output of U_{2, j}= U_{1, w2 (j)}・ Y @ t_{2, w2 (j)} = M_{0, w1w2 (j)}・ Y ＾ (t_{1, w1w2 (j)}+ T_{2, w2 (j)})  Becomes Therefore, the node device P_mThe output of U_{m, j}= M_{0, w1w2 ... wm (j)}・ Y ＾ (t_{1, w1 ... wm (j)}+ T_{2, w2 ... wm (j)}+ ... + t_{m, wm (j)} ) = M_{0, w '(j)}・ Y @ t_j  And equation (9) holds. Equation (10) is exactly the same
Explained.

Furthermore, the R _i ^-1 as an inverse permutation function of ^{_{R i, R i -1 · R}} i-1 -1 ... R 1 · w 1 ... w i-1 · w i the z _'i (j) expressed in, if all of the E _mj has been created _{correctly, s j = t 1, w1} ... wm (j) -r 1, w1 ... wm (j) + ... + t i, wi .. _{.wm (j) -r i, z'i} -1 w i ... w m (j) + ... + t m, wm (j) -r m, z'm-1 · wm (j) (mod q ) (11), U _mj = M _{m, z'm (j)} · Y ＾ s _j (12) and V _mj = G _{m, w'm (j)} · g ＾ s _j ... (13) holds. The establishment of equation (12) can be explained as follows. First, as in the case of U _{m, j} , M _{m, j} is given by M _{m, jj} = M _{0, R1... Rm (j)} · Y ・ (r _{1, R1... Rm (j)} +
_... + rm _{, Rm (j)} ). Therefore, M _{m, z} ′ _{m (j)} = M _{0, R1... Rmz} ′ _{m (j)} · Y ＾ (r _{1, R1... Rmz} ′ _{m (j)} + _... + _{Rm, Rmz} 'M _{(j )} ) = M _{0, R1 ... Rm} · _Rm ^-1 _{... R1} ^-1 · _{W1 ... Wm (j)} · Y ＾ (r _{1, R1 ... Rm} · _Rm ^-1 _{... R1} ^-1 · _{W1 ... Wm (j)} + _... + rm _{, Rm} · _Rm ^-1 _{... R1} ^-1 · _{W1 ... Wm (j)} ) _... = M _{0, W1 ... Wm (j)} .Y ＾ (r1 _{, W1 ... Wm (j)} + _... + rm _{, zm- 1.wm (j)} ). Therefore, U _{m, j} / M _{m, z} ′ _(j) = M _{0, W1 ... Wm (j)} · Y ＾ (t _{1, W1 ... Wm (j)} + _... + _{tm, wm (j)} ) / M _{0, W1 ... Wm (j )} · Y ＾ (r _{1, W1 ... Wm (j)} + _... + rm _{, zm-1} · _{wm (j)} ) = Y ＝ (t _{1, w1 ... Wm (j)} −r _{1 ) , W1 ... Wm (j) +} ... + t m, wm (j) -r m, zm-1 · w m (j)) = Y ^ s j , and the equation (12) holds. Equation (13) can be explained in exactly the same way.

[0019] After a random permutation processing using the random number r _ij as shown in FIG. 4 (S1), performs random permutation processing using the random number t _ij (S2), from each subsequent unit P _i BBS device 11 T _m1 ,..., _Tmn are read (S3), and c = h ( _Tm1 ,..., _Tmn ) (14) is calculated using a predetermined one-way function b (S4). c has a value of 0 or 1 with equal probability, according to its value, unit P _i performs the following processing. c
= 0 (S5) The device P _i calculates e _i = h (t _i1 ,..., T _in , w _i ) (15) and publishes e _i . That is, it is sent to the bulletin board device 11 (S6). After all of the equipment P _i has published the e _i, each of the devices P _i is t _i1, ..., t _in, to publish the w _i (S7), is e _i, which is published from all of the other node devices P _i It is verified whether e _i = h (t _i1 ,..., t _in , w _i ) (16) is satisfied (S8). If there is a node device that has released data that does not satisfy the above expression, the node device is excluded (S9), and the process returns to step S1 to execute the processing after the message reception deadline again. All e _i
If the correct _{(S8), t j = t} 1, w'1 (j) + t 2, w'2 (j) + ... + t m, w'm the _{(j) mod q ··· (17} ) computes (S10), U _mj = M _{0, w'm (j)} · Y ＾ t _j (18) and V _mj = G _{0, w'm (j)} · g ＾ t _j (19) ) Is verified (S11). That is, in this verification, the input of the first node device P _{1 and} the input of the last node device P 1
_a random number t _j connecting outputs from _m and a random permutation w ′ ₁
Is confirmed by actually calculating t _j , w ′ _i . If this check cannot be performed, that is, if the above formula is not satisfied, the input / output of each node device is expressed as U _ij / U _{i−1, w′i (j)} = Y ＾ t _{i, w′i (j).} (20) It is verified whether or not V _ij / V _{i−1, w′i (j)} = g ＝ _{ti, w′i (j)} (21) (S12). If there is a node device that has released data that does not satisfy the verification, the node device is excluded (S9), and the process returns to step S1 to execute the process after the message reception is closed again.

If all verifications pass, T _m1,.
mn , t ₁ ,..., t _n are set as certificates (S13). As described above, T _ij is generated by so-called commitment generation processing without _displaying the random number r _ij in a table, a challenge c is generated in response thereto, and t ₁ ,
.., T _n can be obtained. If c = 1 (S5),
The device P _{1 transfers} z ₁ ′ = R ₁ ⁻¹ _w1 (22) s _1j = t _{1, w1 (j)} −r _{1, w1 (j)} mod q (23) to the device P ₂ Send it. Similarly, the devices P _i is ^{_{z i '= R i -1 Z}} i-1'w i ··· (24) s ij = s i-1, wi (j) + t i, wi (j) -r _{i, zi−1} ′ · _{wi (j)} mod q (25) is sent to the next device P _{i + 1} (S14). The last node device P _m discloses s _mj and z ′ _m (S15). Here, if correct all devices, P _m is published s
_mj is equal to s _j in equation (25). this is,
This is clearly established from the equations (11) and (25).

In each node device, the values disclosed by the device P _m are expressed as follows: U _mj = M _{m, z'm (j)} · Y ＾ s _mj (26) and V _mj = G _{m, z'm ( j)} · g ＾ s _mj (27) It is verified whether or not the following _expression is satisfied (S16). If the above expression is not satisfied, the values of the node devices are expressed as U _ij = M _{iz'i (j)} · Y ＾ s _ij (28) and V _ij = G _{i, z'i (j)} · g It is verified whether or not ＾ s _ij (29) is satisfied (S17). If there is a node device that has published data that does not satisfy the above expression, the node device is excluded (S18), and the process returns to step S1 to execute the processing after the message reception is closed again.

If all verifications pass, T_m1, ..., T
_mn, S₁, ..., s_nAs a certificate (S19). the value of c
If can be predicted in advance, the verification formula in the above process is satisfied.
It is easy to create such illegal data. Predict
The probability that the value of C actually occurs is 1/2, so
If the order is repeated, for example, 40 times, all predictions will be hit
Probability is 2 ^-40And it can be considered almost impossible.
Therefore, the above certification procedure is performed a predetermined number of times (40 to 80).
Repeat) Alternatively, perform the processing for the number of repetitions in parallel.
After executing all the certificates issued, one certificate Pp
Published on the bulletin board.

Since the node device for which the verification is not established in the above-described processing is excluded from the processing, for example, the processing in which the processor is out of order is removed and the correct processing is performed.
After the certificate Pp is published, all decryption node devices verify Pp. That is, U _mj = M _{0, w′m (j)} · Y ＾ t _j , V _mj =
G _{0w'm (j)} · g ＾ t _j is satisfied or U _mj = M _{mz'm (j)} · Y
It is _{checked whether or not} ＾ s _mj , V _mj = G _{n, z′m (j)} · g ＾ s _mj is satisfied. If Pp is invalid, the random replacement node device re-executes the process or stops.

As shown in FIG. 5, when Pp passes the verification (S1), the decoding node device executes the following decoding procedure. i = 1, H ₀ = 1 and initialized (S2), the node apparatuses D ₁ calculates the _{H i = G mi ^ X 1} ··· (30), sent to the next device D _2. Similarly device D _i calculates the _{H ij = H i-1,} j · G mj ^ X j ··· (31), that is to perform some decoding processing (S3), i
If not k (S4), _Hij is sent to the next device _{Di + 1} (S5). Thereafter, i is incremented by 1 and the process returns to step S3 (S6). If i = k in step S4, the last decoding node device D _k sends H _ki to the bulletin board device 11 (S
7).

Next, in order to issue a certificate Pd that all the node devices have correctly processed, that is, each H _ki is correct, as shown in FIG. Perform the steps. First, i = 1, F ₀ = 1, R
_0j = 1 and initialized (S1), the decoding node apparatuses D ₁ generates a random number a ₁ (S2), calculating the F ₁ = g ^ a ₁ and _{R 1j = G mj ^ a 1} ··· (32) It is sent to the next of the device D ₂ in. The same applies to the device D
_i calculates F _i = F _i−1 · g ＾ a _i and R _ij = R _{i−1, j} · G _{mj Ｇa i} (33) (S3), and if i = k, S4), F _j, sends the R _ij to the next device D _{i + 1} (S5). i is incremented by 1, and the process returns to step S2 (S6). If i = k, the last decoding node device D _k sends F _k and R _kj to the bulletin board device 11 (S7).

Each of the decryption node devices transmits information from the bulletin board device 11 to F
_k , R _kj and H _kj are read (S8), and these and the public key Y are read.
A one-way function calculation _{c = h (Y, F k} , H k1, R k1, ..., H kn, R kn) performs ··· (34) (S9). i = 1, b ₀ = 0, c (S10), the apparatus D ₁ calculates b ₁ = a ₁ −c × X ₁ mod q (35) and sends it to the apparatus D ₂ . The following Similarly apparatus D _i is _{b i = a i -c · X} i + b i-1 mod q ··· (36) and the calculated (S11), i = k unless (S12), b
_i is sent to the device _{Di + 1} (S13), i is incremented by 1, and the process returns to step S11 (S14). If i = k, the last decryption node device D _k sends b _k to the bulletin board device 11 (S15).

[0027] If each decoding node device D _i is working _{properly, F k = g ^ b k} · Y ^ c ··· (37) and _{R kj = G mj ^ b k} · H kj ^ c ··· ( 38) is satisfied. Furthermore, with respect to input and output of each decoder node device _{D i, F i = g ^} (b i -b i-1) Y i ^ c ··· (39) and _{R ij = G mj ^ (b} i -b i _-1 ) · (H _ij / H _{i-1, j} ) ＾ c (40)

Each decoding node device D_iFirst, F_k= G ＾
b_k・ Y ＾ c and R_kj= G_mj＾ b _k・ H_kjVerify ＾ c
(S16), and if so, Y, F_k, H_k1,
R_k1, ..., H_kn, R_knAnd b_kAs a certificate Pd
Open (S17). If the above verification formula does not hold,
Decryption key X used to issue certificate Pd_iAll information except
Open to each node device D_iCheck the input and output of
Proof, F_i= G ＾ (b_i-B_{i- 1}) ・ Y_i＾ c, R_ij= G
_mj＾ (b_i-B_i-1) ・ (H_ij/ H_{i-1, j}Holds
And detects a decryption node device that has performed an illegal operation.
(S18).

[0029] After the verification is passed, decrypting node device D _i is 'calculates the _{j = M kj / H kj ···} (41), m as a decoding result' m publishing _j (S1
9). The external verifier device V is Pp, Pd and m ′ _j = M
Verify that _kj / _Hkj holds.

The functional configuration of the random replacement node device is shown in FIG.
As described above, as described above, the message E _i starting from the message E _0j of the bulletin board device 11 using the random number r _ij from the random number generation unit 202 and the public key Y and the public information g is used. _{-1, j} is randomized by the randomizer 203,
Furthermore it sends replaced the sequence at random permutation unit 204 to the next node device P _{i + 1} from the transmitter 206 as E _ij.

A permutation cooperative proof means 220 is provided. In this means 220, a random permutation processing section 221 similar to the random permutation processing section 210 uses a random number t instead of a random number r _ij.
processed by _ij . An operation is performed by the one-way function operation unit 222 using the data T _mj released by the random replacement processing unit 221 of the last node device P _m as a variable, and the control unit 250 determines whether the operation result c is 0 or 1. Done in c = 0
Random number t _i1 as the processing in the case of, ..., t _in, the permutation function w
_i is input to the one-way function calculator 223 and calculated,
e _i is output and published. Further, random numbers t _ij and w _i are also made public, and thereafter, e in other random permutation node devices is used.
_i and t _ij, expression in the relationship of w _i is e _i verification section 224 (16)
Is further verified by the t _j calculating unit 225, and the U _mj and V _mj verifying units 226 verify that the expressions (18) and (19) are both satisfied. If this verification is passed, the node input / output verification unit 227 uses the expression (2)
It is verified that both 0) and equation (21) hold. The control unit 250 determines which process is to be performed next based on various verification results. Certificate P that passes all verifications
The P is issued by the Pp certificate issuing unit 228.

When c = 1, the s _ij , z ′ operation unit 231 performs the operations of the expressions (24) and (25), and the U _mj and V _mj verification units 232 _{execute the} expressions (26) and (27). ) Is verified. If the verification fails, the U _ij and V _ij verification unit 233 verifies whether Expressions (28) and (25) are satisfied. If all the verifications pass, the Pp certificate issuing unit 228 issues the certificate Pp.

The storage unit 240 stores various kinds of public information and temporarily stores the read data, holds generated random numbers, and the like. The control unit 250 determines the various verification results as described above, performs the next processing based on the results, reads / writes to / from the storage unit 240, and transmits various data to the next node device P _{i + 1} or the bulletin board device 11 through the transmission unit 206. In addition, it sequentially controls each part. Note that U
_mj , V _mj verification units 226 and 232, node input / output verification unit 2
27, the U _ij and V _ij verification unit 233 constitute a replacement verification unit 235.

FIG. 7 shows a decryption node device D._iFunction configuration example
Show. Various kinds of public information and a reading unit 311 are stored in the storage unit 310.
Data, random numbers, and generated data
Used for holding. In the Pp verification unit 312, the expression (18)
And Equation (19) or Equation (26) and Equation (27)
And the partial decoding unit 313 calculates
Part of the decoding process is performed, and as a result H_ijIs the transmission unit 314
The next node device D _{i + 1}Sent to

The random number a from the random number generator 315_iIs generated
And this random number a_iUsing F_iArithmetic unit 316, R_ijPerformance
Equation (33) is calculated by the arithmetic unit 317, and F_i, R_ijSent
Next node device D from unit 314_{i + 1}Sent to Bulletin board
F read from device 11_k, R _kjAnd using public key Y
Equation (34) is calculated by the directional function calculation unit 318, and the
Using the calculation result c, b_iExpression (36) is performed by the arithmetic unit 319.
And the result b_iIs the next node device b_iSent to
You. F_k, R_kjExpressions (37) and (38) in the verification unit 320
Is verified whether it holds, and if it passes, Pd certificate
The certificate issuing unit 321 issues and sends a certification Pd. Part 31
In FIG. 6, the unit 321 constitutes the decryption cooperation certification means 330.
You.

The decoding operation unit 331 decodes m _j by the operation of the expression (41), and the unauthorized node detection unit 332 performs the operations of the expressions (39) and (40) to detect an illegal node device. Units 320 to 332 are decryption verification means 340
Is composed. The control unit 350 determines the verification results of the various verification units, and performs a process based on the determination in each unit.
It performs reading and writing to the storage unit 310, reading by the reading unit 311, transmission of each data to the next node device _{Di + 1} , and the bulletin board device 11, and sequential processing of each unit.

Random permutation node device, decoding node device
Read the program by the computer,
By performing decryption, it is configured to function
It can also be done. Decryption node device D₁~ D_kIs orchid
Dam replacement node device P₁~ P _mAs a subset of
You can also. That is, one decoding node device and one
Of random replacement node devices with common processor
And independent decoding node devices and random permutation
It may be configured to function as a node device.

The random replacement node device prepares a plurality of sets of nodes, and performs random replacement, certificate generation, and the like in cooperation with one set as described above. If the verification of the certificate by the decryption node device is unsuccessful due to damage to the processor of the pair, use another pair of nodes to re-perform random replacement, certificate generation, etc. Can also be configured.

[0039]

Effects of the Invention According to the cooperative certificate issuing procedure shown in the above embodiment, the certificate issued Pp is T _m1, ..., T _mn and s _1, ..., s _n or t _1, ..., t consists become more data is _n, it depends on the number n of the message m _j, does not depend on the number of random replacement node device P _i. Similarly, the certificate Pd
_{Y, F k, H k1,} R k1, is ..., H _kn, consists R _kn and b _k, depending on the number of messages m _j, independent of the number of decoding the node device D _i. Therefore, the external verifier device can verify Pp and Pd with a calculation amount independent of the number of nodes.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a system configuration according to an embodiment of the present invention.

2 is a block diagram showing a functional configuration example of the random replacement node device P _i of the present invention.

FIG. 3 is a flowchart showing a procedure of a random replacement process in the method of the present invention.

Figure 4 is a flow diagram illustrating an example of a processing procedure in the random replacement node device P _i.

FIG. 5 is a flowchart showing a part of a decoding procedure in the method of the present invention.

FIG. 6 is a flowchart showing an example of a procedure for issuing a certificate Pd of a decryption node.

FIG. 7 is a block diagram showing a functional configuration of a decoding node device according to an embodiment of the present invention;

────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] June 9, 1998

[Procedure amendment 1]

[Document name to be amended] Statement

[Correction target item name] Claim 8

[Correction method] Change

[Correction contents]

Claims (15)

[Claims] 1. An anonymous communication method in which a plurality of message senders publish anonymous messages on one bulletin board device by publishing an anonymous message. A plurality of random replacement node devices P _{1 to} P _m and decryption node devices D _{1 to} D _k are connected. A first step in which each sender S _i sends a message E _j encrypted by the sender device to the bulletin board device; and all the messages received by the random replacement node device P ₁ in the bulletin board device are received. After randomizing E _j , a second step of randomly permuting and outputting the message order, and the random permutation node devices P _{1 to} P _m cooperate to output the last random permutation node device P _m The third step of creating a certificate that proves that it is the result of randomization and replacement of the input message from all senders, and the certificate output in the third step A fourth step of the decoding node device verifies, in the fifth step of the decoding node device D _i is partial decoding randomized encrypted message, the calculating the result of the entire decoded from the result of the partial decoding Six steps, and confirming that the decryption has been correctly performed by the decryption node devices D _{1 to} D _k
An authentication method comprising: a seventh step of cooperating proofs; and an eighth step of each of the decryption node devices verifying the proof output in the seventh step. 2. The anonymous communication method according to claim 1, wherein when the verification in the fourth step is unsuccessful,
By each random replacement node device P ₁ to P _m is the information used in the second step, the random replacement node device P ₁ to P
Anonymous, characterized by identifying the replacement node device that has output an invalid result by verifying each input / output data of _m , and performing the second to fourth steps again without using the invalid node device. Communication method. 3. The anonymous communication method according to claim 1, wherein the verification in the eighth step is unsuccessful.
Each decoding node device D ₁ to D _k exposes all information except for the decryption key used in the seventh step, the proof of the decryption node devices D _i in the seventh step is decoding the node device in the fifth step by verifying whether a certificate for the input-output relation of D _i, to identify the decoding node device which has output the incorrect results, rerun die five to eight steps without unauthorized node device An anonymous communication method characterized by: 4. The anonymous communication method according to claim 1, wherein the decryption node devices D _{1 to} D _k are random replacement node devices P.
Anonymous communication method which is a subset of the ₁ to P _m. 5. The anonymous communication method according to claim 1, comprising a plurality of node sets as a random replacement node device, wherein the second to fourth steps are executed using one node set, An anonymous communication method characterized by re-executing the second to fourth steps using another set of nodes when the verification in the fourth step is unsuccessful. 6. A storage unit for storing public information and the like, a random number generating unit, a randomizing unit for randomizing an encrypted message from a bulletin board device by using a random number, and a random order of the randomized message. First random replacement processing means comprising random replacement means, second random replacement processing means for randomizing and random replacing the encrypted message with another random number, and data based on the processing of the second random replacement processing means , A proof verification unit for verifying that a plurality of random replacement node devices cooperate to create a certificate, and data based on the processing of the second random replacement processing unit. Node verification means for verifying data; reading means for reading required data from a bulletin board device; Transmitting means for transmitting each processing data of the random replacement processing means to the next random replacement node device, and transmitting other data to the random replacement node device or the bulletin board device; determining the next processing based on various verification results; A random permutation node device comprising: a control unit that performs reading / writing to a storage unit, order processing of each unit, and the like. 7. The random permutation node device according to claim 6, wherein a first function operation unit that performs a predetermined function operation on a processing result of the second random permutation processing unit of the last random permutation node device; Means for executing the first processing means or the second processing means in accordance with the calculation result of the first function calculation means; and the first processing means preliminarily performs the random number and the replacement function used in the second random replacement processing means. Second function operation means for performing a predetermined function operation, operation verification means for verifying the operation of the second function operation means for other random permutation node devices, and the operation verification means passing for all random permutation node devices Then, means for verifying the existence of a random number and a permutation function relating the input of the first random permutation node device and the output of the last random permutation node device The second processing means is a random number associating means for associating the random numbers used in the first and second random replacement processing means, respectively, and the random number of the last random replacement node device. Means for verifying whether or not a verification formula for associating both output data of the first and second random replacement processing means of the last random replacement node device with the value of the association means is established. A random permutation node device as a means. 8. The first processing means includes means as the node verification means for verifying whether input data and output data of the second random replacement processing means of each random replacement node device have a predetermined relationship. Wherein the second processing means includes means as the node verification means for verifying whether both output data of the first and second random replacement processing means of each random replacement node device have a predetermined relationship. Random replacement node device. 9. A storage unit for storing a decryption key, public information, etc., a proof verification unit for verifying a proof Pp created by a random replacement node device, and a partial decryption of information including a part of an encrypted message with a decryption key. Partial decryption means for performing processing; decryption operation means for decrypting an encrypted message using the processing result of the partial decryption means; and decryption for generating a proof that decryption has been correctly performed in cooperation with another decryption node device. Cooperative certification means, transmission means for transmitting data to the next decryption node device or bulletin board device, reading means for reading data from the bulletin board device, and means to be processed based on the verification result are determined and processed. Or to transmit the processing result data to the next decoding node device or bulletin board device by the transmitting means, to sequentially process each unit, or to read / write the storage means. Decoding node device and a control unit. 10. The decryption node device according to claim 9, wherein the decryption cooperative proof means comprises: a random number generation means; a public information randomizing means for randomizing public information by using a random number and associating the public information with another decryption node apparatus; Information of the public information randomization means of the last decryption node device, function operation means for performing a predetermined function operation on the partial decryption processing result, and associating the random number, the decryption key, and the function operation result,
And a parameter generation means for generating a parameter to be associated with another decoding node device; and a result of the public information randomization means of the last decoding node device calculates an expression comprising the parameter, the function operation result, public information, and the like. A decryption node device comprising: verification means for verifying whether the result matches the result; and, if the verification is successful, means for executing the processing result of each stage of the last decryption node device as the proof Pd. 11. The random replacement node of the next stage by randomizing data corresponding to the encrypted message from the bulletin board device from the random replacement node device of the preceding stage by using a random number, and randomly replacing the order of the randomized message. A first random replacement process to be sent to the device; a randomization and random replacement of the data corresponding to the encrypted message with another random number; and a second random replacement process to be sent to the next-stage random replacement node device; Using data based on the replacement process,
A proof verification process for verifying that a plurality of random permutation node devices cooperate to generate a certificate, and, if the proof verification process fails, using each of the random permutation nodes using data based on the second random permutation process. A recording medium storing a program for causing a computer to execute a node verification process for verifying device data and a read process for reading required data from a bulletin board device. 12. The recording medium according to claim 11, wherein a predetermined function operation is performed on a processing result of the second random replacement processing of the last random replacement node device.
A function operation process, a process of executing a first process or a second process in accordance with an operation result of the first function operation process, and the first process is performed on a random number and a permutation function used in the second random permutation process. A second function operation process for performing a predetermined function conversion, an operation verification process for verifying the operation of the second function operation process for other random permutation node devices, and an operation verification process for all the random permutation node devices If it passes, the proof verification process is a process of verifying the existence of a permutation function and a random number relating the input of the first random permutation node device and the output of the last random permutation node device. Is a random number associating process for associating the random numbers used in the first and second random permutation processes, and the random number associating process of the last random permutation node device. The above proof verification process is a process of verifying whether a verification formula for associating both output data of the first and second random permutation processes of the last random permutation node device is satisfied using the value of Recording medium. 13. The node verification process according to claim 1, wherein the first process includes verifying whether the input data and the output data of the second random replacement process of each random replacement node device have a predetermined relationship. A recording medium characterized in that the second process includes a process as the node verification process for verifying whether both output data of the first and second random replacement processes of each random replacement node device have a predetermined relationship. 14. A proof verification process for verifying a proof Pp created by a random permutation node device, a partial decryption process for partially decrypting information including a part of an encrypted message with a decryption key, A program for causing a computer to execute a decryption operation process for decrypting an encrypted message using the processing result, and a decryption cooperative proof process for generating a proof of successful decryption in cooperation with another decryption node device, are recorded. Recording medium. 15. The recording medium according to claim 14, wherein the decryption cooperative proof processing includes a random number generation processing, a public information randomization processing for randomizing public information with a random number, and associating the public information with another decryption node device. Information of the public information randomization process of the decryption node device, a function operation process of performing a predetermined function operation on the partial decryption result, and associating the random number, the decryption key, and the function operation result,
And a parameter generation process for generating a parameter to be associated with another decoding node device, and a result of the above-mentioned public information randomization process of the last decoding node device calculates an expression comprising the above-mentioned parameter, the above-mentioned function operation result, public information, etc. A recording medium comprising: a verification process for verifying whether the result matches the result; and, if the verification passes, a process of executing the processing result of each stage of the last decryption node device as the proof Pd.