US-12621165-B2 - Methods and devices for authentication and verification of non-revocation

US12621165B2US 12621165 B2US12621165 B2US 12621165B2US-12621165-B2

Abstract

Method and device for authentication of non-revocation. A revocation list includes at least one pair extracted from a signature generated by a revoked entity, where h i is an element of a mathematical group and k i =h i xi , where xi is a secret of the revoked entity. A first entity sends, to a second entity, to authenticate itself therewith: a signature generated by the first entity for this authentication; a character string; an element of the group for each pair in the revocation list; and a zero-knowledge proof that the first entity used a secret of this first entity and the character string to obtain the group element for each pair. The second entity rejects the first entity if the zero-knowledge proof is not valid or if, for at least one the pair, the group element is such that C i =h i A , where A is a known value.

Inventors

Olivier Sanders

Assignees

ORANGE

Dates

Publication Date: 20260505
Application Date: 20220909
Priority Date: 20210915

Claims (9)

1 . An authentication method implemented by an authentication device of a first entity in order to authenticate said first entity with a second entity, said method comprising: generating a signature in order to authenticate the first entity with the second entity, said signature comprising a pair (h, h X100 ), where X100 is a secret specific to said first entity and h is an element of a mathematical group; for each index i of a pair (h i , k i ) contained in a revocation list, said pair (h i , k i ) having been extracted from a signature generated by a revoked entity, h i being an element of said group, with k i =h i xi , xi being a secret specific to said revoked entity: (i) obtaining, deterministically, a value a i from said index i and from a character string specific to said authentication; (ii) obtaining an element C i of said mathematical group using the formula C i =(h i a i ·k i ) A/ αi+X100 where: h i and k i are the elements of the pair of index i in the revocation list; A is a known value; a i is said deterministically obtained value; and X100 is the secret of the first entity; generating a zero-knowledge proof that said device used the secret X100 and said character string to obtain said group element C i for each of the pairs in said revocation list; and sending, to the second entity: said signature; said character string; said zero-knowledge proof; and said element C i for each pair in the revocation list.
2 . The authentication method as claimed in claim 1 , wherein said mathematical group is a cyclic group of order p, p being a prime number.
3 . The authentication method as claimed in claim 1 , wherein said character string is at least part of said signature.
4 . The authentication method as claimed in claim 1 , wherein said value a i is obtained by a i =H(STR∥i), where H is a public hash function.
5 . A non-transitory computer readable medium comprising a computer program stored thereon comprising instructions for executing the authentication method as claimed claim 1 when said program is executed by a processor of the authentication device.
6 . A non-revocation verification method implemented by a non-revocation verification device of a second entity during authentication of a first entity, said method comprising: receiving: a signature generated by said first entity for this authentication; a character string; an element of one and a same mathematical group for each pair (h i , k i ) contained in a revocation list, said pair (h i , k i ) having been extracted from a signature generated by a revoked entity, h i being an element of said group, with k i =h i xi , xi being a secret specific to said revoked entity; and a zero-knowledge proof that said first entity used a secret of this first entity and said character string to obtain said group element for each of the pairs contained in the revocation list; and rejecting said first entity on grounds of revocation if said zero-knowledge proof is not valid or if, for at least one said pair (h i , k i ), the group element (C i ) is such that C i =h i A , where A is a known value.
7 . A non-transitory computer readable medium comprising a computer program stored thereon comprising instructions for executing the non-revocation verification method as claimed in claim 6 when said program is executed by a processor of the non-revocation verification device.
8 . An authentication device of a first entity, said device being configured to authenticate said first entity with a second entity, said device comprising: at least one processor; and at least one non-transitory computer readable medium comprising instructions stored thereon which when executed by the at least one processor configure the authentication device to: generate a signature in order to authenticate the first entity with the second entity, said signature comprising a pair (h, h X100 ), where X100 is a secret specific to said first entity and h is an element of a mathematical group; for each index i of a pair (h i , k i ) contained in a revocation list, said pair (h i , k i ) having been extracted from a signature generated by a revoked entity, h i being an element of said group, with k i =h i xi , xi being a secret specific to said revoked entity: (i) deterministically obtain a value a i from said index i and from a character string specific to said authentication; (ii) obtain an element C i of said mathematical group using the formula C i =(h i a i ·k i ) A/ αi+X100 where: h i and k i are the elements of the pair of index i in the revocation list; A is a known value; a i is said deterministically obtained value; and X100 is the secret of the entity 100 ; generate a zero-knowledge proof that said authentication device used the secret X100 and said character string to obtain said group element (C i ) for each of the pairs in said revocation list; and send, to the second entity: said signature; said character string; said zero-knowledge proof; and said element C i for each pair in the revocation list.
9 . A non-revocation verification device, said device being configured to verify, during the authentication of a first entity with a second entity, whether this first entity should be rejected, said device comprising: at least one processor; and at least one non-transitory computer readable medium comprising instructions stored thereon which when executed by the at least one processor configure the authentication device to: receive: a signature generated by said first entity for this authentication; a character string; an element (C i ) of one and a same mathematical group for each pair (h i , k i ) in a revocation list, said pair (h i , k i ) having been extracted from a signature generated by a revoked entity, h i being an element of said group, with k i =h i xi , xi being a secret specific to said revoked entity; and a zero-knowledge proof that said first entity used a secret of this first entity and said character string to obtain said group element (C i ) for each of the pairs in said revocation list; and reject said first entity on grounds of revocation if said zero-knowledge proof is not valid or if, for at least one said pair (h i , k i ), the group element (C i ) is such that C i =h i A , where A is a known value.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This Application is a Section 371 National Stage Application of International Application No. PCT/FR2022/051705, filed Sep. 9, 2022, which is incorporated by reference in its entirety and published as WO 2023/041863 A1 on Mar. 23, 2023, not in English. BACKGROUND OF THE INVENTION The invention relates to the general field of digital data protection and cryptography. It lies more particularly in the context of authentication mechanisms. These authentication mechanisms are nowadays extremely widespread, in particular those based on digital signatures or certificates. The use of digital signatures poses a certain number of problems, in particular in that it makes it possible to trace the signatory and in that it potentially discloses too much information about the signatory. Indeed, when a digital signature relates to a set of certified data, the set of certified data has to be disclosed in order to be able to verify the authenticity thereof. This has led to the development of authentication techniques that aim to disclose as few elements as possible at the time of an authentication. These techniques are widely deployed and known as anonymous digital signatures. However, these anonymous authentication systems pose difficulties in terms of revoking the rights of an entity. To address this problem, an authentication mechanism known as EPID (Enhanced Privacy ID) has been defined (see for example the publication “Enhanced privacy id: a direct anonymous attestation scheme with enhanced revocation capabilities” by Brickell and Li, published at the WPS2007 conference). In this mechanism: an entity is said to be revoked when one of its signature keys is revoked, this being done by placing one of the signatures generated with this key on a revocation list;any entity that produces a signature must provide proof that this signature was not produced with the revoked key, that is to say with the key of a signature recorded in the revocation list, thus proving that the entity authenticating itself is not the one that has been revoked. The invention lies more specifically in the context in which the signatures comprise a pair (h, hx), where h is an element of a mathematical group and x is the secret of the signing entity, and in which this pair is written to the revocation list. This pair is denoted (hi, ki=hixi) hereinafter. The most effective technique known to date to report proof that a secret x used to produce a signature differs from a secret xi used to produce a signature (hi, ki=hixi) in the revocation list requires sending three elements of the mathematical group to the entity verifying the proof, this is to say around 894 bits. In practice, revocation lists may contain a very large number N of pairs (hi, ki=hixi), typically several tens of thousands. Having to communicate 3.N group elements (or 894.N bits) to prove that a signing entity is not revoked may constitute a significant drawback when N increases. The invention targets in particular an authentication method that does not exhibit this drawback. Aim and Summary of the Invention According to a first aspect, the invention relates to an authentication method implemented by an authentication device of a first entity in order to authenticate this first entity with a second entity. This method comprises: a step of generating a signature in order to authenticate the first entity with the second entity, said signature comprising a pair (h, hX100), where X100 is a secret specific to the first entity and h is an element of a mathematical group;for each index i of a pair (hi, ki) contained in a revocation list (LR), said pair (hi, ki) having been extracted from a signature generated by a revoked entity, hi being an element of said group, with ki=hixi, xi being a secret specific to said revoked entity: (i) a step of obtaining, deterministically, a value ai from said index i and from a character string specific to said authentication;(ii) a step of obtaining an element of the mathematical group using the formula Ci=(hiαi·ki)A/αi+X100 where: hi and ki are the elements of the pair of index i in the revocation list;A is a known value;ai is said deterministically obtained value; andX100 is the secret of the first entity; a step of generating a zero-knowledge proof that said authentication device used the secret X100 and said character string to obtain said group element Ci for each of the pairs in the revocation list; anda step of sending, to the second entity: said signature;said character string;said zero-knowledge proof; andsaid element Ci for each pair (hi, ki) in the revocation list. In correlation, the invention relates to an authentication device of a first entity, said device being configured to authenticate this first entity with a second entity, this device comprising: a module for generating a signature in order to authenticate the first entity with the second entity, said sig