JP3529078B2 - Electronic secret ballot method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an electronic secret ballot voting method for realizing secure and fair secret ballot when performing voting, questionnaire survey, or the like using electronic means.

[0002]

2. Description of the Related Art Electronic secret balloting is a method that can keep the correspondence between voters and voting contents secret and is suitable for protecting the privacy of individual creeds. It can be used for questionnaire surveys, etc.
To perform secure and fair electronic secret balloting in telecommunications, it is necessary to prevent impersonation of a voter, double voting, leakage of voting content due to eavesdropping of a voting sentence, and the like. As a method for solving these problems, an electronic voting method using a digital signature has been proposed. For example, Kazuo Ota: "Electronic voting method using a single election manager", The Institute of Electronics, Information and Communication Engineers, 1988 Spring National Convention, A-294 (Showa 63-
There is 3).

[0003] However, this method has the following disadvantages. The elector's election details will be posted (in anonymous) on bulletin boards, etc., so that the individual can easily identify himself from other votes. This feature allows opposition to be filed when one's vote is ignored (when it is not made public) and helps to ensure the legitimacy of the election results.

However, this feature, on the other hand, means that information known only to the voter can be used as proof of the vote. In other words, there is a risk that voting evidence could be used to acquire a voter and prove that the acquired voter has voted as said. In addition, there is a danger of being used for forcing voting due to intimidation or the like. As a method of solving such a drawback, "An Electronic by Tatsuaki Okamoto
VotingScheme, Proc.of IFIP '96, Advanced IT Tools,
Chapman & Hall (1996) "and a patent application" Electronic secret ballot method "(Japanese Patent Application No. 8-230869). In other words, in this method by using the encryption method of decryption is possible even in several ways if you have the secret information, the voter V _i is, the vote content v _i using a random number _{r i m i = E (v} i, r _i )
It is published as voting information, but the voter himself V
_i is, your own E by using the secret information a _i have is _{(v i, r i) =} E (v i ", r i") to become like _{(v i ", r i"} ) (v i ≠ v _i ") can be calculated. by this nature, the voters, in fact (v _i, r
_i ), but if you vote for it,
(V _i ″, r _i ″) can be presented with false evidence. Therefore, the use of such a cryptographic function E eliminates the credibility of voting. Even if further cipher E is with nature, such as described above, aggregation's (v _i, r _i) if publish, it is the evidence of the vote. To prevent such things, while _{m i = E (v i,} r i) a correspondence relationship between v _i secret employs a proven method of disclosing v _i. However, even with these methods, under certain conditions, there is a danger of acquiring or forcing votes.

[0005]

SUMMARY OF THE INVENTION An object of the present invention is to provide a secure electronic secretary voting method in which proof of voting cannot be made under any conditions.

[0006]

In the present invention, a new technology is used based on the technology of the electronic secret ballot voting method of Japanese Patent Application No. 8-230869. It is a technology that proves to a tallyer at the time of voting that the secret information is surely held in an encryption scheme that can be decrypted in any number of ways if the secret information is available. As one of the realization technologies,
A method is used in which the secret information is divided and entrusted to a plurality of parameter managers. Further, as another realization method, a technique for proving only that the confidential information is held without leaking (so-called zero knowledge proof) is used.

[0007]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the first aspect of the present invention will be described below. FIG. 1 shows an example of a system configuration to which the present invention is applied. Voters device 1 of the I's voter V _i
00, the administrator device 200 Election administrator A, totalizer C Aggregate's device 300, a parameter manager device 600 of the list display unit 400N's parameter manager R _j, respectively,
It is assumed that they are connected via the communication path 500. It is also assumed that all voters have access to list display 400. FIG. 2 shows an example of a communication sequence according to the present invention. FIG. 3 shows an example of a functional configuration of the voter apparatus 100, and FIG. 4 shows an example of a functional configuration of the parameter manager apparatus 600.

In the following, in particular, the voter V _i (i = 1, 2, 2)
..., I) is after obtaining the approval of the election administrator A vote content v _i, a description will be given of a case to vote against aggregate user device 300. The voting procedure will be described below. First, as parameters commonly used in the system, values p and satisfies the following conditions.
It is assumed that q, g, and h are defined. p, q: prime q | p-1 (q is about the number of _{p-1) q, h∈Z p} * of order in the (multiplicative group) q, in other words g ^q ≡h
^q ≡1 (mod p), and g ≠ h ≠ 1, and a
It is assumed that no one knows the value of (h = g ^a mod p) (for example, g and h are independently generated using a publicly available pseudo-random number generation algorithm).

1. Voter apparatus 100 of the voter V _i performs the preparation of the vote in the following manner. First, using a random number generator 101 generates a _i ∈ Z _q, using the remainder operator 102 calculates the G _i = g ^ai mod p. Next, the voter V _i
Determines the content of the vote v _i and inputs it to the voter device 100. The voter device 100 generates a random number r _i using a random number generator 101, and uses a remainder calculator 103 to obtain m _i = BC ( v _i , r _i ) = g ^vi G _i ^ri mod p, is calculated.

[0010] 2. Apparatus 100 of the voter V _i is, blind signature technique (David Chaum: "Securitywithout identifi
cation: Transaction systems to make big brother ob
solete ", Communications of the ACM, Vol.28, No.10,
pp. 1030-1044 (described in Oct., 1985)) to obtain the signature s _i of the election manager device 200 for (m _i , G _i ).

3. Voter V_iThe device 100 of (m_i, G
_i, S_i) Is sent anonymously to the list display 400, and FIG.
Posted as shown. Voter V_iThe device 100
Is sent to the tallyer device 300 (v_i, R_i, M_i) Secret
Send (for example, by encrypted communication). Up to this point, the patent application
The processing is the same as that shown in FIG. 4. Voter V_iDevice 100 includes a random number generator 101,
Using the coprocessor 104, a_i∈Z_qSatisfy the following equation
N values a_i1, ..., a_iNDivided into a_i=
a_i1+ ... + a_iN modq Voter V_iThe device 100 of a_ijThe parameter manager
R_j(J = 1,..., N). Parame
Administrator R_jThe device shown in FIG.
01, G_{i, j}= G^aijmod p (j = 1, ...,
N) and calculate G _{i, j}To the display 400, and
It is sent to totalizer apparatus 300.

[0012] totalizer device 300 checks whether _{^{G i = П j = 1 N}} G i, j mod p is satisfied with the remainder calculator 310 and a comparator 311. If they do not match, the aggregator device 610 sends the corresponding vote (m _i , G _i ,
s _i ) is regarded as invalid and is excluded from the target of aggregation. In addition,
This verification can be performed by anyone since G _{i, j} is made public. For example, as shown in FIG.
At 00, the verification may be performed using the remainder arithmetic unit 602 and the comparator 603.

5. The tallyer device 300 can be used to
Divide into groups and put all (mostly
A) Candidates are included in the ballot. example
So for the sake of simplicity, here are 5 voters
A group will be described. In this example, the list
What is posted on the indicator 400 is ((m₁ , G
₁),…, (M_Five , G_Five )) Corresponds to this group
Is declared by the tallyer apparatus 300. Moreover
Voting details (v₁ , V_Two , V_Three , V_Four , V_Five ) Is random
Published by the tallyer device 300 in an appropriate order. here,
Published vote, with π as the permutation to randomize the order
V₁ ', V_Two ', V_Three ', V_Four ', V _Five '= ｛Π
(V₁ ), Π (v_Two ), ..., π (v_Five )｝.
For example, replacing the substitution π with (1, 2, 3, 4, 5) → (2, 4,
1,5,3), then (v₁ ', V _Two ', V_Three ', V
_Four ', V_Five ') = (V_Two , V_Four , V₁ , V_Five , V_Three )When
Become. Note that π is a secret known only to the tallyer apparatus 300.
Dense.

6. The tallyer apparatus 300 uses the following method (v
₁ ', V_Two ', V_Three ', V_Four ', V _Five ') Is the correct vote
Π, (r₁ , ..., r_Five ) Kept secret
As it is, the proof information σ is published. Below, the raw of σ
The method of formation is shown. As shown in FIG.
Permutation δ that rearranges 5 elements_jTo the random number generator 301
And randomly select k (j = 1, ..., k) using
And random number u_ij, S_ij, T_ij∈Z_q(I = 1, ..., 5; j
= 1,..., K).

Next, the following is calculated using the remainder arithmetic unit 302. ^{_{Z ij = m i G i Sij}} h uij mod p, W ij = g v 'i' h tij mod p, i = δ j (i) (i = 1, ..., 5ij = 1, ..., k) then , F as a function for compressing data of an arbitrary length to k bits, using this function calculator 303, (e ₁ , e ₂ ,..., E _k ) = F (Z ₁₁ ,..., Z _5k ,
W ₁₁ ,..., W _5k ). Here, e _j {0, 1} (j = 1,...,
k).

Next, a decision is made using the comparator 305 in accordance with the value of e _j , and if e _j = 0 (j = 1,..., K), Y _j = (δ _j , u _ij , s _ij , t _ij (i = 1,..., 5))
If e _j = 1 (j = 1,..., K), the tallyer apparatus 300 uses the replacement calculator 304 and the remainder calculator 306 to obtain ρ _j = π ⁻¹ oδ _j ⁻¹ , (AoB describes the synthesis of a function a and _{B) x ij = r i +} s ij mod p, y ij = u ij -tρ j (i) mod p, and the _{calculation, Y j = (ρ j,} x ij, y ij (I = 1, ...,
5)).

As described above, the proof information σ is determined as follows. σ = (Z ₁₁ ,..., Z _5k , W ₁₁ ,..., W _5k , Y _{1 ,.
k} ) 7. Verification of the validity of the proof information σ is performed as follows.
(Hereinafter, an example will be described in which the voter apparatus 100 performs the verification.) First, the function calculator 105 of F stores σ of (Z ₁₁ ,..., Z _5k ,
W _11, ..., and enter the _{W 5k) (e 1, e} 2, ..., e k)
Ask for.

Next, a decision is made using the comparator 106 according to the value of e _j . If e _j = 0 (j = 1,..., K),
Remainder operator 107, a comparator _{108 Z ij = m i G i} Sij h uij mod p, W ij = g v 'i' h tij mod p, i '= δ j (i) (i = 1 using, ..., 5).

If e _j = 1 (j = 1,..., K), the voter apparatus 100 uses the remainder arithmetic unit 109 and the comparator 110 to obtain W _ij G _i ^xij h ^yij ≡Z _ij (mod p ), I '= ρ
Verify whether _j (i) holds. In the above, the signature by the election manager device is not necessarily required.

Next, a second embodiment of the present invention will be described. The components used here have the same symbols as in the above description. Here, the parameter manager device 600 is not required. FIG. 7 shows the procedure.
FIG. 8 shows a part of the functional configuration of the voter apparatus 100, and FIG. 9 shows a part of the functional configuration of the tallyer apparatus 300. The voting procedure is as follows.

1. From the beginning, the voter V _i of the device 100 _{(m i, G i, s} i) posted be sent anonymously to the list display unit 400, also in the summary's device _{300 (v i, r i,} m
_The procedure up to the step of secretly sending _i ) is the same as that of the first embodiment. 2. 100 of voter V _i, it proves to totalizer device 300 in the following procedure, further knows the value of a _i ∈ Z _q.

[0022] First, apparatus 100 of voter V _i generates a random number r ∈ Z _q using the random number generator 110, using the remainder operator 111 calculates the T = g ^R mod p, the T This is sent to the tallyer apparatus 300. The tallyer device 300 includes a random number generator 3
It generates a random number U∈Z _q using 07, and sends it to the voter apparatus 100.

The voter device 100 calculates Q = R + Ua _i mod q using the remainder calculator 112 and sends it to the tallyer device 300. The tallyer device 300 is a remainder operator 30
8 and the comparator 309 to verify whether g ^Q QTG _i ^U (mod p) holds.

[0024] if they pass the verification of the above, admitted has been sent _{(v i, r i, m} i) and voting, advance to the next stage.
That is, the process proceeds to the fifth step of the embodiment of claim 1 and performs the same processing. In the above, the signature S _i by the election manager device is not necessarily required.

[0025]

In the electronic secret ballot method according to the present invention Japanese Patent Application No. 8-230869, G _i = g ^ai m acquirer of the vote is hiding a _{i
od p, v i, r i} , m i = BC (v i, r i) = g vi G
_{If i} ^ri mod p is given to the voter and the vote is forced, the voter cannot vote anymore.

On the other hand, according to the first aspect of the present invention, a_ij
To the parameter manager R_j(J = 1, ... 4, N)
Must be a_i= A_i1
+ ... + a_iN You can know the value of mod q. Therefore,
Voter is G_i, V_i, R_i, M_iBeing forced to vote
Also any v_i'∈Z_qAgainst m_i= G^viG_i ^ri mod p = g^vi'G_i ^ri´mod p R such that_i'∈Z_qCan be calculated. Subordinate
So, the voter is actually (v_i', R_i′)
, But for those who acquire the vote, v_i∈Z _qThrow
It is possible to falsify as having voted.

Similarly, according to the second aspect of the present invention, the voter is a _i
In order to compel it to prove to the aggregation person that you know the value, always a _i voter when to pass the inspection
You can know the value of Therefore, it has the same effect as the first aspect of the invention.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration example of a system to which the present invention is applied.

FIG. 2 is a view showing a processing sequence in the embodiment of the second invention.

FIG. 3 is a block diagram showing a functional configuration of a voter device 100 in the embodiment of FIG. 2;

FIG. 4 is a diagram showing a display example of a display device 400.

FIG. 5 is a parameter management device 60 in the embodiment of FIG. 2;
FIG. 2 is a block diagram showing a functional configuration of the first embodiment.

FIG. 6 is a block diagram showing a functional configuration of a tally person apparatus 300 in the embodiment of FIG. 2;

FIG. 7 is a diagram showing a processing sequence in the embodiment of the second invention.

FIG. 8 is a block diagram showing a main part of a functional configuration of the voter apparatus 100 in the embodiment of FIG. 7;

FIG. 9 is a block diagram showing a main part of a functional configuration of the tally person apparatus 300 in the embodiment of FIG. 7;

Claims (2)

(57) [Claims] A voter apparatus according to claim 1] voter V _i, a display unit,
And totalizer aggregate's apparatus, a method for implementing electronically ballot by the parameter manager device parameters administrator, the voter apparatus voter V _i, using the random number r _i a vote content v _{i m i = E (v i,} r i) encrypts, the cipher E (v _i, r _i) is E by using the secret information a _i only own voter unit has (v _i, r _i) = E
_{(V i ', r i'} ) to become like _{(v i ', r i'} )
(V _i ≠ v _i ') are those that can be calculated, voter apparatus of voter V _i sends a m _i to the aggregate's device, the voter device secret information a _i of the voter V _i Information a _i1 ,
..., it is divided into a _iN feed to each parameter manager device N's parameter manager, each of the parameter manager device is a _i1, ..., information corresponding with _{a iN F (a i1),} ..., F (a _iN) to generate publish, voter apparatus of voter V _i is the aggregation's device (v _i, r _i)
Subjected sent in encrypted communication, totalizer device, for each _{m i, F (a i1)} , ..., F
(A _iN ) satisfies the verification formula, and if the verification does not pass, the voting content is invalidated. The tallyer apparatus calculates the above m ₁ ,..., _Mk and the voting content v ₁ ,
..., v ₁ to v _k in a random order ', ..., v _k' and,
Furthermore any of the _{v i '(i = 1,} ..., k) be (m _1,
, M _k ), the electronic secretary voting method characterized by sending information certifying that the cipher text is any one of the ciphertexts to a display device and making it public. A voter apparatus wherein voter V _i, a display unit,
A method for realizing electronically ballot by the aggregate's totalizer device, voter device voter V _i is vote content v _i a using a random number _{r i m i = E (v} i, r i ) to encrypt, the cipher E (v _i, r _i) is E (v _i by using the secret information a _i only own voter device has, r _i) = E
_{(V i ', r i'} ) to become like _{(v i ', r i'} )
(V _i ≠ v _i ') are those which can be calculated, voter device voter V _i sends m _i to totalizer device, further totalizer device (v _i, r _i) as well as sending in encrypted communication, that holds the secret information a _i to be verified in the summary's device in the secret the value of a _i, we have to pass this verification aggregate's device and disable the vote contents , The tallyer's device includes m ₁ ,..., _Mk and voting contents v ₁ ,.
v v a _k in random order ₁ ', ..., v _k' and then, further to any of the _{v i '(i = 1,} ..., k) be (m _1, ..., m
_k ) the electronic secretary voting method, wherein the information proving that the encrypted text is any of the ciphertexts is sent to the display and made public.