List signature method and application to electronic voting

ES 2 360 044 T3

DESCRIPTION

List signing method and application to electronic voting

The present invention relates to the general field of the security of services accessible by a digital data transmission network and, more specifically, the field of electronic signature.

It applies, in particular, but not exclusively to electronic voting or also to electronic petition.

The electronic signature of a message implements a relevant mechanism of so-called public key cryptography: the signatory who possesses a secret or private key and an associated public key, can provide a message signature with the help of the secret key. To verify the signature, it is enough to have the public key.

In some applications such as electronic voting, the signatory must be able to remain anonymous. For this purpose, what is known as the anonymous electronic signature has been developed, which allows, with the help of a public key, to determine whether the signatory of a message has any rights (right to sign the message, right to possess the secret key used to sign the message, etc.), preserving the anonymity of the signatory. Furthermore, in voting or electronic petition applications, each authorized person should only be able to sign once.

Among anonymous signatures, there is also what is called a blind signature, which allows a person to obtain the signature of a message from another entity, without the latter having to know the content of the message and can establish, later, the link between the signature and the identity of the signatory. This blind signature solution therefore requires the intervention of an intermediary entity that provides the signatures. In applications such as voting or electronic petition, this solution involves an authorized authority that signs the vote of each voter or the petition for each petitioner.

In addition, the concept of group signature has been made known, which allows each member of a group to provide a signature such that a verifier, possessing an appropriate public key, can verify that the signature was issued by a member of the group without be able to determine the identity of the signatory.

This concept is described, for example, in the document:

[1] A Practical and Provably Secure Coalition-Resistant Group Signature Scheme by G. Ateniese, J Camenisch, M. Joye and G. Tsudik, in M. Bellare, Editor, Advance in Cryptology - CRYPTO 2000, vol. LNCS 1880, pages 255-270, Springer-Verlag 2000.

However, in this concept, a trusted authority can lift, at any time, this anonymity and determine the identity of a person in the group who has issued a signature. In addition, this type of signature is called unreliable, that is, it does not allow determining whether or not two signatures have been issued by the same person without lifting the anonymity of the signature. Group signatures are used in many applications, such as electronic sale at auctions, electronic currency or electronic voting. The group signature does not perfectly suit the latter application, since it authorizes a trusted authority to access the identity of a signatory, and does not allow two signatures issued by the same person to be related without determining the identity of the signatory. Furthermore, document [1] does not foresee processes for the revocation of a member of the group.

To remedy this last problem, the document [2] Efficient Revocation of Anonymous Group membership Certificates and Anonymous Credentials by J. Camenisch and A. Lysyanskaya, published by Cryptologie ePrint Archive IACR 2002, plans to add to this concept a revocation process (this document it will also be published by M. Jung, Editor CRYPTO 2002, Springer-Verlag 2002). However, this solution does not provide any solution to the problems of preserving the anonymity of the signatory and the reliability of two signatures.

In an electronic voting application, it is also necessary to guarantee a security of the maximum approximation of the traditional vote, to secure the following properties.

No one should be able to know, even partially, the results of the vote before its closing. Anyone must be able to convince themselves of the validity of the final scrutiny result. Finally, an authorized authority must be able to withdraw or revoke a person's right to vote.

When it comes to offline voting, that is, using an electronic voting machine installed in a voting office, or online voting, that is, remotely, through the Internet, for example, the proposed systems currently, who use a group signature as described in document [1] and completed in document [2], do not meet these conditions, but partly the revocation of the right to sign.

On the other hand, the application of the concept of blind signature to electronic voting is a solution whose implementation is onerous, because it forces the voter to connect several times to each election. Furthermore, if the poll is transmitted poorly, it is not possible to determine who is responsible: a voter or the organizer of the poll.

In addition, in particular in the document [3] Untraceable Electronic Mail Return Addresses and Digital Pseudonym of D. Chaum, ACM 1981, the concept of mixing networks has been disclosed, each mixing network being a function that provides a list of numbers decrypted from a list of encrypted numbers, hiding the correspondence between the encrypted numbers and the decrypted numbers. Applied to electronic voting, this

ES 2 360 044 T3 technique has the significant drawback of not allowing to verify the validity of a vote without compromising the secrecy of the latter.

The document [4] A Secure and Optimal Efficient Multi-Authority Election Scheme, by Cramer, Gennaro and Schoenmakers, Eurocrypt'97, LNCS - Springer-Verlag, describes what is called homomorphic encryption that allows calculations based on numbers encrypted. Solutions based on this method are not, however, applicable to polls involving a large number of voters.

The present invention aims to eliminate this drawback. This objective is achieved by the provision of a list signing method, which comprises at least:

- an organization phase that consists, for a trusted authority, defining implementation parameters of an anonymous electronic signature, with a private key and a corresponding public key, - a phase of registration of persons in a list of authorized members to generate their own electronic signature to the members of the list, in the course of which phase each person to be registered calculates a private key with the help of parameters provided by the trusted authority and parameters chosen, randomly, by the person to be registered, and the trusted authority delivers, to each person to be registered, a certificate of member of the list, - a signature phase, during which a member of the list generates and issues their own signature to the members of the list, constructing this signature so that it contains a proof that the member of the list, who has issued the signature, knows a certificate of member of the list, and - a phase of verification of the issued signature comprising steps of applying an algorithm predefined to show proof that the signature was issued by a person in possession of a certificate of membership of the list.

According to the invention, this method further comprises:

- a phase of definition of a sequence that consists, for the trusted authority, in generating a sequence number to be used in the signing phase, a signature generated during the signing phase that includes a signature element that is common to all the signatures issued by the same member of the list with the same sequence number and containing proof that the sequence number was used to generate the signature, including the verification phase, in addition, a verification stage of proof that the sequence number was used to generate the signature;

- a phase of revocation of a member from the list to remove a member from the list, in the course of which, the trusted authority removes the member to be removed from the list and updates the implementation parameters of the anonymous electronic signature, in order to take into account the deletion of the member from the list and - a phase of updating the certificates of the members of the list to take into account changes in the composition of the list.

According to an embodiment of the invention, the organization phase comprises the definition of a common parameter, which depends on the composition of the list, the registration phase of a person in the list comprising the definition of a parameter specific to the person to be registered, which is calculated based on the parameter that depends on the composition of the list and that is integrated into the certificate sent to the person, the registration phase comprising a stage of updating the common parameter, which depends on the composition of the list, the phase of revocation of a member of the list comprising a stage of modifying the common parameter, which depends on the composition of the list, to take into account the deletion of the member from the list and presenting the phase of updating the certificates of the members of the list with a stage of updating the parameter of each member of the list to take into account the changes in the composition of the list list.

According to an embodiment of the invention, a signature for a member of the list and who possesses the certificate [A_i,and_i] comprises T parameters₁, T₂, T₃ such as:

Ti = Ab "(mod.n),

T₂ = g "(mod.n),

T3 = geih “(mod.n), where ω is a randomly chosen number at the time of the signature phase, and where b, g, h and n are general parameters for implementing the group signature, such that the parameters b, g and h cannot be deduced from each other by integer power elevation functions modulo n, so that the number Ai and, therefore, the identity of the list member who holds the certificate [Ai e ¡], Cannot be deduced from a signature issued by the member.

Preferably, the number of a sequence used to generate a list signature is calculated based on a sequence start date.

ES 2 360 044 T3

In a preferred embodiment, the function for calculating the number of a sequence is of the form:

F (d) = (H (d))² (mod.n) where H is a collision resistant cryptographic summary function, d is the start date of the sequence, and n is a general implementation parameter of the group signature.

According to an embodiment of the invention, a signature issued by a member of the list contains a parameter that is calculated based on the sequence number and the private key of the signing member.

According to an embodiment of the invention, the parameter T4 of a signature issued by a member of the list, and which depends on the sequence number my on the private key Xi of the signatory member, is obtained by the following formula:

T4 = M^xi (mod. n) where n is a general parameter for implementing the group signature, and the signature comprising the proof that the parameter T4 was calculated with the private key Xi of the member of the list that issued the signature.

The invention also refers to a method of electronic voting that comprises an election organization phase, during which an organizing authority proceeds to generate the parameters necessary for a vote count and attributes keys to tellers, which allow them to decipher and verify the ballot papers, a phase of attribution of a signature right to each of the electors, a voting phase during which the voters sign a ballot paper and a counting phase, during which the tellers verify the ballot papers and calculate the result of the counting based on the content of the deciphered and valid ballots.

According to the invention, this method implements a list signing method as defined above, to sign the ballot papers, each voter being registered as a member of a list and being a sequence number generated for the scrutiny, to detect whether the same voter has issued, or not, several ballot papers for the scrutiny.

According to an embodiment of the invention, the organization phase comprises the delivery to each scrutineer of a public key and a private key, the voting ballots being encrypted with the help of a public key obtained by the product of the public keys. respective data of all the scrutineers, and the corresponding decryption private key being obtained by calculating the sum of the respective private keys of all the scrutineers.

Preferably, the encryption of the voting ballots is carried out with the aid of a probabilistic encryption algorithm.

According to an embodiment of the invention, the voting ballots cast by the voters are stored in a public database, the result of the verification and the counting of each ballot paper stored in the database in association with the ballot paper, and the private decryption key of the ballot papers that have been published.

The invention also relates to a calculator for the implementation of a list signature, comprising means for:

- generate implementation parameters of an anonymous electronic signature for the members of a list, the parameters comprising a private key and a corresponding public key, and

- transmit to each person to be registered in the list, parameters to be used by the person to be registered to calculate a private key, and a - certificate of member of the list.

According to the invention, the calculator also comprises means for:

- generate a sequence number to be used by the members of the list to issue their own anonymous signature for the members of the list, an anonymous signature issued by a member of the list that includes a signature element that is common to all the signatures issued by the same member of the list, with the same sequence number, and containing proof that the sequence number was used to generate the signature;

- Remove from the list a member to be revoked from the list, and update the parameters of implementation of the own anonymous electronic signature for the members of the list, to take into account the withdrawal of the member from the list and update the certificates of the members of the list at each modification of the composition of the list.

The invention also relates to a calculator for the implementation of an electronic voting method, comprising means for:

- generating, in the course of an organization phase of a poll, parameters for putting into practice an anonymous electronic signature for the members of a list of voters, the parameters containing a private key and a corresponding public key;

ES 2 360 044 T3

- assign key tellers that allow them to decipher and verify the ballot papers issued for the scrutiny and

- to transmit to each member of the list of voters of the poll the parameters to be used by the voter to calculate a private key, and a certificate of member of the list of voters of the poll.

According to the invention, the calculator also comprises means for:

- generate a sequence number of its own for the count to be used by the members of the voters list to sign a ballot, a signature of a ballot that includes a signature element that is common to all the signatures issued with a same sequence number for the same member of the poll voters list, and containing proof that the sequence number was used to generate the signature;

- Remove from the list a voter from the poll to be revoked, and update the parameters of implementation of the anonymous electronic signature of the members of the list of voters from the poll, to take into account the removal of the voter and

- Update the certificates of the counting voters at each modification of the composition of the list of counting voters.

The invention also relates to a terminal for issuing a list signature comprising means for:

- receive calculation parameters of a private key;

- calculate the private key with the help of the received parameters and the parameters chosen randomly;

- receive a certificate of membership from a list;

- generate their own signature for the members of the list, this signature being constituted in such a way that it contains proof that the member of the list, who has issued the signature, knows a certificate of member of the list and

- checking a signature issued by a member of the list by applying a predefined algorithm to show proof that the signature was issued by a person in possession of a certificate of a member of the list.

According to the invention, the terminal further comprises means for:

- receive a sequence number to be used in a signature phase;

- generate a signature by calculating a signature element that is common to all the signatures issued by the same member of the list, with the same sequence number and that contains a proof that the sequence number was used to generate the signature;

- check the proof that the sequence number was used to generate a signature and

- receive a new certificate of member of the list at each modification of the composition of the list.

The invention also relates to a terminal for issuing a vote ballot signature for a scrutiny, comprising means for:

- receive calculation parameters of a private key;

- calculate the private key with the help of the received parameters and randomly chosen parameters;

- receive a certificate of membership from a list of voters for the ballot;

- generate a signature of a voting ballot, this signature being constituted in such a way as to contain proof that the member of the list, who has issued the signature, knows a certificate of member of the voters list and

- verify a signature of a voting ballot, issued by a member of the voter list, applying a predefined algorithm to highlight the proof that the signature was issued by a person in possession of a certificate of membership of the list.

According to the invention, the terminal further comprises means for:

- receive a sequence number to be used to sign a ballot;

- generate a signature of a voting ballot by calculating a signature element that is common to all the signatures issued by the same member of the voters list, with the same sequence number, and that contains proof that the sequence number was used to generate the signature;

- verify proof that the sequence number was used to generate a signature on a ballot paper and

ES 2 360 044 T3 - receive a new certificate of member of the voters list at each modification of the composition of the voters list.

A preferred embodiment of the invention will be described below, by way of non-limiting example, with reference to the attached drawings where:

Figure 1 represents a system that allows the implementation of list signing and electronic voting methods, according to the invention;

Figures 2 to 8 illustrate, in the form of flow charts, the different procedures carried out in accordance with the methods of signing the list and electronic voting, according to the invention.

The present invention provides a method of signing the list, where all authorized persons, that is, those who appear on the list, can provide a signature that is anonymous, and regardless of whether it is capable of verifying the validity of the signature. without having access to the identity of the list member who signed.

Such a method can be put into practice in the system represented in Figure 1. This system has terminals 2 made available to users and connected to a digital data transmission network 5, such as the Internet network. Each terminal 2 is advantageously connected to an integrated circuit card reader 8 7. Through the network 5, users can connect to a server 6 that gives access to information, for example, stored in a database 4. This system further comprises a computer 1 of a trusted authority that delivers, in particular, the integrated circuit cards 7 to the users.

The list signature method, according to the invention, takes up the following procedures in the group signature method, described in the reference document [1]:

- a procedure for organizing a group of signatories, which consists of establishing the different parameters and public keys that are needed, - a registration procedure, where a person to be registered in the group receives a signing right from a trusted authority , i.e. an authorized private key and certificate, - a signature procedure proper in the course of which a person, who has the right to sign, signs a message and - a verification procedure that consists of applying a signature verification algorithm to verify that the signature has been provided by a person who has a signature right.

The invention also provides a provision to guarantee the anonymity of a signatory, even before a trusted authority, as well as a procedure for organizing a sequence, which consists of defining a sequence number to be used to generate list signatures, comprising in addition, verification of a signature, a step of verifying that the signature is unique for a given sequence number.

The method according to the invention may further comprise a revocation procedure, as defined in the reference document [2]. With the help of this revocation procedure, a trusted authority can withdraw, from a member of the list, the signing rights that were previously attributed to him, based on the identity of the member. The establishment of this possibility of revocation implies the execution by the members of the list of an update procedure, during which the members of the list update their certificates to take into account the modifications (additions or withdrawals) made in the list of the persons authorized to sign.

Figure 2 illustrates the different stages of the organization procedure 10 executed in the computer 1 of the trusted authority.

According to the reference document [1], this procedure consists of choosing, 11, the following integers:

<img file="ES2360044T3_D0001.tif" />

<img file="ES2360044T3_D0002.tif" />

which are lengths of integers in numbers of bits, with:

<img file="ES2360044T3_D0003.tif" />

and in defining the following sets of integers:

ES 2 360 044 T3

Λ =] 2^λ1 - 2^λ2, 2^λ* + 2^λ2[ Y

Γ =] 2^Υ1 - 2^Υ2, 2^γι + 2^Υ2[.

This procedure also consists of choosing a collision-resistant cryptographic summary function H such that a binary sequence of any specified length {0, 1} * is transformed into a binary sequence of specified length k {0,1}^k.

Next, the calculator 1 of the trust authority generates, randomly, in stage 12, prime numbers p 'and q' of magnitude Ip, such that p = 2p '+ 1 and q = 2q' + 1 are also prime numbers . It then calculates, in step 13, the modulus n = pq and generates, at random, in step 14, integers a, a0, b, g and h in the set QR (n) of the quadratic residues of n, that is, the set of integers y such that y = x²(mod.n), where x is an integer. It is considered, then, that the public key PK of the trusted authority is constituted by the sequence of integers (n, a, a₀, b, g, h) and that the private key of the latter is made up of the sequence of integers (p ', q').

To be registered by the trusted authority, a user, who wishes to become a member of the list, executes on his terminal 2 the procedure 20 illustrated in Figure 3. Executing this procedure establishes a dialogue with the computer 1 of the trusted authority, which then executes a procedure 20 '. The method comprises, first of all, a stage 21 of random generation of integers X_l and r, respectively, in the intervals] 0.2 ^² [y] 0, n² [. From these integers, we calculate 22 an integer C1 such that:

Cj = g^x'h^r(modn) (5)

In stage 23, the U test of the knowledge of two numbers α and β is established (that is,

<img file="ES2360044T3_D0004.tif" />

lyr) such that

C1 = gOi¹³ (mod n).

Such a test is constituted, for example, by randomly choosing two integers n and r2 from the set of signed binary numbers in s (21p + k) bits, indicated as follows:

<img file="ES2360044T3_D0005.tif" />

, and calculating the numbers di = g^rlh^Q (mod n)&gt;

c = / í (g || h || C₁|| di), where the symbol || represents the concatenation operator,

Yes! = n -ca, s₂= r₂-cp.

(6) (7) (S) (9) where s1 and s2 are relative integers.

The test U is then equal to (c, s1, s2, C1).

The number C1 and the test U are then sent to the trusted authority the test U and that C₁ it is found in the set QR (n) of the quadratic residuals of n.

which verifies, at stage 21 '

In the preceding example, the verification of the U test consists of calculating:

<img file="ES2360044T3_D0006.tif" />

The test is verified if c '= cy if s1 and s2 belong to the set ± {0_s ij^AND&lt;^2lp^{+ k})⁺¹

If this is the case, the trusted authority's calculator 1 randomly generates 22 'two integers a_i, β, in the interval] 0.2^λ2[, and sends these numbers to the user's terminal 2. In procedure 20, the user terminal then calculates in step 24 the integers xi and C2 using the following formulas:

ES 2 360 044 T3 ^ = 2 ^ 0.5 ^ + 01 (1110 (12 ^)), and (12)

C2 = a^x'(ínodn). (13)

Then, in step 25, build the following tests (for example, according to the same principle as test U):

- the test V of knowing a number α that belongs to the set Λ such that:

C₂ = a^to (mod n)

<img file="ES2360044T3_D0007.tif" />

β e] - 2 '·², 2^h-[ _Y - the W test of knowing three numbers β, γ, δ such that

<img file="ES2360044T3_D0008.tif" />

C₂ and the tests V and W are then sent to the calculator 1 of the trusted authority which verifies 23 'tests V and W, and that C2 belongs to the set QR (n). If this is the case, generate 24 ', randomly, a prime number e, that belongs to the set Γ and apply the following formula:

1 / eAi = (C₂to₀) '(modn) (17) and returns to the user the integers Ai and ei considered as a certificate [Ai, ej of the user's membership in the list.

The calculator 1 then creates 26 'a new entry in a table of the members of the list, for example in database 4, where it stores the certificate [Ai, eg in view of modifications of the list (for example, revocation of members) and, preferably, the messages exchanged between the trusted authority and the user during this user registration procedure.

On the other hand, the user can verify 26 the authenticity of the received certificate by verifying that the following equation is satisfied:

to^Xito₀= A®^í(modn) (18)

At the end of this registration procedure 20, the user has a private key x_i and a certificate [A_i, e_i] of list member, which are memorized, for example, on an integrated circuit board 7.

With the help of such a certificate, the user can generate a signature of a message M belonging to the set {0, 1} *.

For this purpose, the trusted authority publishes, according to the invention, a sequence number m, chosen randomly from the set QR (n). This number should be used by members of the list to sign a message during a given sequence. The respective numbers of different sequences must not be able to be linked. In particular, it must be impossible to calculate a discrete logarithm of a given sequence number, with respect to the base of another sequence number, that is, it must not be possible, in practice, to calculate integers x and y such that: m^x= m^,Y (mod n), where m and m 'sequence numbers.

This sequence number m can be calculated based on the sequence start date: m = F (date). This function F is chosen, for example, equal to:

F (d) = (/ T (d))² (mod n) (19) where H 'is a collision resistant cryptographic digest function, such as a binary sequence of any indicated length {θ, 1}, is transformed into a binary sequence of indicated length 21p {θ , 1}^{twenty-one p} . Therefore, it is easy to check the validity of the sequence number by applying formula (19).

The procedure for signing a message is designed to allow, in particular, a user to demonstrate that they know a member certificate and member private key and that they are using the correct sequence number.

To sign a message M, a member of the list must execute, for example, on his integrated circuit card 7, connected to a terminal 2 and memorizing his certificate [Ai, ei] and his private key Xi, a signing procedure 30 ,

ES 2 360 044 T3 as illustrated in Figure 4. This method comprises, first of all, a step 31 of random generation of a number ω belonging to the set {θ, 1}²¹ ” .

In addition, it includes a step 32 that consists of calculating the following numbers from ω:

Ti = A¡b® (mod n),

T₂ = g^ra (mod n),

T₃ = g^eih® (mod n).

(20) (21) (22)

In accordance with the invention, the following number is also calculated:

T4 ^{_ mX}'(mod n) (23)

In the next step 33, the numbers ri are generated in a random way in the set of numbers ρΑ, + ιλ -ι / n 1 utoto) + ín 1-1 ^₂+ k) binary, signed, in bits, indicated, r₂ in the set ^!, r₃ in the set and r4 in the set - (θ: O ^P . Then, in step 34, the following quantities are calculated:

di = T / '/ Ca¹²/³) (mod n) d₂ = T? / ^ (Mod n) d₃ = g^r4 (mod n) d₄ = gⁿh^r4 (mod n) (24) (25) (26) (27)

According to the invention, the following number is also calculated:

d₅ - m '² (mod n)

<img file="ES2360044T3_D0009.tif" />

Then, in step 35, the following numbers are calculated:

<img file="ES2360044T3_D0010.tif" />

where || represents the concatenation operation, s_t = ri-c (ei-2^Y1), s₂ = r₂ - c (x¡ - 2^λ1), s₃= r₃-ceiO,

S4 = Γ₂ “ ^C0)&gt;

(30) (31) (32) (33) where sl, s2, s3, s4 are relative integers.

The signature is, at the end, made up of the following set of numbers:

(c, Si, S₂, S₃, S4, Tj, T2 »T₃, T4).

(34) that is broadcast, for example, by network 5.

The verification of a signature of an M message is carried out by executing the procedure 40 illustrated in Figure 5. This procedure comprises, first of all, in step 41, the calculation of the following numbers:

ES 2 360 044 T3 t₁= ajTr²’^,/(to'''^C2Mb^S)) (modn) to-T ^² / g^Yes(modn) t₃ = T2g^S4(modn) (35) (36) (37)

<img file="ES2360044T3_D0011.tif" />

According to the invention. It also includes the calculation of the following numbers:

t ^ TÍm ^ 'ímodn) (39) c' = «(mllblIglIhllaollalIT ^ I ^ IITjllT.Iltdltjll ^ llUlItsllM) (40)

The signature is authentic if the following conditions are verified in step 42:

C * = C _S1 G ± {0, s₂ e ± {0, s₃e ± {0, l}^{6 (rl + 21}P^{+ fcflH}, s₄ e + {0, (41) (42) (43) (44) (45)

If these conditions are not met, the signature is invalid (step 45).

Furthermore, by accessing all the signatures that were issued during a given sequence, for example in database 4, it can be easily verified, in step 43, with the help of the T4 parameter, if a member of the list has signed several times: all signatures issued by a member of the list comprise a T4 parameter that has the same value for a given sequence number.

It should also be noted that a member cannot cheat by using another value because T4 is closely tied to T1. Indeed, the calculation formula for T1 can also be written as follows:

lfⁱ= a₀to^x¡b®^ei(modn) (46)

If T4 is already in the set of signatures issued for a given sequence number, it follows that the signature was already issued by a member of the list for this sequence number (step 46).

To include a possibility to revoke a member of the list, the method, just described, can be modified as follows.

The list organization procedure 10 further comprises, in step 14, the random choice of a number u, which belongs to the set QR (n), and the definition of two sets E_todd and Edel that are initially empty.

The public key PK of the trusted authority is then made up of the sequence of integers (n, a, a0, b, g, h, u) and sets Eadd and Edel.

During the registration procedure 20, 20 ', the calculator 1 of the trust authority attributes, in step 25', the parameter u¡ to the new member U¡ of the list, this parameter being such that u¡ = u, and updates the value of the u parameter by substituting this value for u^ei.

The certificate of the new member then regroups the integers Ai, e¡ yu¡, this certificate being memorized, in step 26 ', for future modifications and is transmitted to the new member.

The trusted authority also enters the number ei assigned to the new member in the Eadd set.

Upon receipt of their certificate, the new member further verifies that:

ES 2 360 044 T3 u¡^and'= u (mod n) (47)

The other members Uj of the list must then execute an update procedure to take into account the arrival of the new member and therefore the modification of the list parameter u. This procedure consists of recalculating its parameter uj as follows:

(48)

In this way, the relation (47) is always verified for all the pairs (uj, ej) of all the members of the list.

The revocation procedure of a Uk member of the list, whose certificate is (Ak, ek, uk) consists, for the trusted authority, in modifying the u parameter as follows:

u = u^{1 / ek} (mod n) and in introducing the parameter ek in the Edel set.

In addition, each non-revoked member Uj of the list must take into account this revocation (change of

u) by recalculating its parameter uj as follows:

u¡ = Uj^b_or^to (mod n) ^ 0) where a and b such that aej + bek = 1

To determine a and b, it is enough to apply the extended Euclidean algorithm, which consists of carrying out a series of Euclidean divisions.

It should be noted that the revoked member (which has ek) cannot determine a and b with the help of formula (50), which becomes ek (a + b) = 1, and therefore recalculate the parameter uk.

During the procedure 30 for the signature by a member of the list, it is also necessary, in step 31, to choose, at random, the numbers wi, W2 and W3 of binary length equal to 21p, that is, that belongs to the set {ü, 1}²¹ ”, And calculate, in step 32, the following numbers:

<img file="ES2360044T3_D0012.tif" />

<img file="ES2360044T3_D0013.tif" />

In addition, it is necessary, in step 33, to randomly choose numbers 15, re, r₇ belonging to the set + Í0 1 vfri^+2,p^{+ fc + 1}&gt;

and numbers re and rg that belong to the set and then, calculate, in step 34, the following numbers:

di = gⁿh^T5 (mod n) d? = g ^ h¹⁷ (mod n) do = T₆^ri/ h^rg(mod n) d₉ = Tv ^ / Cg ^ h ^) (mod n) (54) (55) (56) (57)

The number c then includes the following elements:

<img file="ES2360044T3_D0014.tif" />

It is necessary, then, to calculate in step 35:

ES 2 360 044 T3 s₅ r₅ - cwi s₆ = r₆ - cw₂s₇ = r₇ - cw₃sg = r₈ - ce¡w₂ s₉ = r₉ - ceiW₃ (59) (60) (61) (62) (63)

The signature is, then, made up of the following set of numbers:

(c, Yes, s₂, s₃, s₄, s₅, S6, s₇, s₈, s₉, T_b T₂, T3, T₄ T₅, T₆, T₇). (64)

The procedure 40 for verifying a signature then further comprises the calculation of the following numbers in step 41:

t₆= T₅^cg^{S1 c2} h^Yes(modn) t7-T7 g^S6h^S7(modn) t8 = u^CT6^Cg^S1_c2n/ h^S8(modn) t9 = T₇^1_c2 / (g^S8h^S9) (modn) (65) (66) (67) (68)

<img file="ES2360044T3_D0015.tif" />

The signature is authentic if the following supplementary conditions are verified in step 42:

s₅ e ± {0, s₆ e ± {0, s₇ e ± {0, s₈e ± {0_sl) ^^{+ 2l}^^,)+,et s₉ e ± {0, (70) (71) (72) (73) (74)

It should be noted that, contrary to the group signature described in document [1], it is not possible, for the trusted authority, to rediscover the identity of a signatory, that is, the Ai number of the signatory's certificate from a signature of list, as described. Indeed, contrary to the method described in this document, the trusted authority does not use a private key x to generate the parameter b and therefore the number Ai cannot be derived from T1 and T2.

Also, the signature generated by a revoked member U_k invalid will be detected. Indeed, the parameter T₆makes intervene the parameter uk that was determined from the common parameter u, and the parameter t₈, which is calculated to verify the signature, also involves the parameter u that was modified as a result of the revocation of member k. It follows that, at the time of signature verification, the parameters T6 and t8 are inconsistent and, therefore, that the equality between c and c 'cannot be verified by the signature of member k.

The list signing method, just described, can be applied to an electronic voting method. The electronic voting method, according to the invention, comprises several phases, the execution of which of the list signing method procedures is described below.

This method involves the intervention of a trusted authority 1 organizing the elections, which executes, for this purpose, a procedure 50 for organizing the vote. This procedure consists of generating the data necessary for the proper conduct of the elections, a public database accessible to all, where the ballot papers are collected. In the course of organizing the scrutiny, scrutineers are also appointed who will be in charge of counting the votes and determining the result of the election.

The organizing authority proceeds, first of all, to the generation of the different parameters necessary for the establishment of a list signature, executing the procedure 10 for organizing a list signature. Voters must then register in advance, for example in a mayor's office, on an electoral list in such a way that they

ES 2 360 044 T3 that receives all the necessary data, namely a private key xi and a certificate (Ai, ei, ui), to generate a list signature. With the help of these parameters, voters can participate in all future elections. This registration procedure can, for example, be carried out between an integrated circuit card 7 and a terminal 2, the integrated circuit card memorizing, at the end of the procedure, the voter's certificate.

Before an election, the organizing authority proceeds to update the electoral lists by executing procedure 20, 20 'for the newly registered voters, and withdrawing (revoking) the rights to sign the list of all persons excluded from the voter registers. (for example, people who have left the constituency or deprived of their civic rights). These revocations are made by executing the revocation procedure described above. In step 51 of procedure 50, the organizing authority also publishes a sequence number m necessary for the establishment of a new list signature sequence, so that voters are prevented from voting (signing) twice in this election .

On the other hand, the scrutineers will proceed to create 52 the necessary public / private key pairs, in such a way that all must cooperate to be able to decrypt a message encrypted with the public key. For this purpose, the established cryptographic system is chosen so that a voter is allowed to encrypt a message (ballot) with the help of at least one public key, imposing the cooperation of all tellers to use the private key (s) and thus decipher the message.

The distribution of the private decryption keys among all the scrutiners can be carried out as follows.

G is considered to be a generator of the cyclic group G. A respective private key xi is assigned to each scrutineer i that calculates the number y, belonging to G such that:

(75)

<img file="ES2360044T3_D0016.tif" />

The public key Y to be used by voters is obtained by the following formula:

<img file="ES2360044T3_D0017.tif" />

and the corresponding private key X shared by all scrutiners i is the following:

<img file="ES2360044T3_D0018.tif" />

(77)

An analogous result can be reached by carrying out an encryption using all the respective public keys of the scrutineers, the decryption requiring knowledge of all the corresponding private keys.

Before going to vote, each voter must update their list signing certificate, in accordance with the modification procedure described above, with the help of the previously published parameters. If the voter is not excluded from the electoral lists, this modification may be made.

During the opening of the voting offices, each voter issues a ballot paper by executing, in a terminal, a procedure 60. In step 61, the voter selects his vote vi and encrypts the latter with the help of the public key of the tellers to obtain an encrypted vote Di. He then signs the encrypted vote with the help of the list signing method to obtain a Yes signature. The ballot made up of the set (Di, Si) of the vote and the signature, is then published, anonymously, in a public database 4.

In step 62, the vote is encrypted using a probabilistic encryption algorithm (that is, the probability that two encryptions of the same message are identical is almost zero), such as, for example, the El Gamal algorithm or by Paillier. If the El Gamal algorithm is applied, the encryption is carried out by calculating the following numbers:

<img file="ES2360044T3_D0019.tif" />

where r is a random element. The encrypted vote vj is then constituted by the pair Dj = (aj, bj). The voter Ej determines 63, then, the list signature of the encrypted vote, the list signature being as described above, executing the procedure 30 by his integrated circuit card 7, which is then transmitted to terminal 2.

The voter Ej has thus generated his ballot paper (Dj, Sj) which sends 64 to the public database 4 by means of an anonymous transmission channel, that is to say, preventing a transmitted message from being related to the issuer of the latter. The voter can, for this purpose, use a public terminal or a network of mixers.

At the end of the scrutiny, the scrutineers count the scrutiny by executing procedure 70 on terminal 3. This procedure consists, above all, of generating 71 the private decryption key X from its keys

ES 2 360 044 T3 respective private xi and with the help of formula (77). Then, in step 72, they access the public database 4 of the voting ballots to obtain the ballots (Di, Si) and to decrypt them.

The actual decryption of the ballot papers consists for each ballot issued (step 73) to verify 74 the signature Yes by executing the above-described list signature verification procedure and if the signature is valid and unique (step 75) , to decrypt 76 the encrypted vote Dj by applying the following formula:

<img file="ES2360044T3_D0020.tif" />

The votes vj thus deciphered and verified, with the result of the corresponding verification, are entered 77 in the database 4 of the ballots, in association with the ballot (Dj, Sj).

Decryption private key X is also published to allow everyone to verify the ballot count.

Once all the ballots have been counted, this procedure 70 calculates, in step 78, the result of the election and updates the public database of the ballots, introducing in it this result and, if necessary, the private key decryption X.

It is easy to verify that the aforementioned properties, necessary for the establishment of an electronic voting system, are verified by the method described above. Indeed, each voter can only vote once since it is easy to find, in the database, two signatures issued by the same voter for the same ballot (for the same sequence number). In this case, the tellers may disregard the two votes or count only one vote if they are identical.

As an alternative, it can be envisaged that, in step 64 of entering a vote in database 4, it is verified that the vote cast by the voter no longer appears in the database, by searching in it for its own parameter T4 of the voter. If, in this way, it is detected that the voter has already voted for this count, the new vote will not be entered in the database 4.

Consequently, it is not possible to start the counting of the ballots before the end of the count if at least one of the tellers respects the rule, since the presence of all the tellers is required to count a ballot. Finally, the result of the election is verifiable by all, since the scrutineers provide, in the database, all the necessary elements (in particular, the private counting key) to proceed with such a verification and that the verification of a signature is accessible to all, using the public key PK = (n, a, a0, b, g, h, u) of the trusted authority. In this way, any trusted person will be able to carry out the count in the same way as the tellers and therefore, it will be possible to make sure that it was done correctly.

Of course, the tellers' keys will be out of date at the end of the count, since they were made public.