Method for deriving a partial signature with partial verification

Abstract

A method for deriving a partial signature for a subset of a set of messages. The method includes: receiving the set of messages and a signature of the set, which includes signature elements of the set; generating anonymized elements of the signature; generating a first verification element from messages other than those of the subset; generating a second verification element to prove the first verification element is well formed; and sending, to a verification entity, a partial signature specific to the subset. The partial signature includes a constant number of elements having at least the elements of the signature of the set of anonymized messages, the first verification element and the second verification element. The partial signature is verifiable with only the messages of the subset of messages. The second verification element is a function of derived values calculated from at least the other elements of the partial signature.

Claims

1. A method for deriving a partial signature for a subset of a set of messages, called subset of messages, said partial signature proving validity of a signature of the set of messages for the messages of the subset of messages, said method, implemented by an entity for deriving a partial signature, comprising: receiving the set of messages and a signature of said set of messages, said signature comprising signature elements of the set of messages, generating anonymized elements of the signature, generating a first verification element calculated from the messages of the set other than those of the subset of messages, and generating a second verification element to prove that the first verification element is well formed, and sending, to a verification entity, of a partial signature specific to the subset of messages, said partial signature comprising a constant number of elements comprising at least the elements of the signature of the set of anonymized messages, the first verification element and the second verification element, said partial signature being verifiable with the only messages of the subset of messages, wherein the second verification element is a function of derived values calculated from at least the other elements of the partial signature.

2. The method for deriving a partial signature according to claim 1, wherein, let I be a subset of a set {1, . . . , n}, n designating a maximum number of messages that can be signed at a time, the set of messages being denoted {m_1, . . . , m_n}, let m_i be the messages of the subset of messages, i belonging to I, the calculation of the derived values, denoted c_i, of the second verification element comprises: for any i of I, application of a function H taking as input any string of characters and returning a non-zero scalar, said function H being applied to the elements of the signature of the set of anonymized messages, to the first verification element, to the subset I and to i in order to calculate the derived values c_i.

3. The method for deriving a partial signature according to claim 2 wherein the function H taking as input any string of characters and returning a non-zero scalar is a one-way function.

4. The method for deriving a partial signature according to claim 1 comprising beforehand generating a secret key and an associated public key in a bilinear environment, said environment designating a first group G1, a second group G2 and a third group GT of order p, as well as a bilinear map, taking as input an element of the first group G1, an element of the second group G2 and with values in the third group GT, let g, respectively h, be an element of the first group G1, respectively of the second group G2, said generating comprising: generating, by the signatory entity, 2 random scalars a and b, said random scalars forming the secret key of the signatory entity, and calculating by the signatory entity of:
G_i=g{circumflex over ( )}{b{circumflex over ( )}i}, for any 1≤i≤n and n+2≤i≤2n,
A=h{circumflex over ( )}a, and
B_i=h{circumflex over ( )}{b{circumflex over ( )}i}, for any 1≤i≤n, wherein the public key is formed of g, h, G_i, A, and B_i and of the function of calculating the derived values.

5. The method for deriving a partial signature according to claim 4, wherein the signature of the set {1, . . . , n} of messages {m_1, . . . , m_n}, comprises selecting by the signatory entity of a random element s_1 of the first group G1, and calculating: s_2=s_1 {a+b*m_1+B{circumflex over ( )}2*m_2+ . . . +b{circumflex over ( )}n*m_n}, said signature comprising the signature elements s_1, s_2, and being denoted (s_1, s_2).

6. The method for deriving a partial signature according to claim 1, wherein the derivation of the partial signature for the subset I of the set {1, . . . , n} of messages comprises: calculation of the anonymized elements ((s′_1, s′_2)) of the signature, said calculation comprising: generation of a first random scalar t and of a second non-zero scalar r, anonymization of the first signature element and calculation of s′_1=s_1{circumflex over ( )}r, anonymization of the second signature element and calculation of s′_2=s_2{circumflex over ( )}r*s′_1{circumflex over ( )}t, generation of the first verification element s′_3=Π_{j in {1, . . . , n}\I} B_j{circumflex over ( )}{m_j}*h{circumflex over ( )}t, and generation of the second verification element s′_4=Π_{i in I}(G_{n+1−i}{circumflex over ( )}t*Π_{j in {1, . . . , n}\I} G_{n+1−i+j}m_j){circumflex over ( )}c_i, the partial signature then being (s′_1, s′_2, s′_3, s′_4).

7. A method for verifying a partial signature for a subset of a set of messages, called subset of messages, said partial signature being intended to prove validity of a signature of the set of messages for the messages of the subset of messages, said method, implemented by an entity for verifying a partial signature, comprising: receiving the subset of messages and a partial signature specific to the subset of messages, said partial signature comprising a constant number of elements comprising at least the anonymized elements of the signature of the set of messages, a first verification element calculated from the messages of the set other than those of the subset of messages and a second verification element to prove that the first verification element is well formed, the second verification element being a function of derived values from at least the other elements of the partial signature, calculating the derived values by using a function for calculating derived values, and verifying a first equation and of a second equation, said first equation comprising the messages of the subset of messages, the elements of the signature of the set of messages, the first verification element and elements of the public key, the second equation comprising the first signature verification element, the second signature verification element, elements of the public key and the derived values.

8. The method for verifying a partial signature according to claim 7, wherein a secret key and a public key have been previously generated in a bilinear environment for a signatory entity, said environment designating a first group G1, a second group G2 and a third group GT of order p, as well as a bilinear map e, taking as input an element of the first group G1, an element of the second group G2 and with values in the third group GT, let g, respectively h, be an element of the first group G1, respectively of the second group G2, said generation of the secret key and of the public key comprising: generating, by the signatory entity, of 2 random scalars a and b, said random scalars forming the secret key of the signatory entity, and n designating the maximum number of messages that can be signed at a time, calculating by the signatory entity:
G_i=g{circumflex over ( )}{b{circumflex over ( )}i}, for any 1≤i≤n and n+2≤i≤2n,
A=h{circumflex over ( )}a, and
B_i=h{circumflex over ( )}{b{circumflex over ( )}i}, for any 1≤i≤n, g, h, G_i, A, and B_i and the function of calculating derived values, denoted H, forming the public key, the verification of the partial signature, denoted (s′_1, s′_2, s′_3, s′_4), received by the verification entity comprising for a subset I of a set {1, . . . , n}, the set of messages being denoted {m_1, . . . , m_n}, let m_i be the messages of the subset of messages: calculating the derived values:
c_i=H(s′_1∥s′_2∥s′_3∥I∥i), for any subscript i in I, verifying the first equation:
e(s′_1,A*(Π_{i in I}B_i{circumflex over ( )}{m_i})*s′_3)=e(s′_2,h), and of the second equation:
e(Π_{i in I}G_{n+1−i}{circumflex over ( )}{c_i},s′_3)=e(s′_4,h).

9. An A partial signature derivation entity for deriving a partial signature to derive a partial signature for a subset of a set of messages called subset of messages, said partial signature being intended to prove validity of a signature of the set of messages for the messages of the subset of messages, said partial signature derivation entity, comprising: a processor; and a non-transitory computer readable medium comprising instructions stored thereon which when executed by the processor configure the partial signature derivation entity to: receive the set of messages and a signature of said set of messages, said signature comprising signature elements of the set of messages, generate anonymized elements of the signature, generate a first verification element calculated from the messages of the set other than those of the subset of messages, generate a second verification element intended to prove that the first verification element is well formed, and send to a verification entity a partial signature specific to the subset of messages, said partial signature comprising a constant number of elements comprising at least the elements of the signature of the set of anonymized messages, the first verification element and the second verification element, said partial signature being intended to be verified with the only messages from the subset of messages, wherein the second verification element is a function of derived values calculated from at least the other elements of the partial signature.

10. A partial signature verification entity for verifying a partial signature, intended to verify a partial signature for a subset of a set of messages, called subset of messages, said partial signature being intended to prove the validity of a signature of the set of messages for the messages of the subset of messages, said partial signature verification entity comprising: a processor; and a non-transitory computer readable medium comprising instructions stored thereon which when executed by the processor configure the partial signature derivation entity to: receive the subset of messages and a partial signature specific to the subset of messages, said partial signature comprising a constant number of elements comprising at least anonymized elements of the signature of the set of messages, a first verification element calculated from the messages other than those of the subset of messages and a second verification element intended to prove that the first verification element is well formed, the second verification element being a function of derived values from at least the other elements of the partial signature, calculate derived values by using a function of calculating derived values, and verify a first equation and a second equation, said first equation comprising the messages of the subset of messages, the elements of the signature of the set of messages, the first verification element and elements of the public key, the second equation comprising the first signature verification element, the second signature verification element, elements of the public key and the derived values.

11. (canceled)

12. The method according to claim 1, comprising implementing the method in an anonymous credential system.

13. (canceled)

14. (canceled)

15. (canceled)

16. (canceled)

17. The method according to claim 7, comprising implementing the method in an anonymous credential system.

Description

BRIEF DESCRIPTION OF THE FIGURES

[0062] Other characteristics and advantages of the present invention will be better understood from the detailed description and the appended figures, among which:

[0063] FIG. 1 presents the steps of a method for deriving a partial signature and verifying the partial signature for a subset of a set of messages, according to one exemplary embodiment;

[0064] FIG. 2 is a schematic representation of an entity for deriving a partial signature able to implement the steps of the partial signature derivation method for a subset of messages, according to one exemplary embodiment;

[0065] FIG. 3 is a schematic representation of an entity for verifying a partial signature able to implement the steps of the partial signature verification method for a subset of messages, according to one exemplary embodiment.

DETAILED DESCRIPTION

[0066] The steps of a partial signature derivation and associated verification method for a subset of a set of messages, called subset of messages, according to one exemplary embodiment, will now be described in relation to FIG. 1.

[0067] It is noted that a usual notation in cryptography is used here in which:

[0068] “x_i” represents “x subscript i”, namely “x.sub.i”;

[0069] “g{circumflex over ( )}x” represents “g power x”, namely “g.sup.x”,

[0070] the product is schematized by an asterisk: “*”, or by the classic sign H (capital pi) when many indexed factors are involved. A notation where the asterisk is absent is also possible: “2n” for “2*n”,

[0071] the addition is classically schematized by the sign “+”, or by the sign Σ (capital sigma) when many indexed factors are involved.

[0072] The signature scheme described here operates in a bilinear environment which designates three groups, usually denoted G1, G2 and GT, of order p, as well as a bilinear map e called “bilinear coupling” taking as input an element of the group G1 and an element of the group G2 and with values in the group GT. This type of environment has become classic in cryptography and can be implemented very efficiently. It should be noted that the roles of G1 and G2 are perfectly interchangeable. Moreover, the term “scalar” here designates any integer comprised between 0 and p−1, p being the order of the groups mentioned above.

[0073] The signature scheme is based on a system that comprises several entities:

[0074] a signatory entity 10. The signatory entity 10 is a computing device which comprises code instructions to implement those of the steps of the partial signature derivation method implemented by the signatory entity 10,

[0075] an entity 11 for deriving a partial signature. The partial signature derivation entity 11 is a computing device which comprises code instructions for implementing those of the steps of the partial signature derivation method implemented by the partial signature derivation entity 11,

[0076] an entity 12 for verifying a partial signature. The partial signature verification entity 12 is a computing device which comprises code instructions to implement those of the steps of the partial signature derivation method implemented by the partial signature verification entity 12.

[0077] It is noted that the same entity can combine several roles. For example, a signatory entity can also act as a partial signature derivation entity. Similarly, a signatory entity can also be caused to act as a partial signature verification entity.

[0078] For the record, a bilinear coupling e is a function verifying among others the following properties:

e(g{circumflex over ( )}a,h{circumflex over ( )}b)=e(g,h){circumflex over ( )}(a.b)

e(g{circumflex over ( )}a,q)=e(g,g){circumflex over ( )}a=e(g,q{circumflex over ( )}a)

[0079] In the following, n designates the maximum number of data that can be signed at a time. Thereafter, a classic notation in cryptography is used and it is referred to as “messages” rather than “data”. Thus, a set {1, . . . , n} of messages to be signed, denoted {m_1, . . . , m_n} is provided. For example, for an individual, such messages may be their name, address, date of birth, etc.

[0080] In a prior key generation step E10, the signatory entity 10 generates for the signature scheme, a pair of secret/public keys Ks/Kp. It should be noted that in another exemplary embodiment, the generation of keys can be implemented by a dedicated key generation entity, distinct from the signatory entity 10, the keys, and in particular the secret key then being transmitted to the signatory entity 10 in a secure manner, according to the known methods not presented here.

[0081] Let g, respectively h, be a random element of the group G1, respectively of the group G2, the signatory entity 10 controls the generation of two scalars a and b and calculates the following elements:

G_i=g{circumflex over ( )}{b{circumflex over ( )}i}, for 1≤i≤n and n+2≤i≤2n

A=h{circumflex over ( )}a

B_i=h{circumflex over ( )}{b{circumflex over ( )}i}, for 1≤i≤n

[0082] The public key Kp is formed of the elements g, h, A, B_i and G_i, for the subscripts mentioned above. The public key also defines a function, denoted H, intended to freeze the data to which it applies. More specifically, applying the function H to data produces a commitment on these data. The function H takes as input any string of characters and returns a non-zero scalar. In one exemplary embodiment, the function H is a one-way function. For the record, a one-way function is a function that can be easily calculated but difficult to reverse. In another exemplary embodiment, the function H is a cryptographic hash function, such as SHA-256 (Secure Hash Algorithm).

[0083] The secret key Ks of the signatory in the signature system consists only of the scalars a, b.

[0084] Thus:

Ks=(a,b), and

Kp=(g,h,A,B_i,G_i,H)

[0085] Conventionally, the public key Kp is then published or transmitted, here by the signatory entity 10. It should be noted that the cost inherent in this publication or this transmission is considerably reduced, in particular compared to the solution described in PKC 2020: “Efficient Redactable Signature and Application to Anonymous Credentials”, Olivier Sanders, due to the size of the public key Kp. In this exemplary embodiment, the public key Kp is indeed made up of 2n elements of G1 and n+2 elements of G2, against (n{circumflex over ( )}2+n+2)/2 elements for the protocol described in PKC 2020. An estimate for reasonable values of n such as n=100, n=1,000, . . . , shows the practical importance of this improvement, in particular for the transmission and/or the storage of the public key. This is known as linear complexity, or “in n” for the present solution against a quadratic complexity, or in “n{circumflex over ( )}2” for the mechanism presented at PKC 2020.

[0086] The signature scheme described here thus allows very effectively verifying the validity of a signature on any subset of messages. This efficiency is based in particular on the public key whose number of elements is drastically reduced compared to the mechanism described at PKC 2020.

[0087] In a second signature step E11, the signatory entity 10 signs the n messages m_1, . . . , m_n by means of its secret key Ks. To this end, the signatory entity 10 selects a random element s_1 from the group G1 and generates a second element s_2 as follows:

s_2=s_1{circumflex over ( )}{a+b*m_1+b{circumflex over ( )}2*m_2+ . . . +b{circumflex over ( )}n*m_n}

[0088] The signature of the set of n messages is then (s_1, s_2).

[0089] It is noted that the signatory entity 10 can also sign messages of size n′, with n′<n with this same pair of keys, that is to say, without regenerating a pair of keys. In this case, the message of size n′ to be signed is completed with ‘0’s until obtaining a message of size n, and the signatory entity 10 then uses its pair of keys Ks/Kp to sign it. At the end of the signature step E11, the signatory entity 10 sends the signature (s_1, s_2) of the set of n messages to the partial signature derivation entity 11 as well as the set of n messages {m_1, . . . , m_n}.

[0090] The partial signature derivation entity 11 receives, in a substep E12-1 of receiving a step E12 of deriving a partial signature, the signature (s_1, s_2) of this set of n messages as well as the set of n messages {m_1, . . . , m_n}. The step E12 of deriving a partial signature allows deriving from the signature on the n messages received during the step E12-1, a signature subsequently called “partial signature” on any subset of the n messages. The set of subscripts of the messages of this subset is designated by I in the following.

[0091] The partial signature derivation entity 11 generates, in a sub-step E12-2 of generating the anonymized elements of the signature (the term “randomized” is used), a scalar t, potentially equal to 0, as well as a non-zero random scalar r. The scalars t and r are intended to anonymize the signature. The derivation entity 11 then calculates a first and a second anonymized element of the signature:

s′_1=s_1{circumflex over ( )}r

s′_2=s_2{circumflex over ( )}r*s′_1{circumflex over ( )}t

[0092] In a sub-step E12-3 of generating a first verification element, the entity 11 calculates a third element of the signature:

s′_3=Π_{j in {1, . . . ,n}\I}B_j{circumflex over ( )}{m_j}*h{circumflex over ( )}t

[0093] This third element of the signature s′_3 constitutes a first partial signature verification element.

[0094] It is observed that all the subscripts of the product forming this first verification element s′_3 are all the elements of {1, . . . , n} that are not in I.

[0095] In a next step E12-4 of generating a second signature verification element, the entity 11 calculates a fourth element of the signature s′_4. To this end, the entity 11 calculates derived values c_i as follows:

c_i=H(s′_1∥s′_2∥s′_3∥I∥i}, for all i in I. The symbol “∥” designates the concatenation of strings of characters. By definition of the function H, each of the elements c_i is a non-zero scalar. The values c_i, obtained by applying the function H, constitute derived values of the elements of the signature s′_1, s′_2 and s′_3. The derived values somehow freeze the elements of the signature. They are intended to avoid phenomena called “compensation” phenomena, where an adversary would cheat on some messages but would manage to compensate on other messages. These derived values are intended to counteract the simplicity of the public key that uses fewer scalars, thus leading to fewer elements in the public key.

[0096] The derivation entity 11 then calculates the fourth element of the partial signature s′_4:

s′_4=Π{i in I}(G_{n+1−i}{circumflex over ( )}t*Π_{j in {1, . . . ,n}\I}(G_{n+1−i+j}{circumflex over ( )}m_j)){circumflex over ( )}c_i

[0097] This fourth element of the signature s′_4 constitutes the second partial signature verification element.

[0098] The partial signature is then (s′_1, s′_2, s′_3, s′_4).

[0099] The partial signature is specific to the messages m_i, with i in I and is intended to be used to verify the validity of the signature of this subset of messages m_i based on the signature of the n messages (s_1, s_2), and with the only messages of the subset of messages.

[0100] It is observed that in all cases, the subscripts of the elements G of the second verification element of the signature s′_4 are different from n+1. All the elements necessary for the verification of the signatures are therefore present in the public key Kp.

[0101] It should be noted that in one exemplary embodiment where the value of the scalar t is set to 0, the signature system guarantees the authenticity of the signed messages but loses its properties of anonymity. This exemplary embodiment is therefore particularly indicated in a context where the property of anonymity is not desired.

[0102] In the exemplary embodiment described here, in step E12-4 of deriving a second verification element, the partial signature derivation entity 11 calculates, or derives, the second verification element s′_4. This second verification element s′_4 is intended to prove that the first verification element s′_3 is valid, that is to say well formed. Intuitively, the second verification element s′_4 allows showing that the first verification element s′_3, calculated from the concealed messages, is well formed, that is to say it cannot be used to cheat on the value of the messages m_i, for i in I, which are presented to the partial signature verification entity 12.

[0103] In a following sending sub-step E12-5, which constitutes the end of step E12 of generating a partial signature, the partial signature derivation entity 11 sends to the verification entity 12 the partial signature (s′_1, s′_2, s′_3, s′_4) and the subset of messages m_i, with i in I.

[0104] Thus, regardless of the number of messages of the subset of messages m_i, with i in I, regardless of the number of messages of the set of messages, the partial signature is of constant size and comprises few elements, in this case four. It is also noted that only the messages of the subset of messages {m_i}, with i in I, are transmitted. The verification entity 12 therefore does not need to know the set of messages {m_1, . . . , m_n} or of the messages that would be linked by construction to messages of the subset of messages, such as for example for the age, date of birth.

[0105] In a next receiving step E13, the partial signature verification entity 12 receives from the partial signature derivation entity 11 the subset of messages {m_i}, with i in I, and the generated partial signature (s′_1, s′_2, s′_3, s′_4).

[0106] The partial signature verification entity 12, in a prior step E14 of calculating the derived values, calculates:

c_i=H(s′_1∥s′_2∥s′_3∥I∥i), for any subscript i in I

[0107] In a next signature verification step E15, the partial signature verification entity 12 tests whether the following two equations are met:

e(s′_1,A*(Π_{i in I}B_i{circumflex over ( )}{m_i})*s′_3)=e(s′_2,h),  (1)

and

e(Π_{i in I}G_{n+1−i}{circumflex over ( )}{c_i},s′_3)=e(s′_4,h),  (2)

[0108] If both equations are met (branch “ok” in FIG. 1), then the signature is considered as valid. Otherwise (branch “nok” in FIG. 1), it is rejected.

[0109] A signature obtained during the signature step E11 then derived during step E12 of deriving a partial signature is necessarily valid with regard to the signature verification step E15. Indeed:

e(s′_1,A*(Π_{i in I}B_i{circumflex over ( )}{m_i})*s′_3)=e(s_1{circumflex over ( )}r,h{circumflex over ( )}a*Π_{i in I}h{circumflex over ( )}{b{circumflex over ( )}i*m_i}*Π_{j in {1, . . . n}\I}h{circumflex over ( )}{b{circumflex over ( )}j*m_j}*h{circumflex over ( )}t)=e(s_1{circumflex over ( )}r,h{circumflex over ( )}a*h{circumflex over ( )}t*Π{i in {1, . . . ,n}}h{circumflex over ( )}{b{circumflex over ( )}i*m_i})  (1)

[0110] And by noting that

[00001]$e\left(g^{\wedge }a,q\right)={e\left(g,q\right)}^{\wedge }a=e\left(g,q^{\wedge }a\right):$$\begin{array}{c}=e\left(\mathrm{s\_}{1}^{\wedge }\left\{r\left(t+a+b*\mathrm{m\_}1+b^{\wedge }2*\mathrm{m\_}2+.Math.+b^{\wedge }n*\mathrm{m\_n}\right)\right\},h\right)\\ =e\left(s^{\prime }\_1^{\wedge }t*\mathrm{s\_}{1}^{\wedge }\left\{r\left(a+b*\mathrm{m\_}1+b^{\wedge }2*\mathrm{m\_}2+.Math.+b^{\wedge }n*\mathrm{m\_n}\right)\right\},h\right)\\ =e\left(s^{\prime }\_2,h\right)\end{array}$

[0111] The first equation (1) is therefore verified.

[0112] Regarding the second equation:

[00002]$\begin{array}{cc}e({\Pi }_{-}\left\{i\mathrm{in}I\right\}{G}_{-}{\left\{n+1-i\right\}}^{\wedge }\left\{\mathrm{c\_i}\right\},s’\_3)=e\left({\Pi }_{-}\left\{i\mathrm{in}I\right\}{G}_{-}{\left\{n+1-i\right\}}^{\wedge }\left\{\mathrm{c\_i}\right\},{\Pi }_{-}\left\{j\mathrm{in}\left\{1,.Math.,n\right\}\setminus I\right\}{\mathrm{B\_j}}^{\wedge }\left\{\mathrm{m\_j}\right\}*h^{\wedge }t\right)=e({\left({\Pi }_{-}\left\{i\mathrm{in}I\right\}{G}_{-}{\left\{n+1-i\right\}}^{\wedge }\left\{\mathrm{c\_i}\right\}\right)}^{\wedge }t+\Sigma \left\{j\mathrm{in}\left\{1,.Math.,n\right\}\setminus I\right\}{b}^{\wedge }j*\mathrm{m\_j}\},h)=e\left({\Pi }_{-}\left\{i\mathrm{in}I\right\}{\left(G_{-}{\left\{n+1-i\right\}}^{\wedge }t*G_{-}{\left\{n+1-i\right\}}^{\wedge }\left\{\Sigma \left\{j\mathrm{in}\left\{1,.Math.,n\right\}\setminus I\right\}{b}^{\wedge }j*\mathrm{m\_j}\right\}\right)}^{\wedge }\mathrm{c\_i},h\right).& \left(2\right)\end{array}$

[0113] Il suffice to notice that (G_u){circumflex over ( )}{b{circumflex over ( )}v}=g{circumflex over ( )}{b{circumflex over ( )}{u+v} }=G_{u+v} for all integer u and v.

[0114] Thus, the previous coupling can be written:

e(Π_{i in I}(G_{n+1−i}{circumflex over ( )}t*Π_{j in {1, . . . ,n}\}G_{n+1−i+j}{circumflex over ( )}m_j}){circumflex over ( )}{c_i},h)=e(s′_4,h)

[0115] The second verification equation is therefore verified.

[0116] In one exemplary embodiment (not represented in FIG. 1) where the signature verification, implemented by the partial signature verification entity 12 during the prior step E14 of calculating the derived values and the signature verification step E15 would be implemented directly on non-partial signatures, that is to say on signatures obtained at the end of the signature step E11, the first and second verification values s′_3, s′_4 are then set to 1 and I={1, . . . , n}.

[0117] The partial signature derivation method and the associated verification method, are of interest for all use cases requiring authentication, whether anonymous or not. More specifically, they apply in cases where several data are certified but where it is common to need to verify the authenticity of only some of them.

[0118] In a first example of use, a database potentially containing millions of data is certified. When a person wishes to retrieve a data from this database, they only need to verify the authenticity of this data. With a classic signature system, they would have to retrieve the entire database to perform this verification. With the mechanism described in PKC 2020, the signature would be short and the verification efficient, but the public key would contain trillions of elements. With the partial signature derivation method and the associated verification method described here, the same advantages would be kept but with a much shorter public key. The transmission of the public key and its storage by this person are much more efficient, while maintaining undeniable security properties.

[0119] The methods for deriving and verifying a partial signature described above are particularly suitable for use in the anonymous attestations or credentials. An anonymous attestation allows proving a property or a right related to its holder, without revealing the identity of the latter. It protects the privacy of the holder of the anonymous credential by providing the anonymity and non-traceability property. It takes the form here of cryptographic data: the partial signature, which can be shown by its holder, here the partial signature derivation entity 11, to an organization, here the partial signature verification entity 12, to prove a property related to their identity.

[0120] A partial signature derivation entity, according to one exemplary embodiment, will now be described in relation to FIG. 2. The partial signature derivation entity 11 is a computing piece of equipment, such as a computer.

[0121] The partial signature derivation entity 11 comprises:

[0122] a processing unit or processor 110, or CPU (Central Processing Unit), intended to load instructions into memory, to execute them, to perform operations;

[0123] a set of memories, including a volatile memory 111, or RAM (Random Access Memory) used to execute code instructions, store variables, etc., and a storage memory 112 of the EEPROM (Electrically Erasable Programmable Read Only Memory) type. Particularly, the storage memory 112 is arranged to memorize a software module for deriving a partial signature which comprises code instructions for implementing the steps of the partial signature derivation method as described previously and which are implemented by the partial signature derivation entity 11. The storage memory 112 is also arranged to memorize in a secure area the secret key Ks of the signature scheme.

[0124] The partial signature derivation entity 11 also comprises:

[0125] a receiving module 113 adapted to receive the set of messages {m_1, . . . , m_n} and a signature of said set of messages, said signature comprising signature elements (s_1, s_2) of the set of messages. The receiving module 113 is arranged to implement the step E12-1 of the partial signature derivation method as described previously;

[0126] a first generation module 114, arranged to generate anonymized elements of the signature (s′_1, s′_2). The first generation module 114 is arranged to implement the step E12-2 of generating the anonymized elements of the signature of the partial signature derivation method as described previously;

[0127] a second generation module 115, arranged to generate a first verification element s′_3 calculated from the messages other than those of the subset of messages. The second generation module 114 is arranged to implement the step E12-3 of generating a first verification element of the partial signature derivation method as described previously;

[0128] a third generation module 116, arranged to generate a second verification element s′_4 intended to prove that the first verification element is well formed. The third generation module 116 is adapted to implement the step E12-4 of generating a second verification element of the partial signature derivation method as described previously; and

[0129] a sending module 117, arranged to send to a verification entity 12 a partial signature specific to the subset of messages. The partial signature comprises a constant number of elements: at least the elements of the signature of the set of anonymized messages (s′_1, s′_2), the first verification element s′_3 and the second verification element s′_4. The partial signature is intended to be verified with the only messages of the subset of messages. The second verification element s′_4 is a function of derived values calculated from at least the other elements of the signature. The sending module 117 is adapted to implement the sending sub-step E12-5 of the step E12 of deriving a partial signature of the partial signature derivation method as described previously.

[0130] The receiving module 113, the first generating module 114, the second generating module 115, the third generating module 116 and the sending module 117 are preferably software modules comprising software instructions for implementing those of the steps of the partial signature derivation method implemented by the partial signature derivation entity 11.

[0131] The invention therefore also concerns:

[0132] a computer program including instructions for the implementation of the steps of the partial signature derivation method as described above and implemented by the partial signature derivation entity when this program is executed by a processor of the partial signature derivation device,

[0133] a readable recording medium on which the computer program described above is recorded.

[0134] A partial signature verification entity, according to one exemplary embodiment, will now be described in relation to FIG. 3. The partial signature verification entity 12 is a computing piece of equipment, such as a computer.

[0135] The partial signature verification entity 12 comprises:

[0136] a processing unit or processor 120, or CPU, intended to load instructions into memory, to execute them, to perform operations;

[0137] a set of memories, including a volatile memory 121, or RAM used to execute code instructions, store variables, etc., and a storage memory 122 of the EEPROM type. Particularly, the storage memory 122 is arranged to memorize a software module for verifying a partial signature as generated by the partial signature derivation entity 11. The software module comprises code instructions for implementing the steps of the partial signature verification method as described above and which are implemented by the partial signature verification entity 12. The storage memory 122 is also arranged to memorize in a storage area the public key Kp of the signature scheme.

[0138] The partial signature verification entity 12 also comprises:

[0139] a receiving module 123, arranged to receive the subset of messages and a partial signature (s′_1, s′_2, s′_3, s′_4) specific to the subset of messages. Said partial signature comprises a constant number of elements: at least the anonymized elements of the signature of the set of messages (s′_1, s′_2), a first verification element s′_3 calculated from the messages of the set other than those of the subset of messages and a second verification element s′_4 intended to prove that the first verification element is well formed. The second verification element s′_4 is a function of derived values from at least the other elements of the partial signature. The first receiving module is adapted to implement the step E14 of receiving the partial signature derivation method as described previously;

[0140] a calculation module 124, arranged to calculate derived values by means of a function of calculating derived values. The calculation module 124 is adapted to implement the step E14 of calculating the derived values of the partial signature derivation method as described previously;

[0141] a verification module 125, arranged to verify a first equation and a second equation. The first equation comprises the messages of the subset of messages, the elements of the signature of the set of messages, the first verification element and elements of the public key. The second equation comprises the first signature verification element, the second signature verification element, elements of the public key and derived values. The verification module 125 is arranged to implement the verification step E15 of the partial signature derivation method as described previously.

[0142] The receiving module 123, the calculation module 124 and the verification module 125 are preferably software modules comprising software instructions for implementing those of the steps of the partial signature derivation method implemented by the partial signature verification entity 12.

[0143] The invention therefore also concerns:

[0144] a computer program including instructions for implementing the steps of the partial signature derivation method as described above and implemented by the partial signature verification entity when this program is executed by a processor of the partial signature verification device 12,

[0145] a readable recording medium on which the computer program described above is recorded.

[0146] The invention also relates to a partial signature derivation and verification system which comprises:

[0147] a partial signature derivation entity 11 as described above, and

[0148] a partial signature verification entity 12 as described previously.

[0149] Although the present disclosure has been described with reference to one or more examples, workers skilled in the art will recognize that changes may be made in form and detail without departing from the scope of the disclosure and/or the appended claims.