List signature method and application to electronic voting

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

0002It applies in particular, but not exclusively, to electronic voting or to electronic petitions.

0003The electronic signature of a message implements a mechanism related to so-called public key cryptography: the signatory who has a secret or private key and an associated public key, can produce a message signature using the secret key . To verify the signature, all you need is the public key.

0004In certain applications such as electronic voting, the signatory must be able to remain anonymous. To this end, we have developed what is known as anonymous electronic signature allowing, using a public key, to determine whether the signatory of a message has certain rights (right to sign the message, right to have the secret key that was used to sign the message, etc.), while preserving the anonymity of the signatory. In addition, in voting or electronic petition applications, each authorized person must be able to sign only once.

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

0006We have also proposed the concept of group signature which allows each member of a group to produce a signature such that an verifier with an adequate public key can verify that the signature was issued by a member of the group without being able to determine the identity of the signatory. This concept is for example described in the document:<ul id="ul0001" list-style="none" compact="compact"><li>[1] "<nplcit id="ncit0001" npl-type="b"><text>A Practical and Provably Secure Coalition-Résistant Group Signature Scheme "by G. Ateniese, J Camenisch, M. Joye and G. Tsudik, in M. Bellare, Editor, Advance in Cryptology - CRYPTO 2000, vol. 1880 of LNCS, p. 255-270, Springer-Verlag 2000</text></nplcit>.</li></ul>

0007However, in this concept, a trusted authority can lift this anonymity at any time and determine the identity of a person in the group who has issued a signature. In addition, this type of signature is said to be "unreliable", that is to say that it does not make it possible to determine 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 auctions, electronic money and electronic voting. The group signature is not perfectly suitable for this 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 linked without determining the identity of the signatory. In addition, document [1] does not provide for a group member dismissal process.

0008To remedy this last drawback, 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 a revocation process to this concept (this document will also be published by M. Jung, Editor CRYPTO 2002, Springer-Verlag 2002). However, this solution does not provide a solution to the problems of preserving the anonymity of the signatory and the "reliability" of two signatures.

0009In an electronic voting application, it is also necessary to ensure security which is as close as possible to traditional voting, to guarantee the following properties. No one should be able to know even partially the results of the poll before its closure. Everyone must be able to convince themselves of the validity of the final result of the ballot. Finally, an empowered authority must be able to withdraw or revoke a person's right to vote.

0010Whether it is offline voting, i.e. using an electronic voting machine installed in a polling station, or online voting, i.e. remotely, via the Internet for example, the systems currently offered, using a group signature as described in document [1] and supplemented in document [2], do not meet these conditions, apart from revocation of the right of signature.

0011In addition, the application of the concept of blind signature to electronic voting is a solution whose implementation is cumbersome, because it obliges the voter to connect several times at each election. In addition, if the ballot goes wrong, it cannot be determined who is responsible for it: a voter or the organizer of the ballot.

0012We also proposed, in particular in the document [3] "Untraceable Electronic Mail Return Addresses and Digital Pseudonym" by D. Chaum, ACM 1981, the concept of mixing networks, each mixer being a function producing a list of numbers deciphered from 'a list of encrypted numbers, while hiding the correspondence between the encrypted numbers and the deciphered numbers. Applied to electronic voting, this technique has the major drawback of not making it possible to verify the validity of a vote without compromising its secrecy. In the document [4] "A Secure and Optimal Efficient Multi-Authority Election Scheme", by Cramer, Gennaro, and Schoenmakers, Eurocrypt'97, LNCS - Springer-Verlag, there is described what is called homomorphic encryption allowing perform basic calculations on numbers. Solutions based on this process are however not applicable to polls involving a large number of voters.

0013The object of the present invention is to eliminate this drawback. This objective is achieved by providing a list signing process comprising at least:<ul id="ul0002" list-style="dash" compact="compact"><li>an organizational phase consisting for a trusted authority in defining parameters for implementing an anonymous electronic signature, including a private key and a corresponding public key,</li><li>a phase of registering people in a list of members authorized to generate an electronic signature specific to the members of the list, during which each person to be registered calculates a private key using parameters provided by the trusted authority and parameters chosen randomly by the person to be registered, and the trusted authority issues each person to register a list member certificate,</li><li>a signature phase during which a member of the list generates and issues a signature specific to the members of the list, this signature being constructed so as to contain proof that the member of the list having issued the signature, knows a certificate of member of the list, and</li><li>a verification phase of the signature issued comprising steps of applying a predefined algorithm to highlight the proof that the signature was issued by a person in possession of a list member certificate.</li></ul>

0014According to the invention, this method further comprises:<ul id="ul0003" list-style="dash" compact="compact"><li>a phase of defining a sequence consisting for the trusted authority in generating a sequence number to be used in the signature phase, a signature generated during the signature phase comprising a signature element which is common to all the signatures issued by the same member of the list with the same sequence number and which contains proof that the sequence number was used to generate the signature, the verification phase further comprising a step of verifying the proof that the sequence number was used to generate the signature;</li><li>a phase of revocation of a member from the list to remove a member from the list, during which the trusted authority removes the member to be removed from the list and updates the parameters for implementing the electronic signature anonymous, to take account of the member's withdrawal from the list; and</li><li>a phase of updating the certificates of the members of the list to take account of changes in the composition of the list.</li></ul>

0015According to one embodiment of the invention, the organization phase comprises the definition of a common parameter depending on the composition of the list, the phase of recording a person in the list comprising the definition of a parameter specific to the person to be registered which is calculated according to the parameter depending on the composition of the list and which is integrated into the certificate delivered to the person, the registration phase comprising a step of updating the common parameter depending on the composition of the list, the phase of revocation of a member of the list comprising a step of modifying the common parameter depending on the composition of the list, to take account of the member's removal from the list, and the phase for updating the certificates of the members of the list comprising a step of updating the parameter specific to each member of the list to take account of the modifications in the composition of the list.

0016According to one embodiment of the invention, a signature specific to a member of the list and having the certificate [A_i, e_i] includes T parameters₁, T₂, T₃ such as : <maths id="math0001"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">AT</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msup><mi mathvariant="normal">b</mi><mi mathvariant="normal">ω</mi></msup><mfenced><mi>mod n</mi></mfenced><mo>,</mo></math><img file="EP1523824B1_D0001.tif" /></maths><maths id="math0002"><math display="block"><msub><mi mathvariant="normal">T</mi><mn>2</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><mi mathvariant="normal">ω</mi></msup><mfenced><mi>mod n</mi></mfenced><mo>,</mo></math><img file="EP1523824B1_D0002.tif" /></maths><maths id="math0003"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">=</mo><mi mathvariant="normal">g</mi><mo>⁢</mo><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><mi mathvariant="normal">ω</mi></msup><mfenced><mi>mod n</mi></mfenced><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0003.tif" /></maths>ω being a number chosen randomly during the signature phase, and b, g, h and n being general parameters for implementing the group signature, such that the parameters b, g and h cannot be deduced each other by modulo n whole power elevation functions, so the number A_i, and therefore the identity of the member of the list with the certificate [A_i, e_i] cannot be inferred from a signature issued by the member.

0017Preferably, the number of a sequence used to generate a list signature is calculated as a function of a sequence start date.

0018Advantageously, the function for calculating the number of a sequence is of the form: <maths id="math0004"><math display="block"><mi mathvariant="normal">F</mi><mfenced><mi mathvariant="normal">d</mi></mfenced><mo mathvariant="normal">=</mo><msup><mfenced><mi mathvariant="normal">H</mi><mfenced><mi mathvariant="normal">d</mi></mfenced></mfenced><mn mathvariant="normal">2</mn></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0004.tif" /></maths>in which H is a hash function resistant to collisions, d is the start date of the sequence, and n is a general parameter for implementing the group signature.

0019According to one embodiment of the invention, a signature issued by a member of the list contains a parameter which is calculated according to the sequence number and the private key of the signatory member.

0020According to one embodiment of the invention, the parameter T₄ a signature issued by a member of the list and dependent on the sequence number m and the private key x_i of the signatory member is obtained by the following formula: <maths id="math0005"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">m</mi><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0005.tif" /></maths>n being a general parameter for implementing the group signature, and the signature comprising proof that the parameter T₄ was calculated with the private key x_i of the member of the list who issued the signature.

0021The invention also relates to an electronic voting method comprising an election organization phase, during which an organizing authority proceeds to the generation of parameters necessary for a vote, and assigns to tellers keys allowing them to decipher and verify. ballot papers, a phase of granting a signature right to each of the voters, a voting phase during which the voters sign a ballot, and a counting phase during which the tellers check the ballots, and calculate the result of the ballot according to the content of the deciphered and valid ballots. According to the invention, this method implements a list signing process as defined above, to sign the ballots, each voter being registered as a member of a list, and a sequence number being generated for the ballot, to detect whether or not the same voter has issued more than one ballot for the ballot.

0022According to one embodiment of the invention, the organization phase includes the delivery to each scrutineer of a public key and a private key, the ballot papers being encrypted using a public key obtained by the product of the respective public keys of all the tellers, and the corresponding private decryption key being obtained by calculating the sum of the respective private keys of all the tellers.

0023Advantageously, the encryption of the ballot papers is carried out using a probabilistic encryption algorithm.

0024According to one embodiment of the invention, the ballots cast by the voters are stored in a public database, the result of the verification and counting of each ballot being stored in the database in association with the ballot, and the private key for decrypting the ballots being published.

0025The invention also relates to a computer for implementing a list signature, comprising means for:<ul id="ul0004" list-style="dash" compact="compact"><li>generate parameters for implementing an anonymous electronic signature specific to the members of a list, the parameters comprising a private key and a corresponding public key; and</li><li>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</li><li>list member certificate.</li></ul>

0026According to the invention, the computer further comprises means for:<ul id="ul0005" list-style="dash" compact="compact"><li>generate a sequence number to be used by the members of the list to issue an anonymous signature specific to the members of the list, an anonymous signature issued by a member of the list comprising a signature element which is common to all the signatures issued by the same member of the list with the same sequence number, and which contains proof that the sequence number was used to generate the signature;</li><li>remove from the list a member to be revoked from the list, and update the parameters for implementing the anonymous electronic signature specific to the members of the list, to take account of the removal of the member from the list; and</li><li>update the certificates of the members of the list each time the composition of the list is modified.</li></ul>

0027The invention also relates to a computer for implementing an electronic voting method, comprising means for:<ul id="ul0006" list-style="dash" compact="compact"><li>generate, during an organization phase of a vote, parameters for implementing an anonymous electronic signature specific to the members of a list of electors, parameters comprising a private key and a corresponding public key;</li><li>assign to tellers keys allowing them to decipher and verify ballot papers issued for the ballot; and</li><li>transmitting to each member of the poll list, parameters to be used by the voter to calculate a private key, and a certificate of member of the poll list.</li></ul>

0028According to the invention, the computer further comprises means for:<ul id="ul0007" list-style="dash" compact="compact"><li>generate a poll-specific sequence number to be used by members of the list of electors to sign a ballot, a signature of a ballot comprising a signature element which is common to all signatures issued with the same sequence number by the same member of the poll list, and which contains proof that the sequence number was used to generate the signature;</li><li>remove from the list an elector from the poll to be revoked, and update the parameters for implementing the anonymous electronic signature specific to the members of the list of electors to reflect the withdrawal of the elector; and</li><li>update the certificates of polling voters each time the composition of the list of polling voters is changed.</li></ul>

0029The invention also relates to a terminal for issuing a list signature comprising means for:<ul id="ul0008" list-style="dash" compact="compact"><li>receive parameters for calculating a private key;</li><li>calculate the private key using the parameters received and parameters chosen randomly;</li><li>receive a list member certificate;</li><li>generating a signature specific to the members of the list, this signature being constructed so as to contain proof that the member of the list having issued the signature, knows a certificate of member of the list; and</li><li>verify a signature issued by a member of the list by applying a predefined algorithm to highlight the proof that the signature was issued by a person in possession of a list member certificate.</li></ul>

0030According to the invention, the terminal also comprises means for:<ul id="ul0009" list-style="dash" compact="compact"><li>receive a sequence number to be used in a signing phase;</li><li>generating a signature by calculating a signature element which is common to all the signatures issued by the same member of the list with the same sequence number, and which contains proof that the sequence number was used to generate the signature;</li><li>verify the proof that the sequence number was used to generate a signature; and</li><li>receive a new list member certificate each time the list composition changes.</li></ul>

0031The invention also relates to a terminal for issuing a signature of a ballot to a ballot, comprising means for:<ul id="ul0010" list-style="dash" compact="compact"><li>receive parameters for calculating a private key;</li><li>calculate the private key using the parameters received and parameters chosen randomly;</li><li>receive a membership certificate from a list of electors;</li><li>generating a signature of a ballot, this signature being constructed so as to contain proof that the member of the list having issued the signature, knows a certificate of member of the list of electors; and</li><li>verify a signature on a ballot, issued by a member of the voters list, by applying a predefined algorithm to highlight evidence that the signature was issued by a person in possession of a member's certificate the list.</li></ul>

0032According to the invention, the terminal also comprises means for:<ul id="ul0011" list-style="dash" compact="compact"><li>receive a sequence number to use to sign a ballot;</li><li>generate a signature of a ballot by calculating a signature element which is common to all the signatures issued by the same member of the list of electors with the same sequence number, and which contains proof that the sequence number was used to generate the signature;</li><li>verify the proof that the sequence number was used to generate a signature on a ballot; and</li><li>receive a new certificate from the list of electors each time the composition of the list of electors changes.</li></ul>

0033A preferred embodiment of the invention will be described below, by way of nonlimiting example, with reference to the appended drawings in which:<ul id="ul0012" list-style="none" compact="compact"><li>The <figref idref="f0001">figure 1</figref> shows a system for implementing the list signing and electronic voting methods according to the invention;</li><li>The <figref idref="f0001 f0002 f0003 f0004">figures 2 to 8</figref> illustrate in the form of flowcharts the various procedures which are executed in accordance with the list signing and electronic voting methods according to the invention.</li></ul>

0034The present invention provides a list signing method in which all authorized persons, i.e. belonging to the list, can produce a signature which is anonymous, and anyone is able to verify the validity of the signature without having access to the identity of the member of the list who signed.

0035Such a method can be implemented in the system shown in the <figref idref="f0001">figure 1</figref>. This system includes terminals 2 made available to users and connected to a network 5 for transmitting digital data, such as the Internet. Each terminal 2 is advantageously connected to a smart card reader 8 7. Via the network 5, users can connect to a server 6 giving access to information for example stored in a database 4. This system also includes a computer 1 of a trusted authority which in particular delivers smart cards 7 to users.

0036The list signing process according to the invention resumes in the group signing process described in the document referenced [1], the following procedures:<ul id="ul0013" list-style="dash" compact="compact"><li>a procedure for organizing a group of signatories, which consists of setting up the various parameters and public keys required,</li><li>a registration procedure in which a person to be registered in the group receives from a trusted authority a signing right, i.e. an authorized private key and certificate,</li><li>an actual signature procedure during which a person with signing rights signs a message, and</li><li>a verification procedure consisting in applying a verification algorithm to a signature to verify that the signature has been produced by a person having a signature right.</li></ul>

0037The invention further provides a provision for guaranteeing the anonymity of a signatory, even vis-à-vis a trusted authority, as well as a procedure for organizing a sequence consisting in defining a sequence number. to be used to generate list signatures, the verification of a signature further comprising a step of verifying that the signature is unique for a given sequence number.

0038The method according to the invention can also include a revocation procedure, as defined in the document referenced [2]. With the help of this revocation procedure, a trusted authority can withdraw from a member of the list, the signature rights that it previously assigned to it, based on the identity of the member. The implementation of this revocation possibility implies the execution by the members of the list of an updating procedure during which the members of the list update their certificates to take into account the modifications (addition or withdrawals) made from the list of persons authorized to sign.

0039The <figref idref="f0001">figure 2</figref> illustrates the different stages of the organization procedure 10 executed on the computer 1 of the trusted authority.

0040According to the document referenced [1], this procedure consists in choosing 11 of the following whole numbers:<ul id="ul0014" list-style="dash" compact="compact"><li>ε> 1, k, I_p,</li><li>λ₁, λ₂, γ₁, γ₂ which are lengths of whole numbers in numbers of bits, with: <maths id="math0006" num="(1)"><math display="block"><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">></mo><mn mathvariant="normal">4</mn><mo>⁢</mo><msub><mi mathvariant="normal">l</mi><mi mathvariant="normal">p</mi></msub></math><img file="EP1523824B1_D0006.tif" /></maths><maths id="math0007" num="(2)"><math display="block"><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">></mo><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">2</mn></math><img file="EP1523824B1_D0007.tif" /></maths><maths id="math0008" num="(3)"><math display="block"><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">></mo><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">+</mo><mn mathvariant="normal">2</mn></math><img file="EP1523824B1_D0008.tif" /></maths><maths id="math0009" num="(4)"><math display="block"><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">></mo><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">2</mn></math><img file="EP1523824B1_D0009.tif" /></maths>and to define the following sets of whole numbers: <maths id="math0010"><math display="block"><mi mathvariant="normal">Λ</mi><mo>=</mo><mrow><mo>]</mo></mrow><msup><mn>2</mn><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub></msup><mo>-</mo><msup><mn>2</mn><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub></msup><mo>,</mo><msup><mn>2</mn><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub></msup><mo>+</mo><msup><mn>2</mn><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub></msup><mrow><mo>[</mo></mrow></math><img file="EP1523824B1_D0010.tif" /></maths> and<maths id="math0011"><math display="block"><mi mathvariant="normal">Γ</mi><mo>=</mo><mrow><mo>]</mo></mrow><msup><mn>2</mn><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup><mo>-</mo><msup><mn>2</mn><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">2</mn></msub></msup><mo>,</mo><msup><mn>2</mn><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup><mo>+</mo><msup><mn>2</mn><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">2</mn></msub></msup><mrow><mo>[</mo></mrow><mn>.</mn></math><img file="EP1523824B1_D0011.tif" /></maths></li></ul>

0041This procedure also involves choosing a collision-resistant hash function <i>H</i> such that a binary sequence of any length denoted {0, 1} * is transformed into a binary sequence of length k denoted {0, 1}^k.

0042Then, the computer 1 of the trusted authority randomly generates, in step 12, prime numbers p 'and q' of size l_p, such that p = 2p '+ 1 and q = 2q' + 1 are also prime numbers. Then, it calculates in step 13 the module n = pq and randomly generates in step 14 whole numbers a, a₀, b, g and h in the QR set (n) of the quadratic residues of n, i.e. the set of whole numbers y such y = x² (mod n), x being an integer. We then consider that the public key PK of the trusted authority consists of the sequence of whole numbers (n, a, a₀, b, g, h) and that its private key consists of the sequence of whole numbers (p ', q').

0043To be registered by the trusted authority, a user wishing to become a member of the list performs on his terminal 2 the procedure 20 illustrated on the <figref idref="f0002">figure 3</figref>. The execution of this procedure initiates a dialogue with the computer 1 of the trusted authority which then executes a procedure 20 ′. Procedure 20 firstly comprises a step 21 of random generation of integers x̃_i and r̃, respectively in the intervals] 0, 2^λ2[and] 0, n²[. From these integers, we calculate 22 an integer C₁ such as : <maths id="math0012" num="(5)"><math display="block"><msub><mi mathvariant="normal">VS</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mover><mi mathvariant="normal">x</mi><mo mathvariant="normal">˜</mo></mover><mi mathvariant="normal">i</mi></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><mover><mi mathvariant="normal">r</mi><mo mathvariant="normal">˜</mo></mover></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0012.tif" /></maths>

0044In step 23, we build the proof U of the knowledge of two numbers α and β (i.e. x̃_i and r̃) such that C₁ = g^αh^β (mod n).

0045Such proof is for example constituted by randomly choosing two integers r₁ and r₂ in the set of binary numbers signed at ε (21_p + k) bits, noted ± {0, 1}^{ε (21}p^{+ k)}, and by calculating the following numbers: <maths id="math0013" num="(6)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">1</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">2</mn></msub></msup><mfenced><mi>mod n</mi></mfenced><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0013.tif" /></maths><maths id="math0014" num="(7)"><math display="block"><mi mathvariant="normal">vs</mi><mo>=</mo><mi>H</mi><mfenced><mi mathvariant="normal">g</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">h</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">VS</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">1</mn></msub></mfenced><mo>,</mo></math><img file="EP1523824B1_D0014.tif" /></maths>in which the symbol ∥ represents the concatenation operator, <maths id="math0015" num="(8)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">that</mi><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0015.tif" /></maths><maths id="math0016" num="(9)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn>2</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">cβ</mi><mn>.</mn></math><img file="EP1523824B1_D0016.tif" /></maths>s₁ and s₂ being whole numbers. The proof U is then equal to (c, s₁, s₂, Cl).

0046The number C₁ and the proof U are then sent to the trusted authority which verifies in step 21 'the proof U and that C₁ is found in the QR set (n) of the quadratic residues of n.

0047In the previous example, the verification of the proof U consists in calculating: <maths id="math0017" num="(10)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">VS</mi><mn mathvariant="normal">1</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">2</mn></msub></msup><mfenced><mi>modn</mi></mfenced><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0017.tif" /></maths> and<maths id="math0018" num="(11)"><math display="block"><mi mathvariant="normal">vs</mi><mo>=</mo><mi>H</mi><mfenced><mi mathvariant="normal">g</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">h</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">VS</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">1</mn></msub></mfenced><mn>.</mn></math><img file="EP1523824B1_D0018.tif" /></maths>

0048The proof is verified if c '= c and if s₁ and s₂ belong to the set ± {0, 1}^{ε (21}p^{+ k) +1}.

0049If this is the case, the computer 1 of the trusted authority randomly generates 22 'two whole numbers α_i, β_i in the meantime] 0, 2^λ2[, and sends these numbers to the user's terminal 2. In procedure 20, the user's terminal then calculates in step 24 the whole numbers x_i and C₂ by applying the following formulas: <maths id="math0019" num="(12)"><math display="block"><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">=</mo><msup><mn mathvariant="normal">2</mn><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub></msup><mo mathvariant="normal">+</mo><mfenced><msub><mi mathvariant="normal">α</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mover><mi mathvariant="normal">x</mi><mo mathvariant="normal">˜</mo></mover><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">β</mi><mi mathvariant="normal">i</mi></msub><mfenced><msup><mrow><mi>mod</mi><mo>⁢</mo><mn mathvariant="normal">2</mn></mrow><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub></msup></mfenced></mfenced><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0019.tif" /></maths> and<maths id="math0020" num="(13)"><math display="block"><msub><mi mathvariant="normal">VS</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">at</mi><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub></msup><mfenced><mi>modn</mi></mfenced><mn>.</mn></math><img file="EP1523824B1_D0020.tif" /></maths>

0050Then, in step 25, it constructs the following proofs (for example according to the same principle as the proof U):<ul id="ul0015" list-style="dash" compact="compact"><li>the proof V of knowing a number α belonging to the set A such that: <maths id="math0021" num="(14)"><math display="block"><msub><mi mathvariant="normal">VS</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">at</mi><mi mathvariant="normal">α</mi></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0021.tif" /></maths></li><li>the proof W to know three numbers β, γ, δ such that β ∈] - 2^λ2, 2^λ2 [and</li></ul><maths id="math0022" num="(15)"><math display="block"><msub><mi mathvariant="normal">VS</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">/</mo><msup><mi mathvariant="normal">at</mi><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub></msup><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">at</mi><mi mathvariant="normal">β</mi></msup></math><img file="EP1523824B1_D0022.tif" /></maths> and<maths id="math0023" num="(16)"><math display="block"><msubsup><mi mathvariant="normal">VS</mi><mn mathvariant="normal">1</mn><msub><mi mathvariant="normal">α</mi><mi mathvariant="normal">i</mi></msub></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">β</mi><mi mathvariant="normal">i</mi></msub></msup><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><mi mathvariant="normal">β</mi></msup><mo>⁢</mo><msup><mfenced><msup><mi mathvariant="normal">g</mi><msup><mn mathvariant="normal">2</mn><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub></msup></msup></mfenced><mi mathvariant="normal">γ</mi></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><mi mathvariant="normal">δ</mi></msup></math><img file="EP1523824B1_D0023.tif" /></maths>

0051VS₂ and the proofs V and W are then sent to the computer 1 of the trusted authority which verifies 23 'the proofs V and W, and that C₂ belongs to the QR (n) set. If this is the case, it randomly generates 24 'a prime number e_i belonging to the set Γ and applies the following formula: <maths id="math0024" num="(17)"><math display="block"><msub><mi mathvariant="normal">AT</mi><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">=</mo><msup><mfenced><msub><mi mathvariant="normal">VS</mi><mn mathvariant="normal">2</mn></msub><mo>⁢</mo><msub><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn></msub></mfenced><mrow><mn mathvariant="normal">1</mn><mo mathvariant="normal">/</mo><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></mrow></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0024.tif" /></maths>and returns the integers A to the user_i summer_i considered a certificate [A_i, e_i] the user's membership of the list. The computer 1 then creates 26 ′ a new entry in a table of the members of the list, for example in the database 4, in which it stores the certificate [A_i, e_i] with a view to modifications to the list (for example revocation of members), and preferably the messages exchanged between the trusted authority and the user during this user registration procedure.

0052Furthermore, the user can check 26 the authenticity of the received certificate by checking that the following equation is satisfied: <maths id="math0025" num="(18)"><math display="block"><msup><mi mathvariant="normal">at</mi><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub></msup><mo>⁢</mo><msub><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">AT</mi><mi mathvariant="normal">i</mi><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></msubsup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0025.tif" /></maths>

0053At the end of this registration procedure 20, the user therefore has a private key x_i and a certificate [A_i, e_i] of members of the list, which are for example stored in a smart card 7. Using such a certificate, the user can generate a signature of a message M belonging to the set {0, 1}^*. To this end, the trusted authority publishes according to the invention a sequence number m, chosen randomly from the set QR (n). This number must be used by the 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 should be impossible to calculate a discrete logarithm of a given sequence number, compared to the base of another sequence number, i.e. it should not be possible in practice calculate whole numbers x and y such that: m^x = m '^y (mod n), m and m 'being sequence numbers.

0054This sequence number m can be calculated according to the start date of the sequence: m = F (date). This function F is for example chosen equal to:<maths id="math0026" num="(19="><math display="block"><mi mathvariant="normal">F</mi><mfenced><mi mathvariant="normal">d</mi></mfenced><mo>=</mo><msup><mfenced><mi mathvariant="italic">Hʹ</mi><mfenced><mi mathvariant="normal">d</mi></mfenced></mfenced><mn>2</mn></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0026.tif" /></maths>in which <i>H</i>'a collision-resistant hash function, such as a binary sequence of any length denoted {0, 1}^* is transformed into a binary sequence of length 21_p noted {0, 1}²¹p. It is therefore easy to check the validity of the sequence number by applying formula (19).

0055The message signing procedure is designed in particular to allow a user to demonstrate that he knows a member's certificate and a member's private key and that he is using the correct sequence number. To sign a message M, a member of the list must execute, for example on his smart card 7 connected to a terminal 2 and memorizing his certificate [A_i, e_i] and his private key x_i, a signature procedure 30, illustrated on the <figref idref="f0003">figure 4</figref>. This procedure firstly includes a step 31 of random generation of a number ω belonging to the set {0, 1}²¹p_.It further comprises a step 32 consisting in calculating the following numbers from ω: <maths id="math0027" num="(20)"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">AT</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msup><mi mathvariant="normal">b</mi><mi mathvariant="normal">ω</mi></msup><mfenced><mi>mod n</mi></mfenced><mo>,</mo></math><img file="EP1523824B1_D0027.tif" /></maths><maths id="math0028" num="(21)"><math display="block"><msub><mi mathvariant="normal">T</mi><mn>2</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><mi mathvariant="normal">ω</mi></msup><mfenced><mi>mod n</mi></mfenced><mo>,</mo></math><img file="EP1523824B1_D0028.tif" /></maths><maths id="math0029" num="(22)"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><mi mathvariant="normal">ω</mi></msup><mfenced><mi>mod n</mi></mfenced><mn>.</mn></math><img file="EP1523824B1_D0029.tif" /></maths>

0056In accordance with the invention, the following number is also calculated: <maths id="math0030" num="(23)"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">m</mi><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0030.tif" /></maths>

0057In the following step 33, the numbers r are randomly generated₁ in the set of binary numbers signed at ε (γ₂+ k) bits, noted ± {0, 1}^{ε (γ}2^{+ k)}, r₂ overall ± {0, 1}^{ε (λ}2^{+ k)}, r₃ overall ± {0, 1}^{ε (γ}1⁺²¹p^{+ k + 1)} and r₄ overall ± {0, 1}^{ε (21}p^{+ k)}. Then, in step 34, the following quantities are calculated:<maths id="math0031" num="(24)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msup><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">1</mn></msub></msup><mo mathvariant="normal">/</mo><mfenced><msup><mi mathvariant="normal">at</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">2</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">y</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">3</mn></msub></msup></mfenced><mo>⁢</mo><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0031.tif" /></maths><maths id="math0032" num="(25)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn>2</mn></msub><mo mathvariant="normal">=</mo><msup><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn></msub><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">1</mn></msub></msup><mo mathvariant="normal">/</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">3</mn></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0032.tif" /></maths><maths id="math0033" num="(26)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">r</mi><mn>4</mn></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0033.tif" /></maths><maths id="math0034" num="(27)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">r</mi><mn>1</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">r</mi><mn>4</mn></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0034.tif" /></maths>

0058In accordance with the invention, the following number is also calculated: <maths id="math0035" num="(28)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">m</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">2</mn></msub></msup><mfenced><mi mathvariant="normal">m</mi><mo>⁢</mo><mi mathvariant="normal">o</mi><mo>⁢</mo><mi mathvariant="normal">d</mi><mspace width="1em" /><mi mathvariant="normal">not</mi></mfenced></math><img file="EP1523824B1_D0035.tif" /></maths>

0059Then, in step 35, the following numbers are calculated: <maths id="math0036" num="(29)"><math display="block"><mi mathvariant="normal">vs</mi><mo>=</mo><mi>H</mi><mfenced><mi mathvariant="normal">m</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">b</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">g</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">h</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">at</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">M</mi></mfenced><mo>,</mo></math><img file="EP1523824B1_D0036.tif" /></maths>in which ∥ represents the concatenation operation, <maths id="math0037" num="(31)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">-</mo><msup><mn mathvariant="normal">2</mn><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup></mfenced><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0037.tif" /></maths><maths id="math0038" num="(31)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn>2</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">-</mo><msup><mn mathvariant="normal">2</mn><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub></msup></mfenced><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0038.tif" /></maths><maths id="math0039" num="(32)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><mi mathvariant="normal">ω</mi><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0039.tif" /></maths><maths id="math0040" num="(33)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn>4</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">cω</mi><mo>,</mo></math><img file="EP1523824B1_D0040.tif" /></maths>s₁, s₂, s₃, s₄ being whole numbers.

0060The signature finally consists of the following set of numbers: <maths id="math0041" num="(34)"><math display="block"><mfenced><mi mathvariant="normal">vs</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">2</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">3</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">4</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub></mfenced><mn mathvariant="normal">.</mn></math><img file="EP1523824B1_D0041.tif" /></maths>which is for example transmitted by the network 5.

0061The verification of a signature of a message M takes place by executing the procedure 40 illustrated on the <figref idref="f0003">figure 5</figref>. This procedure comprises first of all in step 41, the calculation of the following numbers:<maths id="math0042" num="(35)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msup><msub><mi mathvariant="normal">vs</mi><mn mathvariant="normal">2</mn></msub><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msubsup><mo mathvariant="normal">/</mo><mfenced><msup><mi mathvariant="normal">at</mi><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">-</mo><msup><msub><mi mathvariant="normal">vs</mi><mn mathvariant="normal">2</mn></msub><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msup><mo>⁢</mo><msup><mi mathvariant="normal">b</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">3</mn></msub></msup></mfenced><mo>⁢</mo><mfenced><mi>mod</mi><mspace width="1em" /><mi mathvariant="normal">not</mi></mfenced></math><img file="EP1523824B1_D0042.tif" /></maths><maths id="math0043" num="(36)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msup><mrow><mi mathvariant="normal">vs</mi><mo>⁢</mo><mn mathvariant="normal">2</mn></mrow><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msubsup><mo mathvariant="normal">/</mo><mfenced><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">3</mn></msub></msup></mfenced><mo>⁢</mo><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0043.tif" /></maths><maths id="math0044" num="(37)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">4</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0044.tif" /></maths><maths id="math0045" num="(38)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">g</mi><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msup><mrow><mi mathvariant="normal">vs</mi><mo>⁢</mo><mn mathvariant="normal">2</mn></mrow><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">4</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0045.tif" /></maths>

0062According to the invention, it also includes the calculation of the following numbers: <maths id="math0046" num="(39)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">T</mi><mn>4</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">m</mi><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">-</mo><msup><mrow><mi mathvariant="normal">vs</mi><mo>⁢</mo><mn mathvariant="normal">2</mn></mrow><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0046.tif" /></maths><maths id="math0047" num="(39)"><math display="block"><mi mathvariant="normal">vs</mi><mo>=</mo><mi>H</mi><mfenced><mi mathvariant="normal">m</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">b</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">g</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">h</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">at</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">M</mi></mfenced></math><img file="EP1523824B1_D0047.tif" /></maths>

0063The signature is authentic if the following conditions are verified in step 42: <maths id="math0048" num="(41)"><math display="block"><mi mathvariant="normal">vs</mi><mo>=</mo><mi mathvariant="normal">vs</mi></math><img file="EP1523824B1_D0048.tif" /></maths><maths id="math0049" num="'42)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0049.tif" /></maths><maths id="math0050" num="(43)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn>2</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0050.tif" /></maths><maths id="math0051" num="(44)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">+</mo><mn mathvariant="normal">2</mn><mo>⁢</mo><msub><mi mathvariant="normal">l</mi><mi mathvariant="normal">p</mi></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0051.tif" /></maths><maths id="math0052" num="(45)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><mn mathvariant="normal">2</mn><mo>⁢</mo><msub><mi mathvariant="normal">l</mi><mi mathvariant="normal">p</mi></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup><mn mathvariant="normal">.</mn></math><img file="EP1523824B1_D0052.tif" /></maths>

0064If these conditions are not verified, the signature is not valid (step 45).

0065Furthermore, by accessing all the signatures which have been produced during a given sequence, for example in database 4, it is easy to verify in step 43, using the parameter T₄, if a member of the list has signed several times: all the signatures issued by a member of the list include a parameter T₄ having the same value for a given sequence number. It should also be noted that a member cannot cheat using another value because T₄ is strongly linked to T₁. Indeed, the formula for calculating T₁ can also be written as follows: <maths id="math0053" num="(46)"><math display="block"><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></msubsup><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn></msub><mo>⁢</mo><msup><mi mathvariant="normal">at</mi><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">b</mi><mrow><mi mathvariant="normal">ω</mi><mo>⁢</mo><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></mrow></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0053.tif" /></maths>

0066If T₄ is already in the set of signatures issued for a given sequence number, it is deduced therefrom that the signature has already been issued by a member of the list for this sequence number (step 46).

0067To include a possibility of revoking a member of the list, the process which has just been described can be modified as follows.

0068The organization procedure 10 of the list further comprises in step 14, the random choice of a number u belonging to the set QR (n), and the definition of two sets E_add summer_{of the} which are initially empty.

0069The public key PK of the trusted authority then consists of the sequence of integers (n, a, a₀, b, g, h, u) and sets E_add summer_{of the}.

0070During the registration procedure 20, 20 ', the computer 1 of the trusted authority assigns in step 25' the parameter u_i to the new member U_i from the list, this parameter being such that u_i = u, and updates the value of the parameter u by replacing this value with u^ei.

0071The certificate of the new member then groups the integers A_i, e_i and you_i, this certificate being stored in step 26 'for future modifications and transmitted to the new member. The trusted authority also enters the number e_i assigned to new member in set E_add.

0072Upon receipt of his certificate, the new member also checks that: <maths id="math0054" num="(47)"><math display="block"><msup><msub><mi mathvariant="normal">u</mi><mi mathvariant="normal">i</mi></msub><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></msup><mo mathvariant="normal">=</mo><mi mathvariant="normal">u</mi><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0054.tif" /></maths>

0073The other U members_j 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 in recalculating their parameter u_j as follows : <maths id="math0055" num="(48)"><math display="block"><msub><mi mathvariant="normal">u</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">=</mo><msup><msub><mi mathvariant="normal">u</mi><mi mathvariant="normal">i</mi></msub><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0055.tif" /></maths>

0074In this way, relation (47) is always checked for all couples (u_j, e_j) of all members of the list.

0075The procedure for revoking a U member_k from the list whose certificate is (A_k, e_k, u_k) is for the trusted authority to modify the parameter u as follows: <maths id="math0056" num="(49)"><math display="block"><mi mathvariant="normal">u</mi><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">u</mi><mrow><mn mathvariant="normal">1</mn><mo mathvariant="normal">/</mo><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">k</mi></msub></mrow></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0056.tif" /></maths>and introduce the parameter e_k overall E_{of the}.

0076In addition, each non-revoked member U_j of the list must take this revocation into account (change of parameter u) by recalculating its parameter u_j as follows : <maths id="math0057" num="(50)"><math display="block"><msub><mi mathvariant="normal">u</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">=</mo><msup><msub><mi mathvariant="normal">u</mi><mi mathvariant="normal">j</mi></msub><mi mathvariant="normal">b</mi></msup><mo>⁢</mo><msup><mi mathvariant="normal">u</mi><mi mathvariant="normal">at</mi></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0057.tif" /></maths>a and b being such that ae_j + be_k = 1

0077To determine a and b, it suffices to apply the extended Euclidean algorithm consisting in performing a series of Euclidean divisions.

0078It should be noted that the revoked member (having e_k) cannot determine a and b using formula (50) which becomes e_k(a + b) = 1, and therefore recalculate the parameter u_k.

0079During the procedure 30 of signature by a member of the list, it is also necessary in step 31 to randomly choose numbers w₁, w₂ and w₃ of binary length equal to 21_p, i.e. belonging to the set {0, 1}²¹p, and calculate in step 32 the following numbers: <maths id="math0058" num="(51)"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">1</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0058.tif" /></maths><maths id="math0059" num="(52)"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">6</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">u</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">2</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0059.tif" /></maths><maths id="math0060" num="(53)"><math display="block"><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">7</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">w</mi><mn>2</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">3</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0060.tif" /></maths>

0080It is also necessary in step 33 to randomly choose numbers r₅, r₆, r₇ belonging to the set ± {0, 1}^{ε (21}p^{+ k)} and numbers r₈ and r₉ belonging to the set ± {0, 1}^{ε (γ}1⁺²¹p^{+ k + 1)}, then calculate in step 34 the following numbers: <maths id="math0061" num="(54)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">6</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">r</mi><mn>1</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">5</mn></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0061.tif" /></maths><maths id="math0062" num="(55)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">7</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">r</mi><mn>6</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">7</mn></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0062.tif" /></maths><maths id="math0063" num="(56)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">6</mn></msub><mo mathvariant="normal">=</mo><msup><msub><mi mathvariant="normal">T</mi><mn>6</mn></msub><msub><mi mathvariant="normal">r</mi><mn>1</mn></msub></msup><mo>/</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">8</mn></msub></msup><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0063.tif" /></maths><maths id="math0064" num="(57)"><math display="block"><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">9</mn></msub><mo mathvariant="normal">=</mo><msup><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">7</mn></msub><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">1</mn></msub></msup><mo mathvariant="normal">/</mo><mfenced><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">8</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">9</mn></msub></msup></mfenced><mo>⁢</mo><mfenced><mi>mod n</mi></mfenced></math><img file="EP1523824B1_D0064.tif" /></maths>

0081The number c then includes the following: <maths id="math0065" num="(58)"><math display="block"><mi mathvariant="normal">vs</mi><mo>=</mo><mi>H</mi><mfenced><mi mathvariant="normal">m</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">b</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">g</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">h</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">at</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn>5</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn>6</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn>7</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn>6</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn>7</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn>8</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">d</mi><mn>9</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">M</mi></mfenced></math><img file="EP1523824B1_D0065.tif" /></maths>

0082It is still necessary to calculate in step 35: <maths id="math0066" num="(59)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">1</mn></msub></math><img file="EP1523824B1_D0066.tif" /></maths><maths id="math0067" num="(60)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn>6</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">6</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">2</mn></msub></math><img file="EP1523824B1_D0067.tif" /></maths><maths id="math0068" num="(61)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn>7</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">7</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><msub><mi mathvariant="normal">w</mi><mn>3</mn></msub></math><img file="EP1523824B1_D0068.tif" /></maths><maths id="math0069" num="(62)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">8</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn mathvariant="normal">8</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">2</mn></msub></math><img file="EP1523824B1_D0069.tif" /></maths><maths id="math0070" num="(63)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn>9</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">r</mi><mn>9</mn></msub><mo mathvariant="normal">-</mo><mi mathvariant="normal">vs</mi><mo>⁢</mo><msub><mi mathvariant="normal">e</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">w</mi><mn>3</mn></msub></math><img file="EP1523824B1_D0070.tif" /></maths>

0083The signature then consists of the following set of numbers: <maths id="math0071" num="(64)"><math display="block"><mfenced><mi mathvariant="normal">vs</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">2</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">3</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">4</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">5</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">6</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">7</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">8</mn></msub><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">9</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">5</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">6</mn></msub><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">7</mn></msub></mfenced><mn mathvariant="normal">.</mn></math><img file="EP1523824B1_D0071.tif" /></maths>

0084The procedure 40 for verifying a signature then further comprises the calculation of the following numbers in step 41: <maths id="math0072" num="(65)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">6</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">T</mi><mn>5</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">g</mi><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msup><mrow><mi mathvariant="normal">vs</mi><mo>⁢</mo><mn mathvariant="normal">2</mn></mrow><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">5</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0072.tif" /></maths><maths id="math0073" num="(66)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">7</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">7</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">6</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">7</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0073.tif" /></maths><maths id="math0074" num="(67)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">8</mn></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">u</mi><mi mathvariant="normal">vs</mi></msup><mo>⁢</mo><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">6</mn><mi mathvariant="normal">vs</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="normal">g</mi><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msup><mrow><mi mathvariant="normal">vs</mi><mo>⁢</mo><mn mathvariant="normal">2</mn></mrow><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msup><mo mathvariant="normal">/</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">8</mn></msub></msup><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0074.tif" /></maths><maths id="math0075" num="(68)"><math display="block"><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">9</mn></msub><mo mathvariant="normal">=</mo><msubsup><mi mathvariant="normal">T</mi><mn mathvariant="normal">7</mn><mrow><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msup><mrow><mi mathvariant="normal">vs</mi><mo>⁢</mo><mn mathvariant="normal">2</mn></mrow><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub></msup></mrow></msubsup><mo mathvariant="normal">/</mo><mfenced><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">8</mn></msub></msup><mo>⁢</mo><msup><mi mathvariant="normal">h</mi><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">9</mn></msub></msup></mfenced><mo>⁢</mo><mfenced><mi>modn</mi></mfenced></math><img file="EP1523824B1_D0075.tif" /></maths><maths id="math0076" num="(69)"><math display="block"><mi mathvariant="normal">vs</mi><mo>=</mo><mi>H</mi><mfenced><mi mathvariant="normal">m</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">b</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">g</mi><mo mathvariant="normal">‖</mo><mi mathvariant="normal">h</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">at</mi><mn mathvariant="normal">0</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">at</mi><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn>5</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn>6</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">T</mi><mn>7</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">4</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn>6</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn>7</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn>8</mn></msub><mo mathvariant="normal">‖</mo><msub><mi mathvariant="normal">t</mi><mn>9</mn></msub><mo mathvariant="normal">‖</mo><mi mathvariant="normal">M</mi></mfenced></math><img file="EP1523824B1_D0076.tif" /></maths>

0085The signature is authentic if the following additional conditions are verified in step 42: <maths id="math0077" num="(70)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">5</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><mn mathvariant="normal">2</mn><mo>⁢</mo><msub><mi mathvariant="normal">l</mi><mi mathvariant="normal">p</mi></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0077.tif" /></maths><maths id="math0078" num="(71)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">6</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><mn mathvariant="normal">2</mn><mo>⁢</mo><msub><mi mathvariant="normal">l</mi><mi mathvariant="normal">p</mi></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0078.tif" /></maths><maths id="math0079" num="(72)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">7</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><mn mathvariant="normal">2</mn><mo>⁢</mo><msub><mi mathvariant="normal">l</mi><mi mathvariant="normal">p</mi></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">,</mo></math><img file="EP1523824B1_D0079.tif" /></maths><maths id="math0080" num="(73)"><math display="block"><msub><mi mathvariant="normal">s</mi><mn mathvariant="normal">8</mn></msub><mo mathvariant="normal">∈</mo><mo mathvariant="normal">±</mo><msup><mfenced open="{" close="}"><mn mathvariant="normal">0</mn><mn mathvariant="normal">1</mn></mfenced><mrow><mi mathvariant="normal">ε</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">γ</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">+</mo><mn mathvariant="normal">2</mn><mo>⁢</mo><msub><mi mathvariant="normal">l</mi><mi mathvariant="normal">p</mi></msub><mo mathvariant="normal">+</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mfenced><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msup></math><img file="EP1523824B1_D0080.tif" /></maths> and<maths id="math0081" num="(74)"><math display="block"><msub><mi>s</mi><mn>9</mn></msub><mo>∈</mo><mo>±</mo><msup><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced><mrow><mi>ε</mi><mo>⁢</mo><mfenced><msub><mi>γ</mi><mn>1</mn></msub><mo>+</mo><mn>2</mn><mo>⁢</mo><msub><mi>l</mi><mi>p</mi></msub><mo>+</mo><mi>k</mi><mo>+</mo><mn>1</mn></mfenced><mo>+</mo><mn>1</mn></mrow></msup><mn>.</mn></math><img file="EP1523824B1_D0081.tif" /></maths>

0086It should be noted that unlike the group signature described in document [1], it is not possible for the trusted authority to find the identity of a signatory, i.e. the number AT_i the signer's certificate from a list signature as described. In fact, unlike the process 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 deduced from T₁ and T_2.

0087In addition, the signature generated by a revoked member U_k will be detected invalid. Indeed, the parameter T₆ involves the parameter u_k which was determined from the common parameter u, and the parameter t₈ which is calculated to verify the signature also involves the parameter u which has been modified following the revocation of the member k. It follows that, during the signature verification, the parameters T₆ and t₈ are inconsistent, and therefore the equality between c and c 'cannot be verified by the signature of member k.

0088The list signing process which has just been described can be applied to an electronic voting process. The electronic voting method according to the invention comprises several phases including the execution of the procedures of the list signing method described above.

0089This process involves the intervention of a trusted authority 1 organizing the elections, which for this purpose performs a procedure 50 for organizing the ballot. This procedure consists of generating the data necessary for the smooth running of the elections, a public database accessible to all in which the ballot papers are collected. During the organization of the ballot, scrutineers are also appointed who will count the votes and determine the result of the election.

0090The organizing authority first of all generates the various parameters necessary for setting up a list signature, by executing the procedure 10 for organizing a list signature. Voters must then register beforehand, for example in a town hall, on an electoral list so as to receive all the necessary data, namely a private key x_i and a certificate (A_i, e_i, u_i), to generate a list signature. Using these parameters, voters can participate in all future elections. This registration procedure can for example be executed between a smart card 7 and a terminal 2, the smart card storing at the end of the procedure the voter certificate.

0091Before an election, the organizing authority updates the electoral lists by performing the 20, 20 'procedure for newly registered voters, and removing (revoking) the rights to sign the list from all those struck off the registers electoral (for example people who left the constituency or deprived of their civil rights). These revocations are carried out by executing the revocation procedure described above. In step 51 of procedure 50, the organizing authority also publishes a sequence number m necessary for setting up a new list signing sequence, so as to prevent voters from voting (signing) twice. in this election.

0092In addition, the tellers will create 52 the necessary public / private key pairs, so that they must all cooperate in order to be able to decrypt an encrypted message with the public key. To this end, the cryptographic system put in place is chosen so as to allow a voter to encrypt a message (ballot paper) using at least one public key, while imposing the cooperation of all the tellers for use the corresponding private key (s), and thus decrypt the message.

0093The sharing of the private decryption key between all of the tellers can be done as follows.

0094We consider g a generator of the cyclic group G. A private key x_i is assigned to each scrutineer i who calculates the number y_i belonging to G such as: <maths id="math0082" num="(75)"><math display="block"><msub><mi mathvariant="normal">y</mi><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub></msup></math><img file="EP1523824B1_D0082.tif" /></maths>

0095The public key Y to be used by voters is obtained by the following formula: <maths id="math0083" num="(76)"><math display="block"><mi mathvariant="normal">Y</mi><mo mathvariant="normal">=</mo><munder><mi mathvariant="normal">Π</mi><mi mathvariant="normal">i</mi></munder><mo>⁢</mo><msub><mi mathvariant="normal">y</mi><mi mathvariant="normal">i</mi></msub></math><img file="EP1523824B1_D0083.tif" /></maths>and the corresponding private key X shared by all the tellers i is as follows: <maths id="math0084" num="(77)"><math display="block"><mi mathvariant="normal">X</mi><mo mathvariant="normal">=</mo><munder><mi mathvariant="normal">Σ</mi><mi mathvariant="normal">i</mi></munder><mo>⁢</mo><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">i</mi></msub></math><img file="EP1523824B1_D0084.tif" /></maths>

0096A similar result can be achieved by encrypting using all of the respective public keys of the tellers. Decryption requiring knowledge of all corresponding private keys.

0097Before going to vote, each voter must update their list signing certificate in accordance with the modification procedure described above, using the parameters published previously. If the elector is not removed from the electoral lists, this modification can be made.

0098During the opening of the polling stations, each voter issues a ballot by executing a procedure 60 on a terminal. In step 61, the voter selects his vote v_i and encrypts it using the scrutineers' public key to obtain an encrypted vote D_i. Then he signs the encrypted vote using the list signing process to obtain an S signature_i. The ballot made up of the whole (D_i, S_i) of the vote and signature, is then published anonymously in a public database 4.

0099In step 62, the encryption of the vote is carried out using a probabilistic encryption algorithm (that is to say that the probability that two ciphers of the same message are identical is almost zero), such as for example l 'El Gamal or Paillier algorithm. If we apply the El Gamal algorithm, the encryption is done by calculating the following numbers:<maths id="math0085" num="(78)"><math display="block"><msub><mi mathvariant="normal">at</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">v</mi><mi mathvariant="normal">j</mi></msub><mo>⁢</mo><msup><mi mathvariant="normal">Y</mi><mi mathvariant="normal">r</mi></msup><mspace width="1em" /><mi>and</mi><mspace width="1em" /><msub><mi mathvariant="normal">b</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">=</mo><msup><mi mathvariant="normal">g</mi><mi mathvariant="normal">r</mi></msup></math><img file="EP1523824B1_D0085.tif" /></maths>where r is a random element. The vote v_j encrypted then consists of the couple D_j = (a_j, b_j). Elector E_j calculate 63 then the signature of the encrypted vote list S_j = Sig_listing(at_j∥b_j), Sig_listing being the signature of the list as described above, by executing the procedure 30 by its smart card 7, which is transmitted to the terminal 2.

0100Elector E_j thus generated his ballot (D_j, S_j) that it sends 64 to the public database 4 by means of an anonymous transmission channel, that is to say prohibiting the linking of a message transmitted to the transmitter thereof. The voter can use a public terminal or a network of mixers for this purpose.

0101At the end of the poll, the tellers carry out the counting of the votes by executing the procedure 70 on the terminal 3. This procedure consists first of all in generating 71 the private decryption key X from their respective private keys X_i and using the formula (77). Then, in step 72, they access the public database 4 of the ballots to obtain the ballots (D_i, S_i) and to decipher them. The actual deciphering of the ballots consists, for each ballot issued (step 73), of checking 74 the signature S_i by executing the list signature verification procedure 40 described above, and if the signature is valid and unique (step 75), to decrypt 76 the encrypted vote D_j by applying the following formula: <maths id="math0086" num="(79)"><math display="block"><msub><mi mathvariant="normal">v</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">at</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">/</mo><msup><msub><mi mathvariant="normal">b</mi><mi mathvariant="normal">j</mi></msub><mi mathvariant="normal">X</mi></msup></math><img file="EP1523824B1_D0086.tif" /></maths>

0102Votes_j 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 (D_j, S_j). The private decryption key X is also published to allow everyone to check the counting of the ballots.

0103Once all the ballots have been counted, this procedure 70 calculates in step 78 the result of the election and updates the public database of ballots by entering this result, and possibly the key private decryption X.

0104It is easy to see that the properties set out above, necessary for the implementation 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 not take into account the two votes or count only one vote if they are identical. Alternatively, it can be provided that in step 64 of inserting a vote in the database 4, it is verified that the vote cast by the voter does not already appear in the database by searching for the parameter there. T₄ specific to the voter. If it is thus detected that the voter has already voted for this ballot, the new vote is not inserted in the database 4.

0105Then, it is not possible to start counting the ballots before the end of the poll if at least one of the scrutineers respects the rule, since it takes the presence of all the scrutineers to count a ballot. Finally, the result of the election is verifiable by all since the tellers provide in the database all the elements necessary (in particular the private counting key) to carry out such a verification, and that the verification of a signature is accessible to all using the public key PK = (n, a, a₀, b, g, h, u) of the trusted authority. So anyone can count the votes in the same way as the tellers and therefore ensure that it has been done correctly.

0106The tellers' keys are of course obsolete at the end of the poll, since they are published.