Signature with pseudonym for chip card

Abstract

The invention relates to a method of signature with pseudonym of a message m by a user device storing a secret signature key sk dependent at least on a first part of key f, on a second part of key x and on a third part of key A equal to (g.sub.1h.sup.f).sup.1/(x+y) and comprising the following steps: generation of a pseudonym nym equal to h.sup.f dpk.sup.x, with dpk a public domain parameter, determination of random numbers a, r_a, r_f, r_x, r_b, r_d, calculation of signature coefficients R.sub.1 equal to h.sup.r.sup._.sup.Jdpk.sup.r.sup._.sup.x, R.sub.2 equal to nym.sup.r.sup._.sup.ah.sup.r.sup._.sup.ddpk.sup.r.sup._.sup.b, R.sub.3 equal to Z.sup.r.sup._.sup.x V.sup.ar.sup._.sup.xr.sup._.sup.fr.sup._.sup.b W.sup.r.sup._.sup.a, with Z, V and W respectively equal to e(A, g.sub.2), e(h, g.sub.2) and e(h,w), obtaining of a first signature parameter T equal to Ah.sup.a, calculation of a second signature parameter c by applying a cryptographic hash function H, to the public domain parameter dpk, to the pseudonym nym, to the first signature parameter T, to the signature coefficients R.sub.1, R.sub.2, R.sub.3 and to the message m, calculation of signature parameters s_f, s_x, s_a, s_b, s_d, respectively equal to r_f+c.f, r_x+c.x, r_a+c.a, r_b+c.a.x and r_d+c.a.f, generation of said signature with pseudonym of said message m on the basis of said signature parameters.

Claims

1. A pseudonym signing method of a message by a user device comprising processing means, interface means and storage means, the storage means of said user device storing a secret signature key function at least: of a modular integer f constituting a first key part, of a modular integer x constituting a second key part, of a third key part A equal to (g.sub.1h.sup.f).sup.1/(x+) with: g.sub.1 and h first and second elements of a group G.sub.1, said first and second elements g.sub.1 and h of the group G.sub.1 being public parameters and, g.sub.2 an element of a group G.sub.2, said element g.sub.2 of the group G.sub.2 being a public parameter, a modular integer constituting a secret management key, such as w equal to g.sub.2.sup. with w a public parameter, and comprising the following steps implemented by the processing means of said user device: generating a pseudonym nym identifying the user of said user device and equal to h.sup.fdpk.sup.x, with dpk a public domain parameter, determining first, second, third, fourth, fifth and sixth modular random integers a, r_a, r_f, r_x, r_b, r_d, calculating a first signing coefficient R.sub.1 equal to h.sup.r.sup._.sup.fdpk.sup.r.sup._.sup.x, calculating a second signing coefficient R.sub.2 equal to nym.sup.r.sup._.sup.ah.sup.r.sup._.sup.ddpk.sup.r.sup._.sup.b, obtaining a third signing coefficient R.sub.3 equal to Z.sup.r.sup._.sup.x V.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b W.sup.r.sup._.sup.a, with Z, V and W of first, second and third coupling results respectively equal to e(A, g.sub.2), e(h, g.sub.2) and e(h,w), and e a bilinear application of G.sub.1G.sub.2 in a group G.sub.T, said application e being a public parameter, obtaining a first signing parameter T equal to Ah.sup.a, calculating a second signing parameter c by applying a cryptographic hash function H to the public domain parameter dpk, the pseudonym nym, the first signing parameter T, the first, second and third signing coefficients R.sub.1, R.sub.2, R.sub.3 and the message m, calculating third, fourth, fifth, sixth and seventh signing parameters s_f, s_x, s_a, s_b, s_d, respectively equal to r_f+c.f, r_x+c.x, r_a+c.a, r_b+c.a.x and r_d+c.a.f, generating said pseudonym signature of said message from said signing parameters.

2. The pseudonym signing method according to claim 1, comprising a generation step of at least one element of the first key part by the processing means of the user device, a transmission step by the interface means of the user device of an identity datum generated from said at least one generated element of said first key part, so as to prove, by a proof algorithm with zero knowledge proof, to a key-managing authority the knowledge by the user device of said at least one generated element of the first key part, a reception step by the interface means of the user device of second and third key parts generated by the key-managing authority.

3. The pseudonym signing method according to claim 1, wherein the first coupling result and/or the second and third coupling results are calculated prior to the step of obtaining the third signing coefficient.

4. The pseudonym signing method according to claim 1, wherein the second and third coupling results are public parameters.

5. The pseudonym signing method according to claim 1, comprising a reception step, by the interface means of the user device, of the first coupling result calculated by a processing unit of a management server of a key-managing authority.

6. The pseudonym signing method according to claim 1, wherein the step of obtaining the first signing parameter comprises a calculation step of the first signing parameter performed by the processing means of the user device.

7. The pseudonym signing method according to claim 1, wherein the step of obtaining the first signing parameter comprises a transmission step by the interface means of the user device of the first determined random integer to a remote processing device and a reception step by the interface means of the user device of the first signing parameter calculated by the remote processing device and equal to Ah.sup.a.

8. The pseudonym signing method according to claim 1, wherein the step of obtaining the third signing coefficient comprises a calculation step of the third signing coefficient implemented by the processing means of the user device.

9. The pseudonym signing method according to claim 1, wherein the step of obtaining the third signing coefficient comprises: a calculation step by the processing means of the user device of a fourth signing coefficient B.sub.1 equal to A.sup.r.sup._.sup.xh.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b and a fifth signing coefficient B.sub.2 equal to h.sup.r.sup._.sup.a, a transmission step by the interface means of the user device of said fourth and fifth signing coefficients B.sub.1 and B.sub.2 to a remote processing device, a reception step by the interface means of the user device of the third signing coefficient, said third signing coefficient being calculated by the remote processing device and equal to e(B1, g.sub.2)e(B2,w).

10. A signing method according to claim 1, wherein the step of obtaining the third signing coefficient comprises: a calculation step by the processing means of the user device of a sixth signing coefficient B equal to A.sup.r.sup._.sup.xh.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b, a transmission step by the interface means of the user device of the sixth signing coefficient B and of the second determined random integer to a remote processing device, a reception step by the interface means of the user device of the third signing coefficient, said third signing coefficient being calculated by said remote processing device and equal to e(B, g.sub.2)W.sup.r.sup._.sup.a.

11. A control method of signing a message and a pseudonym, said signature and said pseudonym being generated according to the method of claim 1, said control method comprising the following steps implemented by processing means of a control server: calculating a first control coefficient R.sub.1 equal to h.sup.s.sup._.sup.fdpk.sup.s.sup._.sup.xnym.sup.c, calculating a second control coefficient R.sub.2 equal to nym.sup.s.sup._.sup.ah.sup.s.sup._.sup.ddpk.sup.s.sup._.sup.b, calculating a third control coefficient R.sub.3 equal to e(T,g.sub.2).sup.s.sup._.sup.x V.sup.s.sup._.sup.fs.sup._.sup.b W.sup.s.sup._.sup.a[e(g.sub.1,g.sub.2)e(T,w).sup.1].sup.c, calculating a control parameter c by applying a hash function H to a public domain parameter, the pseudonym, a first signing parameter, the first, second and third control coefficients and the message, comparing a second signing parameter and the control parameter, said signature being valid in case of equality of the second signing parameter and of the control parameter; with: f a modular integer constituting a first key part, x a modular integer constituting a second key part, A a third key part equal to (g.sub.1h.sup.f).sup.1/(x+), g.sub.1 and h first and second elements of a group G.sub.1, said first and second elements g.sub.1 and h of the group G.sub.1 being public parameters and, g.sub.2 an element of a group G.sub.2, said element g.sub.2 of the group G.sub.2 being a public parameter, a modular integer constituting a secret management key, such as w equal to g.sub.2.sup. with w a public parameter, e a bilinear application of G.sub.1G.sub.2 in a group G.sub.T, said application e being a public parameter, Z, V and W first, second and third coupling results respectively equal to e(A, g.sub.2), e(h, g.sub.2) and e(h,w), a, r_a, r_f, r_x, r_b, r_d first, second, third, fourth, fifth and sixth modular random integers, T a first signing parameter equal to Ah.sup.a, c a second signing parameter calculated by applying the cryptographic hash function H to the public domain parameter dpk, the pseudonym nym, the first signing parameter T, first, second and third signing coefficients R.sub.1, R.sub.2, R.sub.3 and to the message m, where the first signing coefficient R.sub.1 is equal to h.sup.r.sup._.sup.xdpk.sup.r.sup._.sup.x, the second signing coefficient R.sub.2 is equal to nym.sup.r.sup._.sup.ah.sup.r.sup._.sup.ddpk.sup.r.sup._.sup.b, the third signing coefficient R.sub.3 is equal to Z.sup.r.sup._.sup.x V.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b W.sup.r.sup._.sup.a, and s_f, s_x, s_a, s_b, s_d third, fourth, fifth, sixth and seventh signing parameters respectively equal to r_f+c.f, r_x+c.x, r_a+c.a, r_b+c.a.x and r_d+c.a.f.

12. A computer program comprising program code instructions for execution of the steps of the method according to claim 1 when said programme is executed on a computer.

13. A user device comprising at least storage means, processing means and communication interface means, wherein it is configured to implement a signing method according to claim 1.

14. A control server comprising at least storage means, processing means and interface means wherein it is configured to implement a control method according to claim 11.

15. A system comprising at least one user device including at least storage means, processing means and communication interface means, configured to implement a pseudonym signing method of a message by a user device comprising processing means, interface means and storage means, the storage means of said user device storing a secret signature key function at least: of a modular integer f constituting a first key part, of a modular integer x constituting a second key part, of a third key part A equal to (g.sub.1h.sup.f).sup.1/(x+) g.sub.1.h.sup.f).sup.1/(x+) with: g.sub.1 and h first and second elements of a group G.sub.1, said first and second elements g.sub.1 and h of the group G.sub.1 being public parameters and, g.sub.2 an element of a group G.sub.2, said element g.sub.2 of the group G.sub.2 being a public parameter, a modular integer constituting a secret management key, such as w equal to g.sub.2.sup. with w a public parameter, and comprising the following steps implemented by the processing means of said user device: generating a pseudonym nym identifying the user of said user device and equal to h.sup.f.dpk.sup.x, with dpk a public domain parameter, determining first, second, third, fourth, fifth and sixth modular random integers a, r_a, r_f, r_x, r_b, r_d, calculating a first signing coefficient R.sub.1 equal to h.sup.r.sup._.sup.fdpk.sup.r.sup._.sup.x, calculating a second signing coefficient R.sub.2 equal to nym.sup.r.sup._.sup.ah.sup.r.sup._.sup.ddpk.sup.r.sup._.sup.b, obtaining a third signing coefficient R.sub.3 equal to Z.sup.r.sup._.sup.x V.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b W.sup.r.sup._.sup.a, with Z, V and W of first, second and third coupling results respectively equal to e(A, g.sub.2), e(h, g.sub.2) and e(h,w), and e a bilinear application of G.sub.1G.sub.2 in a group G.sub.T, said application e being a public parameter, obtaining a first signing parameter T equal to Ah.sup.a, calculating a second signing parameter c by applying a cryptographic hash function H to the public domain parameter dpk, the pseudonym nym, the first signing parameter T, the first, second and third signing coefficients R.sub.1, R.sub.2, R.sub.3 and the message m, calculating third, fourth, fifth, sixth and seventh signing parameters s_f, s_x, s_a, s_b, s_d, respectively equal to r_f+c.f, r_x+c.x, r_a+c.a, r_b+c.a.x and r_d+c.a.f, generating said pseudonym signature of said message from said signing parameters, and at least one control server comprising at least storage means, processing means and interface means wherein said at least one control server is configured to implement a control method according to claim 11.

Description

DESCRIPTION OF FIGURES

(1) Other characteristics and advantages will further emerge from the following description which is purely illustrative and nonlimiting and must be considered with respect to the appended figures, in which:

(2) FIG. 1 illustrates advanced security mechanisms for MRTD.

(3) FIG. 2 is a schematic representation of an example of system for implementing the methods according to the invention.

(4) FIGS. 3a and 3b form a flowchart representing the steps of a signing method according to an embodiment of the invention.

(5) FIG. 4 is a flowchart representing the steps of a registration phase of a new user according to an embodiment of the invention.

(6) FIG. 5 is a flowchart representing the steps of a signature control method according to an embodiment of the invention.

DETAILED DESCRIPTION OF AT LEAST ONE EMBODIMENT

(7) System

(8) A system such as illustrated in FIG. 2 comprises a set of user devices DU each held by a user, reading terminals T, a key-managing authority AG, service providers FS and verifiers V which can be service providers.

(9) The set of user devices, the reading terminals, the key-managing authority, the service providers and the verifiers are interconnected by means of a computer network. A set of terminals of this network in communication with a service provider constitutes a domain.

(10) The key-managing authority, the service providers and the verifiers can be connected to this network by respective servers comprising a RAM and storage means such as rewritable non-volatile memory (flash memory or EEPROM memory) which can store a database, processing means comprising a processor, cryptographic units for generating especially random numbers, etc. . . . and interface means allowing them to communicate with other entities on the network and be connected to databases. Such servers can also comprise input and user interface means for their administration. The servers of the above entities are respectively named key management server SAG, service provider server SFS, and control server SC in the following.

(11) At least two of these servers can be gathered within a same computer device jointly ensuring the functions of said servers.

(12) The user device of a user can be included in a portable electronic device capable of secure storing data readable by a reading terminal.

(13) An electronic device can be an identity document comprising a chip on which are stored secure data for example a travel document readable by machine (Machine Readable Travel Document, MRTD) such as a passport or an identity card, a flash memory storage device provided with a USB communication interface, called USB key (Universal Serial Bus), a chip card etc. . . . .

(14) The user device can comprise a RAM and storage means such as rewritable non-volatile memory (flash memory or EEPROM memory), processing means comprising a processor, cryptographic units for generating especially random numbers etc. . . . . The user device can also comprise interface means such as a communication interface without contact of the type RFID or NFC interface, or else a wireless communication interface of the type Bluetooth or Wifi interface.

(15) The stored secure data can be biometric data. In this case, the portable device or the user device can be provided with sensors allowing capturing the biometric data of a user, such as his fingerprints, palm prints or retinal prints.

(16) A user device and a reading terminal can communicate by means of wireless or contactless communications such as those mentioned hereinabove. They can also communicate by means of a USB interface, Firewire or any other wired communication interface. They can also communicate by means of an interface with chip card contact of ISO 7816 type.

(17) A reading terminal can also comprise a wired or wireless communication interface, adapted for connection of the terminal to the computer network, such as an Ethernet, Wifi or 3G interface; and a user interface allowing the user to control its operation.

(18) According to a variant, a user device and a reading terminal can be gathered in the same electronic device comprising communication interface and user interface means similar to those described hereinabove.

(19) In the following description, operations for calculating the signature can be delegated to a remote processing device which can be the reading terminal or any other remote device connected to the user device and comprising processing means with sufficient calculation power to carry out these operations.

(20) The network connecting the user devices and the servers by way of example consists of a local Ethernet network, a local wireless network, the Internet network, a mobile telephony network . . . . The communications on this network can be secure, especially by encrypting exchanged data.

(21) The steps of the signing method implemented by a user device DU of those described in the following paragraphs are represented in the flowcharts of FIGS. 3a and 3b.

(22) Generation of Keys

(23) The signing method can comprise a key generation phase implemented by the key management server SAG.

(24) In this key generation phase, the processing means of the management server generate a set of public parameters gpk and a modular integer constituting a secret management key . Said management key can by way of example belong to Z.sub.p, the body of the modulo relative integers p, with p being a prime number.

(25) The management server can also determine a domain parameter dpk, or dpk.sub.j specific to the domain D.sub.j of a service provider SFS.sub.j when the key managing authority plays the role of managing authority for at least two service provider domains, a service provider domain comprising a set of terminals in communication with a server of said service provider. The management server then sends the domain parameter via its interface means to the server of the service provider SFS or to the service provider SFS.sub.j belonging to the domain D.sub.j. As a variant, the service providers SFS.sub.j can generate these domain parameters themselves.

(26) The public parameters gpk are then made public. The domain parameter dpk.sub.j can also be made public.

(27) More precisely, in an embodiment of the invention, during this key generation phase the processing means of the key management server: determine groups G.sub.1, G.sub.2, G.sub.T which can by way of example be bilinear of prime-order p and a bilinear application of G.sub.1G.sub.2 in G.sub.T which can be a bilinear and nondegenerated form of G.sub.1G.sub.2 in G.sub.T, randomly generate first and second elements of the group G.sub.1 g.sub.1 and h, for example generators of the group G.sub.1, and an element g.sub.2 of the group G.sub.2, g.sub.2 which can be for example a generator of the group G.sub.2, randomly generate a modular integer constituting the secret management key, wherein can belong to Z.sub.p, and can calculate a parameter w which can be equal to g.sub.2.sup., determine a cryptographic hash function H

(28) From these elements, the key management server can generate the set of public parameters gpk=(p, G.sub.1, G.sub.2, G.sub.T, e, h, g.sub.2, w, H).

(29) The key management server can also previously calculate a second coupling result V equal to e(h, g.sub.2) and a third coupling result W equal to e(h,w). These second and third coupling results can be included in the set of public parameters gpk.

(30) The secret management key does not form part of the public parameters gpk, and is held by the managing authority only. The difficulty in executing the algorithm of the discrete logarithm for a selected group G.sub.2 ensures the practical impossibility of recovering the secret management key from w. In this way diffusion of w in the set of public parameters gpk poses no security problem of the signature mechanism.

(31) For each service provider FS (or FS.sub.j specific to the domain D.sub.j if there are several domains), the key management server generates a domain parameter dpk (or dpk.sub.j). This parameter can be a function of a modular integer r (or r.sub.j) which can belong to Z*.sub.p. By way of example this parameter can be equal to g.sub.1.sup.r (or g.sub.1.sup.r.sup.j). The integer r (or r.sub.j) can be randomly generated by the management server by means of its cryptographic unit. The management server then transmits this parameter via its interface means to the server of the service provider FS (or FS.sub.j).

(32) The public parameters gpk and if needed the domain parameter dpk or dpk.sub.j can be made public in various ways. They can be sent by the service providers FS to the control servers SC and to the user devices D.U or published on a service provider site, said user devices receiving them during a reception step 100.

(33) Registration of a New User

(34) The signing method can also comprise a phase called registration of a new user Ui with the key-managing authority AG, consisting of creating a secret signature key sk for the user Ui, illustrated in FIG. 4.

(35) To do this, the new user Ui can generate, by means of the processing means of its user device DU at least one first element of a first unknown key part of the key-managing authority AG during a generation step 200, transmit an identity datum during a transmission step 201 by the interface means of its user device, calculated by these processing means from at least this first element of this first key part, to the key management server SAG and prove to the key-managing authority by means of this identity datum that it holds at least said first element of the first key part by zero knowledge proof algorithm. The key management server then generates and then transmits to the new user the missing key part forming with the first key part the signature key of the new user, which receives this missing key part during a reception step 202.

(36) More precisely, in a first embodiment of the invention during this registration phase: The processing means of the user device of the new user determine a modular integer f constituting a first element f of the first key part f, such a first element f can by way of example belong to Z.sub.p, calculate identity data F equal to h.sup.f, calculate zero knowledge proof of the first element f of the first key part f, and transmit F and to the key management server. The processing means of the key management server verify . If this verification is positive, the new user has in fact brought to the managing authority the proof that it holds the first element f of the first key part f without divulging it. The processing means of the key management server then randomly generate a modular integer constituting a second key part x and a modular integer constituting a second element f of the first key part f then calculate a number F equal to F h.sup.f and a third key part A equal to (g.sub.1F).sup.1/(x+). The interface means of the management server can transmit to the user device the second element f, the second and third key part x and A by using a preferably secure channel. The processing means of the user device calculate the first key part f from the first and second elements of first key part; this first key part can for example be equal to f+f. Optionally, the processing means of the user device verify that e(A, g.sub.2.sup.xw)=e(g.sub.1 h.sup.f, g.sub.2).

(37) The last optional verification allows the member to verify that the second and third key parts A and x as well as the second element f of the first key part f which have been sent to the latter have not been corrupted and are valid, that is, verify the equation A=(g.sub.1F).sup.1/(x+).

(38) The proof calculated by the processing means of the user device can be a noninteractive zero knowledge proof of equality of discrete logarithm. This proof can especially implement a double commitment to prove the knowledge of the first element f of the first key part f. The proof then comprises, in addition to a first encrypted proof value, an additional commitment value C calculated from the first element f of the first key part f by an extractable commitment scheme, such as a commitment scheme perfectly binding and computationally masking having an extraction key for extracting the commitment value.

(39) Such an embodiment allows jointly generating the first key part f by the key management server and by the user device to reinforce the security of this registration phase.

(40) In a second embodiment of the invention, methods similar to those described hereinabove are implemented during this registration phase but the first key part f is entirely determined by the processing means of the user device. The zero knowledge proof transmitted by the user device to the key management server serves to prove the knowledge of all of the first key part f. The interface means of the management transmit send to the user device only the second x and third A key parts. This allows limiting the quantity of information to be exchanged between the key management server and the user device and avoiding making some calculations on both these items of equipment.

(41) In such embodiments of the invention, the new user is the only one to know the entirety of his signature key constituted by first, second and third key parts. Nobody, not even the key-managing authority can accordingly sign a message in place of the new user.

(42) By way of option, during execution of this registration phase, the managing authority sends a first coupling result Z equal to e(A, g.sub.2) to the new user who receives it during a reception step 203 to prevent the user device of the latter having to later take charge of calculating a coupling result during calculation of the signature.

(43) The signature key of the new user and the first coupling result Z can be stored in secure storage means of the user device belonging to the new user, for example in the non-volatile memory of the corresponding portable electronic device.

(44) Similarly, the second and third key parts can be stored by the key management server, for example within a database registered in the storage means of the key management server or else connected to the latter.

(45) According to a variant of the invention, the first key part f or the first element f of the first key part is calculated from a biometric datum of the new user captured by the sensors of the portable electronic device or of the user device or else stored by one of the latter. The first key part f or the first element f of the first key part can also be the result of application by the processing means of the portable electronic device of a hash function with such a biometric datum.

(46) Generation of Pseudonym

(47) The signing method can also comprise a generation step 101 of a pseudonym identifying the user of the user device DU.

(48) This pseudonym is a function of the domain parameter dpk and of the second key part and can be equal to h.sup.fdpk.sup.x.

(49) In the case of multiple domains, with the pseudonym of the user in the domain D.sub.j being formed from the domain parameter dpk.sub.j specific to the domain Dj, the user has different pseudonyms in separate domains. It is then impossible for service providers FS or verifiers V to determine whether two messages in two separate domains having different signatures and pseudonyms have been signed by the same member (cross-domain unlinkability).

(50) Generation of Signature

(51) The signing method comprises a signing phase of a message m. This signing phase can be done for example within the scope of RI protocol (Restricted Identification).

(52) The message m can be a challenge previously transmitted by a control server SC to the user device or any type of message to be signed by the user of the user device DU. The control server can also transmit to the user device the domain parameter dpk (or dpkj), if the latter has been made public or is not already known to said user.

(53) In a first embodiment of the signing phase, the processing means of the user device conduct the following steps: determining 102 first, second, third, fourth, fifth and sixth modular random integers a, r_a, r_f, r_x, r_b, r_d which can belong to Z.sub.p, calculating 103 a first signing coefficient R.sub.1 equal to h.sup.r.sup._.sup.fdpk.sup.r.sup._.sup.x, calculating 104 a second signing coefficient R.sub.2 equal to nym.sup.r.sup._.sup.ah.sup.r.sup._.sup.ddpk.sup.r.sup._.sup.b, obtaining 105 a third signing coefficient R.sub.3 equal to Z.sup.r.sup._.sup.x V.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b W.sup.r.sup._.sup.a, obtaining 106 a first signing parameter T equal to Ah.sup.a, calculating 107 a second signing parameter c by applying a cryptographic hash function H, to the public domain parameter dpk, the pseudonym nym, the first signing parameter T, the first, second and third signing coefficients R.sub.1, R.sub.2, R.sub.3 and the message m; said second signing parameter can for example be equal to H(dpknymTR.sub.1R.sub.2R.sub.3m) with the concatenation operation, calculating 108 third, fourth, fifth, sixth and seventh signing parameters s_f, s_x, s_a, s_b, s_d, respectively equal to r_f+c.f, r_x+c.x, r_a+c.a, r_b+c.a.x and r_d+c.a.f, generating 109 said pseudonym signature of said message m from said signing parameters (T, c, s_f, s_x, s_a, s_b, s_d).

(54) The signature is constructed such that the user of the user device can prove by signing a message or challenge that he has knowledge of the secret signature key sk without divulging it, for example by a zero knowledge proof algorithm.

(55) Also, by construction, the modular integer x, which constitutes a second part of a secret signature key is used both for calculating the signature of the message m and for generating the pseudonym nym used by the user of the user device. This allows linking them and thus being able to prove from the signature and the pseudonym that the user knows the second key part x without revealing the latter and that the user identified by the pseudonym constructed from this second key part x is in fact the legitimate signatory of the message m.

(56) In a variant of this first embodiment, the first coupling result Z can be calculated prior to the step of obtaining the third signing coefficient R.sub.3.

(57) The first coupling result Z can thus be calculated by the processing unit of the management server of the key-managing authority prior to implementing the signing phase, for example during the registration phase before being transmitted to the user device which receives it during a reception step 203. This allows alleviating for the user device and accelerating the calculation of the coupling result, the management server benefiting from more calculation power than the user device.

(58) In the same way the second and third coupling results V and W can be calculated prior to the step of obtaining the third signing coefficient R.sub.3.

(59) The second and third coupling results V and W can for example be public parameters generated by the managing authority and belong to the set of generated public parameters gpk.

(60) Thus in this variant, the user device performs all the calculations for generating the signature in the groups G1 and GT but carries out no operations in the group G2 and does not calculate couplings which are the costliest operations in terms of calculation power and are very rarely embedded on chip cards. So in the case of a chip for example embedded in an MRTD identity document readable by a reading terminal, the chip carries out only the less expensive operations in terms of calculation power and the reading terminal is content to transfer messages between the chip and the service provider.

(61) The step of obtaining the first signing parameter T can comprise a calculation step of the first signing parameter T 106.sub.1 implemented by the processing means of the user device.

(62) Alternatively, the step of obtaining the first signing parameter T can comprise a transmission step 106.sub.2 via the interface means of the user device of the first determined random integer a to a remote processing device which can be a reading and reception terminal via the interface means of the user device of the first signing parameter T calculated by the remote processing device and equal to Ah.sup.a. This allows using the calculation power of the remote processing device and levitating the calculations performed in the user device.

(63) In a first embodiment, the step of obtaining the third signing coefficient R.sub.3 can comprise a calculation step of the third signing coefficient R.sub.3 105.sub.1 performed by the processing means of the user device by means of the first, second and third coupling results Z, V, W obtained according to the different variants presented hereinabove.

(64) In a second embodiment, the step of obtaining the third signing coefficient R.sub.3 can comprise a step 105.sub.2: of calculating by the processing means of the user device of a fourth signing coefficient B.sub.1 equal to A.sup.r.sup._.sup.xh.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b and a fifth signing coefficient B.sub.2 equal to h.sup.r.sup._.sup.a, of transmitting via the interface means of the user device of said fourth and fifth signing coefficients B.sub.1 and B.sub.2 to a remote processing device which can be a reading terminal, of receiving by the interface means of the user device of the third signing coefficient R.sub.3, said third signing coefficient R3 being calculated by the remote processing device and equal to e(B1, g.sub.2)e(B2,w).

(65) In a third embodiment, the step of obtaining the third signing coefficient R.sub.3 can comprise a step 105.sub.3: of calculating by the processing means of the user device of a sixth signing coefficient B equal to A.sup.r.sup._.sup.xh.sup.a.r.sup._.sup.xr.sup._.sup.fr.sup._.sup.b, of transmitting via the interface means of the user device of the sixth signing coefficient B and of the second determined random integer r_a to a remote processing device, of receiving by the interface means of the user device of the third signing coefficient R.sub.3,
said third signing coefficient R.sub.3 being calculated by said remote processing device and equal to e(B, g.sub.2)W.sup.r.sup._.sup.a.

(66) According to these second and third embodiments, the user device performs operations in a single group only and exponentiations only. Moreover, the costliest calculations are performed by the remote processing device, the latter having calculation power greater than the user device without the user device revealing the secret key of the user so as to be protected from a malicious reading terminal.

(67) On completion of this signing phase, the user device DU transmits via its communication interface means, and optionally through the reading terminal T, the signature obtained and the pseudonym corresponding to the user of the user device to the control server SC which has sent it the challenge to be signed, or else to the recipient of the message m to which it also sends the message m.

(68) For a high level of security equivalent to the level offered by a key RSA of 3072 bits, the signature and the pseudonym obtained together weigh 2 Kbits. In the embodiments delegating the calculation of some elements of the signature to a remote processing device, the user device sends a few tens of bits of data to the remote processing device which then sends back around 3 Kbits of data.

(69) Control of Signing

(70) To control the signing a of a message m and of a pseudonym nym generated according to the signing method described hereinabove, processing means of a control server SC can execute a signature control method which comprises the following steps, illustrated in FIG. 5: a calculation step 301 of a first control coefficient R.sub.1, with R.sub.1 equal to h.sup.s.sup._.sup.fdpk.sup.s.sup._.sup.xnym.sup.c, a calculation step 302 of a second control coefficient R.sub.2, with R.sub.2 equal to nym.sup.s.sup._.sup.ah.sup.s.sup._.sup.ddpk.sup.s.sup._.sup.b, a calculation step 303 of a third control coefficient R.sub.3, with R.sub.3 equal to e(T,g.sub.2).sup.s.sup._.sup.x V.sup.s.sup._.sup.fs.sup._.sup.b W.sup.s.sup._.sup.a[e(g.sub.1,g.sub.2)e(T,w).sup.1].sup.c, a calculation step 304 of a control parameter c by applying the hash function H to the public domain parameter dpk, the pseudonym nym, the first signing parameter T, the first, second and third control coefficients R.sub.1, R.sub.2, R.sub.3 and to the message m; c can for example be equal to H(dpknymTR.sub.1R.sub.2R.sub.3m), a comparison step 305 of the second signing parameter c and of the control parameter c, said signature being valid in case of equality of the second signing parameter c and of the control parameter c.

(71) This signature control method controls, from the signature and the pseudonym nym, that the user has knowledge of the secret signature key sk, and that the pseudonym and the signature of the user are linked, that is, that said pseudonym and said signature are a function of a part of said secret signature key. If this verification is positive, the pseudonym received with the signature is that of the signatory.

(72) To verify the signature of a message m and the pseudonym of the user holding the user device, the control server needs only to know this signature and this pseudonym as well as the domain parameters dpk and the public parameters gpk. The control server especially has no knowledge of the secret signature key of the user. For this reason no control server can sign a message in place of the user, or know the pseudonym of the user in several domains and link the signatures and pseudonyms of this user for different domains. For this reason it is impossible to say whether or not they correspond to the same user when two pseudonyms for two different domains are observed.

(73) Revocation

(74) Users who can log on or exit the system at different instants or else users who can lose their capacity to sign, a revocation mechanism can be put in place so that logged-on users can be revoked later, either in the whole system, that is, in all domains, or in a sub-set of domains.

(75) A revocation list can be set up for each domain and updated by the managing authority AG.

(76) Such a revocation list RL.sub.j for the domain Dj is built from pseudonyms nym.sub.j of revoked users and is stored in a revocation database BD.sub.j.

(77) To do this, when a domain is created such an initially empty revocation list can be created for this domain. This list can be created as the same time as the domain parameter dpkj.

(78) During the registration phase, the managing authority can store in a revocation table a revocation token rt associated with the new logged-in user as a function of the second key part x and of the number F calculated, for example equal to the couple (F, x).

(79) According to a first embodiment, when the managing authority wants to revoke a user in a domain D.sub.j, the management server SAG retrieves the revocation token rt stored in the revocation table and transmits it to the server SFS.sub.j of the service provider FS.sub.j. The server of the service provider SFS.sub.j calculates the corresponding pseudonym nym.sub.j, equal to F(dpk.sub.j).sup.x, and adds it to the revocation list RL.sub.j of the revocation database BD.sub.j.

(80) According to a second embodiment, when the managing authority AG wants to revoke a user in a set of domain Dj, the management server SAG retrieves the revocation token rt associated with the user stored in the revocation table and the domain parameter dpk.sub.j, generates auxiliary information corresponding to the pseudonym nym.sub.j of the user equal to F(dpk.sub.j).sup.x and transmits it to each server SFS.sub.j of the service provider FS.sub.j. Each server of the service provider FS.sub.j adds the pseudonym nym.sub.j to the revocation list RL.sub.j of the revocation database BD.sub.j.

(81) This allows avoiding transmitting part of the secret key of the user to the network.

(82) According to a third embodiment, revocation of a user can be at the initiative of a service provider FS.sub.j. A server SFS.sub.j of the service provider FS.sub.j adds the pseudonym of the user it wants to revoke to the revocation list RL.sub.j of the revocation database BD.sub.j.

(83) The control method can also comprise a revocation verification step 300 consisting of verifying that the user has not been revoked in the set of domains or in a sub-set of domains.

(84) To do this, the processing means of the control server SC verify in the revocation database BD.sub.j that the pseudonym nym.sub.j of the signatory does not belong to the revocation list RL.sub.j.

(85) In an embodiment if the control server determines that the user has been revoked, it does not implement the steps of the control method described hereinabove and therefore does not verify the validity of the signature.

(86) On the other hand, the revocation list is not taken into account during signing. This allows not having to renew the keys of valid users after revocation of a user and involving no additional calculations for the signatory.

(87) Moreover, during the verification step of the revocation of a user, the processing means of the control server have only one test for belonging to a list to be performed and not a linear number of arithmetical operations as in the signature mechanisms of known groups.

(88) According to a variant of the invention, lists of valid users are used instead of revocation lists. During the revocation verification step 300, the control server then verify that the pseudonym of the user belongs to the list of valid members.

(89) The storage databases of these lists can be stored on the service provider servers. According to a variant, these lists can be stored in a common database stored on the key management server.

(90) Thus such a pseudonym signing methods allowing a user to authenticate to a service provider while having a level of security at least as high as that of the signature methods of the prior art can be implemented on chip cards having low calculation power and especially on existing chip cards.