Brevet FR2922067A1 — publié le 20090410

Calcul de preuve d'appartenance d'un secret à un intervalle, mettant en oeuvre une décomposition binaire Domaine technique La présente invention concerne un protocole d'authentification et/ou identification d'une première entité auprès d'une deuxième entité, à divulgation de connaissance nulle. Etat de l'art Dans des applications telles que des systèmes de monnaie électronique, ou de vote électronique, il est fréquent de mener une authentification d'une première entité ("prouveur") auprès d'une deuxième entité ("vérificateur"), en demandant à cette première entité de prouver qu'elle connaît un secret x appartenant à un intervalle [a, b]. Les techniques classiques pour prouver l'appartenance à un intervalle ont, pour la plupart, un défaut majeur. En effet, lorsqu'une entité possède un secret x appartenant à un intervalle I et souhaite prouver effectivement que ce secret x appartient à l'intervalle I, au sens de telles techniques, elle peut seulement convaincre une deuxième entité que le secret x appartient à un intervalle qui est généralement plus grand que l'intervalle précité I. Cet inconvénient a été résolu par une méthode dite "exacte" pour prouver qu'un secret appartient à un intervalle. En particulier, au sens de cette méthode, une entité est capable de prouver qu'elle connaît un secret x appartenant à un intervalle [a, b], où a et b sont des données fixes et connues, sans rien révéler néanmoins sur le secret x. Cette technique est dite "à divulgation nulle de connaissance" (ou "zero knowledge"). Une technique qui offre un tel avantage est celle décrite dans le document Boudot.: "Efficient Proofs that a Committed Number Lies in an Interval", Fabrice Boudot, Advances in Cryptology-Eurocrypt'00, vol.1807 de LNCS, pages 431-444, 2000.30 Cette technique utilise des propriétés mathématiques particulières du secret. Elle est caractérisée par le fait que certaines preuves d'appartenance à un intervalle convainquent uniquement le vérificateur que le secret x appartient à un intervalle plus grand que l'intervalle désiré. La technique décrite dans ce document Boudot introduit alors la notion de taux d'expansion qui se définit comme suit. On note ci-après E=E(x,r) un engagement sur un entier x appartenant à un intervalle [a, b]. Alors, une preuve d'appartenance à un intervalle [a, b] est une preuve qui convainc le vérificateur que le prouveur connaît un entier x tel que l'engagement E vaut E(x,r) et que ce secret x appartient à un intervalle [A, B] contenant l'intervalle précité [a, b]. En conservant ces notations, on appelle alors "taux d'expansion" d'une preuve d'appartenance à un intervalle, la quantité : 8= BûA bûa Le but de cette technique Boudot est donc d'obtenir un taux d'expansion égal à 1, ce qui permet d'avoir une preuve exacte, contrairement à ce qui était proposé dans les techniques classiques de l'état de l'art. Pour ce faire, le problème est posé comme suit : pour prouver que x appartient à l'intervalle [a, b], il suffit de savoir prouver qu'un nombre engagé est positif (prouver que x-a et b-x sont tous deux positifs ou nuls) ; de sorte qu'une caractérisation des nombres positifs (prouvable grâce au protocole à divulgation nulle de connaissance), connus, puisse être utilisée. La suite du traitement décrit dans Boudot n'est pas reprise ci-après. On indique simplement ici que le traitement repose sur le principe suivant : un nombre y strictement inférieur au nombre B est positif si et seulement si il peut s'écrire comme la somme d'un carré et d'un nombre compris entre 0 et 2a . Cette technique permet finalement de convaincre le vérificateur que le secret x appartient bien à l'intervalle [a, b], strictement. Pour estimer l'efficacité de cette technique, en termes de complexité, il a été calculé les exponentiations modulaires qui interviennent pour tous les engagements effectués (pour des engagements de la forme E(x,r)=gx h') en prenant un taux d'expansion 5=1. Dans ces conditions, il a été trouvé que la complexité de la technique, après analyse de la preuve, est donnée par : 57/2 IeI + 21 (Inl+s)+51(t+k)+22, où : - s, t et k sont des paramètres de sécurité, n est un entier définissant le modulo des expressions, notamment de l'engagement comme on le verra plus loin, e est la longueur de l'intervalle e=b-a. Dans cette technique Boudot, la variation de la taille du secret a peu d'influence sur la quantification de la complexité. Ainsi, pour un secret x de petite taille ou de très grande taille, la complexité varie peu. On notera d'ailleurs (en comparaison avec d'autres techniques décrites plus loin) que la méthode Boudot est assez complexe, même pour une petite valeur de la longueur de l'intervalle e. Il apparaît alors que cette technique, pourtant largement utilisée dans l'authentification par preuve de connaissance d'un secret dans un intervalle, à divulgation nulle des connaissances, n'est pas particulièrement avantageuse pour des tailles de secret x assez faibles. Or, dans certaines applications, la taille du secret x n'a pas besoin d'être particulièrement élevée. Par exemple, dans certains systèmes de vote électronique (où l'enjeu est de prouver que son choix de vote est bien compris dans l'ensemble des choix possibles), le secret peut par exemple être égal à 16 (s'agissant là d'un nombre maximum de candidats). Dans une autre application telle que la monnaie électronique, il est possible, par exemple, de retirer un nombre initial de pièces de monnaie (par exemple 100 pièces) et d'obtenir une signature de la banque débitrice sur le fait que ce nombre initial est retiré. Les pièces sont ensuite dépensées les unes après les autres en décrémentant un compteur, sans toutefois montrer la valeur de compteur utilisée, de manière à cacher son identité. Ainsi, dans nombreuses applications, dont celles précitées, le secret, en soi, n'a pas besoin d'être de trop grande valeur. Toutefois, la méthode de Boudot est pratiquement aussi complexe pour des secrets de petite valeur (de 16 ou de l'ordre de 100 dans les exemples d'applications précités) que pour des secrets de plus grande valeur. La présente invention vient améliorer la situation. Présentation de l'invention Elle propose à cet effet une technique tout aussi efficace que la technique Boudot, mais 10 dans laquelle la complexité est moindre pour des secrets de petite valeur. L'invention part alors d'une technique connue, décrite dans le document Bellare et al. : "Verifiable Partial Key Escrow", M. Bellare, S. Goldwasser. ACM Conference of Computer Science and Communications Security, pages 78-91, 1997. 15 Dans ce document, on cherche à montrer qu'un secret x appartient bien et très exactement à un intervalle [a, b] (et non pas à un intervalle plus grand). Il est proposé en particulier de considérer une décomposition, par exemple binaire, du secret x et des bornes a et b de l'intervalle précité. Toutefois, cette technique Bellare et al. est 20 complexe (nécessite de grandes ressources de calculs et de mémoire), en particulier pour des secrets de grande taille, par rapport à la technique Boudot décrite précédemment. La technique Bellare et al. est alors perfectionnée, au sens de l'invention, en particulier 25 en formulant l'hypothèse selon laquelle les bornes de l'intervalle a et b sont connues à la fois du prouveur et du vérificateur. L'expression de cette hypothèse permet alors de mettre en oeuvre un traitement préliminaire du calcul de la preuve et/ou de sa vérification qui : construit la preuve des connaissances en fonction des valeurs des bornes de 30 l'intervalle, et5 permet d'éliminer toute prise en compte des valeurs des bornes de l'intervalle dans le déroulement du protocole d'authentification (calcul de la preuve et communication du prouveur au vérificateur et vérification de la preuve par le vérificateur). Ainsi, la présente invention vise tout d'abord un procédé de communication entre une première entité et une deuxième entité, notamment pour une authentification de la première entité auprès de la deuxième entité, dans lequel la première entité prouve à la deuxième entité qu'elle connaît un secret dans un intervalle donné comportant une borne inférieure et une borne supérieure, en mettant en oeuvre au moins les étapes de : calcul d'un engagement en fonction du secret, calcul d'une preuve de la connaissance du secret en utilisant une décomposition binaire au moins du secret et des bornes de l'intervalle donné, et communication de l'engagement et de la preuve à la deuxième entité, et la deuxième entité recalcule la preuve au moins en fonction de l'engagement pour vérifier la preuve reçue de la première entité. Au sens de l'invention, les bornes inférieure et supérieure sont connues de la première entité et de la deuxième entité, et un traitement préliminaire au calcul de la preuve est mis en oeuvre pour simplifier une expression de la preuve, cette expression simplifiée de la preuve étant exempte de composantes issues de la décomposition binaire des bornes. Ainsi, la présente invention utilise, comme la technique Bellare et al., la décomposition 25 binaire. La technique au sens de l'invention est donc, comme la technique Bellare et al., dépendante de la taille du secret, contrairement à la technique Boudot. Toutefois, la technique au sens de l'invention est plus efficace, de toute façon, que la technique Bellare et al., utilisant la décomposition binaire, même dans le pire des cas, 30 puisqu'une hypothèse simplificatrice (connaissance des bornes par le vérificateur et par le prouveur) est menée, de façon efficace, au sens de l'invention, par rapport à la technique Bellare et al. Par ailleurs, la technique au sens de la présente invention est plus efficace, aussi, en termes de complexité, que la technique de Boudot, en particulier lorsque le secret est de petite taille. Par exemple, si le secret est décomposé sur 3 bits (N=23=8), la technique au sens de l'invention est beaucoup moins complexe (un facteur voisin de moitié dans le pire des cas), que la technique Boudot, et, si le secret est décomposé sur 4 bits (N=24=16), la complexité de la technique au sens de l'invention reste inférieure ou équivalente (dans le pire des cas) à la technique Boudot, comme on le verra plus loin. Toutefois, pour l'authentification proprement dite, la sécurité n'est pas forcément réduite lorsque la taille du secret est réduite. En effet, dans les applications ci-avant où l'engagement E(x,r)=gx h', g et h étant des éléments publics, comme souvent dans les applications précitées, le secret n'est pas donné forcément comme le logarithme discret d'un élément public (par exemple un secret x tel que y=g ), mais comme élément de la représentation d'un élément public (typiquement le secret x tel que y=g h'). Ainsi, dans cet exemple de réalisation où l'engagement est donné par une fonction de type E(x,r)=g h', l'élément r (typiquement un aléa tiré par le prouveur) est souvent un nombre très grand pour justement "cacher" le secret x. Par exemple, dans le cas d'un groupe d'ordre connu, on prendra typiquement un nombre r ayant une taille de 160 bits. Ainsi, la taille du secret x importe peu et, dans des applications concrètes, il n'est pratiquement pas possible de retrouver le secret x, même si ce secret est petit, par exemple ayant une valeur de 8 ou 16. Ainsi, en moyenne, la complexité de la technique au sens de l'invention devient plus intéressante que celle de la technique Boudot pour des tailles de secret plus petites, en restant toutefois très avantageuse dans un grand nombre d'applications possibles.30 Comme on le verra dans les exemples de réalisation décrits ci-après, la preuve peut avantageusement s'exprimer simplement en fonction : - d'une première liste des suites possibles des composantes de la décomposition binaire du secret en fonction des valeurs respectives des composantes de la décomposition binaire des bornes de l'intervalle donné, et - préférentiellement d'une deuxième liste, combinée par un "ET" à la première liste précitée, et représentant, si une valeur de composante x, du secret a pu être déterminée en fonction de valeurs de composantes des bornes de l'intervalle donné, toutes les possibilités de valeurs des composantes x;_1, xi_2, ..., xo d'ordres inférieurs à la composante x, dans la décomposition binaire du secret x. Liste des figures D'autres avantages et caractéristiques de la présente invention apparaîtront à l'examen de la description détaillée ci-après, en référence aux dessins annexés, sur lesquels : la figure 1 représente schématiquement les calculs réalisés par le prouveur (entité El) et le vérificateur (entité E2) pour la preuve de la connaissance d'un secret x tel que a Description détaillée Comme la présente invention s'appuie sur la technique Bellare et al. citée ci-avant, on rappelle tout d'abord les principes de cette technique Bellare et al. Cette technique met en oeuvre une décomposition binaire du secret et des bornes de l'intervalle [a, b], auquel appartient le secret. Ensuite, par comparaisons successives, on renvoie tous les résultats que le secret x peut prendre comme valeurs dans le cas où le secret x est tel que a x, d'une part, et dans le cas où le secret x est tel que x b, d'autre part. Pour une décomposition binaire sur 1=3 bits, par exemple, le premier cas : a x s'écrit : ao +a,2+a222 9 (x2 =1 et a2 = 0) ou (x2 = a2 et x, =1 et a, = 0) ou (x2 = a2 et x, =a, et xo =1). Dans la technique Bellare et al, on prouve séparément que a x et que x b. On traite d'abord la preuve qu'un nombre engagé x est tel que : a x Les paramètres suivants sont publics. Il s'agit de : le nombre composé n, produit de deux nombres premiers forts p=2p'+1 et q=2q'+l, avantageusement congrus à 3 modulo 4 pour des propriétés de sécurité optimales, et dont la factorisation est connue seulement d'une autorité distincte du prouveur ou du vérificateur; un élément g de l'ensemble Z , d'ordre p'q', de telle sorte que le problème du logarithme discret modulo n en base g soit un problème difficile, et qu'aucune racine e-ième de �g ne soit connue ; trois paramètres de sécurité s, t et k ; un élément h du groupe engendré par g, tel que le logarithme discret de h en base g soit inconnu ; la fonction d'engagement E(x,r) = geh' mod* n ; et la borne inférieure a. Deux paramètres sont secrets : il s'agit du secret x avec a S x et du paramètre r tel que : t, [ù~:rt + I. `'sri ù 1] A partir de ces deux paramètres est calculé l'engagement E = E(x,r). Ci-après, on note : la preuve que calcule le prouveur et qu'il communique au vérificateur, avec la valeur E de l'engagement, et selon laquelle il connaît un secret x vérifiant l'engagement E=(x,r) et aussi tel que ce secret est supérieur ou égal à la borne a. On comprendra ainsi que la notation " A " désigne l'opérateur "ET", tandis que la notation " v " désigne l'opérateur "OU exclusif'. En référence à la figure 1, le protocole d'authentification entre une entité E1 (prouveur) et une entité E2 (vérificateur) se déroule comme suit : l'entité El connaît le secret x auquel elle applique la décomposition binaire de 0 à l-1 (bit de poids fort) ; par ailleurs, les deux entités El et E2 connaissent la borne a à laquelle elles appliquent chacune une décomposition binaire ; l'entité El (prouveur) tire aléatoirement le secret r dans un ensemble prédéterminé et calcule l'engagement C=g' h` ; elle tire aussi des éléments r; dans un même ensemble, prédéterminé aussi, et calcule les termes C, = g' K' qui interviennent rùi dans le produit C = fl C2- qui est noté C = gxh' , de sorte que CC-' = gx Xh' ' =o avec, en particulier, CC-' = si et seulement si les composantes x; sont bien les valeurs de bits du secret x. L'entité E 1 calcule aussi la preuve PK qui dépend notamment d'un terme a représentant le secret x, d'une terme 3 représentant l'entier r, des termes yo, ..., y14 représentant les composantes ro, ..., , et d'un terme 8 représentant la différence r û . On relèvera d'ailleurs, dans le calcul de la preuve illustré sur la figure 1, que l'expression C, / g = hY (C, = g'hr ) correspond au cas où x1, l'expression C, = hr (C, = g°hy = hY ) correspondant, quant à elle, à l'autre cas où x,=0. L'entité El envoie à l'entité E2: rù1 les éléments Cä l'entité E2 en déduisant = gXhr = [jC2' =o la valeur C de l'engagement, l'entité E2 en déduisant CC-' = gC zh' , et - la preuve PK, l'entité E2 vérifiant la preuve PK avec les données dont elle dispose, en considérant a priori que i = x . Dans la technique Bellare et al., un traitement équivalent est appliqué pour le deuxième cas : x b. Il part du constat, dans un exemple simple d'une décomposition sur 3 bits, que x b revient à écrire xo + x,2 + x222 bo +b,2+ b222 , ce qui est vrai si : (b2=1 et x2 = 0 ) ou ( b2 = x2 etb,=1 et x,=0)ou(b2=x2 et b,=x, etbo=1). De même ici, la preuve que x b revient à prouver qu'un nombre engagé x est tel que xb. En se référant maintenant à la figure 2, le protocole se déroule comme précédemment (cas a x), avec maintenant toutefois la connaissance par les entités El et E2 de la décomposition binaire de la deuxième borne b de l'intervalle, laquelle est maintenant un paramètre public à la place de la première borne a. Par ailleurs, le secret x est maintenant tel que x b. Sinon, les autres paramètres publics et secrets sont les mêmes que précédemment. Pour le protocole global a x 5 b où la preuve PK s'exprime : Pliatd{a b : = E(x, f) , a il suffit, dans la technique Bellare et al., de faire la concaténation des deux procédés illustrés sur les figures 1 et 2. Certes, certaines simplifications sont possibles, notamment dans la première partie du protocole lorsque les termes x, issus de la décomposition binaire du secret sont comparés et que les valeurs C=g" ha et CC-' = hS sont alors vérifiées. Toutefois, même avec ces simplifications, la preuve de connaissance est loin d'être optimale car elle est composée d'exponentiations modulaires très coûteuses en temps de calculs. Par conséquent, du fait de sa complexité, cette technique nécessite une amélioration. Au sens de la présente invention, une simplification de la preuve initiale PK basée sur la décomposition binaire est mise en oeuvre en utilisant, en particulier, le fait que le vérificateur, comme le prouveur, connaît aussi les valeurs des bornes a et b. Ainsi, selon leurs valeurs respectives, il est possible de générer une preuve parfaitement adaptée car le résultat obtenu est optimal par rapport aux valeurs des bornes a et b. En effet, en référence aux figures 1 et 2 décrites ci-avant, le calcul de la preuve faisait toujours intervenir les composantes a, et b; issues de la décomposition binaire des bornes a et b. Il va être montré ci-après que le calcul de la preuve PK est grandement simplifié par la mise en oeuvre de l'invention et, en particulier, ne fait plus intervenir, finalement, les composantes a, et b;. Pour ce faire, au sens de l'invention, il est introduit un traitement préliminaire qui génère la preuve à effectuer, selon les valeurs des bornes a et b. On prévoit globalement un traitement préliminaire incluant deux sous-traitements. Un premier sous-traitement est illustré sur les figures 3A et 4. Un deuxième sous-traitement est illustré sur les figures 3B et 4. Ce premier et ce deuxième sous-traitement permettent d'établir deux listes L° et Lb respectives, représentant toutes les suites possibles des valeurs que peuvent prendre les composantes x; pour le secret x par rapport aux composantes a, de la borne a (pour le premier sous-traitement) et par rapport aux composantes b; de la borne b (pour le deuxième sous-traitement). En reprenant l'exemple d'une décomposition sur 3 bits, si ao = 1, al = 1 et a2 = 0 (les possibilités pour x étant 100, 110, 111, et bien entendu le cas x=a : 011), la liste L° que donne le premier sous-traitement s'écrit : L:{(C2/g=h72)v[(C2 =h72)A(CI =le)n(Co =hY')]} ce qui correspond bien à (x2 =1) v [(x2 = 0) A (x, =1) A (x0 =1)1 . On décrit maintenant, en référence à la figure 3A, comment se déroule le premier sous-traitement au sens de l'invention. Globalement, chaque sous-traitement s'effectue en deux boucles, une première boucle (figure 3A, figure 3B) décrémentant l'indice i des éléments x issus de la décomposition binaire du secret x (i=0,1, ..., l-1), l'autre boucle incrémentant l'indice i (figure 4). Dans l'exemple de réalisation représenté, le sous-traitement de la figure 3A commence par une étape 30 où la valeur de i à décrémenter est initialement fixée à une valeur io qui sera décrite plus loin, en référence à la figure 5 illustrant le traitement général faisant appel au deux sous-traitements. On prévoit donc un indice de boucle i dans les traitements des figures 3A et 3B, qui va être décrémenté de la valeur io jusqu'à 0. Le test 32 de la figure 3A consiste à vérifier que tous les éléments a; de la décomposition binaire de la borne inférieure a, à partir d'un indice courant i (soit a; , , ..., ao ), ne sont pas tous nuls. Si l'un au moins de ces éléments est nul (flèche O en sortie du test 32), la liste L°, des suites possibles pour les éléments x; , ..., xo correspond simplement à l'ensemble vide, soit : L°, = 0 , et le sous-traitement s'arrête à cette étape 34. En revanche, si l'un au moins des éléments a; , ., ao est non nul (flèche N en sortie du test 32), le sous-traitement se poursuit en analysant une à une les composantes a; , , ..., ao de la borne a. Si une valeur courante d'une composante a; vaut 1 (flèche O en sortie du test 36), alors la valeur d'une composante de même indice x; est 1, de sorte que C; / g = kir' . Il s'agit là d'une condition pour l'indice i de la liste courante L°; , qui sera combinée par un "ET" à la liste L°,_, trouvée pour un indice de boucle suivant i-1. On stocke alors en mémoire (étape 38) l'expression de la liste courante L", comme suit : L :(C,/g=h')AL",_1 En revanche, si une valeur courante d'une composante a; vaut 0 (flèche N en sortie du test 36), alors la valeur d'une composante de même indice x; peut être aussi bien 0 ou 1, de sorte qu'on a respectivement C, = hY ou C, / g = hy . Il s'agit là encore d'une autre "condition" pour l'indice i de la liste courante L°, , qui sera combinée par un "ET" à la liste L",_1 trouvée pour un indice de boucle suivant i-1. On stocke alors en mémoire (étape 40) l'expression de la liste courante L comme suit : L" :(C;lg=h')v[(C, =hr' )AL°;_,] Il convient de noter que la valeur d'une composante courante x, du secret peut déterminer directement l'expression de la liste L", . Par exemple ici, si x; =1 à l'étape 40, on a simplement la liste L", donnée par L°; : (C, / g = hy) , de sorte qu'elle ne dépend pas d'une liste L"à déterminer pour un indice de boucle i-1 suivant (décrémenté). Le traitement s'arrête simplement dans ce cas à L", : (C; / g = hy) . En revanche si x, =0, la liste L", est donnée par L", : [(C, = hy ) A L°;_I ] et la liste L"de l'indice de boucle suivant doit être déterminée...DTD: Toutefois, on décrit ici le calcul générique de la preuve (en référence aux figures 3A, 3B, 4, 5 et 6), indépendamment de la valeur du secret car, en pratique, ce calcul générique est programmé une fois pour toutes (sous la forme d'une suite d'instructions informatiques) et un tel programme peut être exécuté pour tout secret x qui sera pris dans un même intervalle [a, b]. En référence à nouveau à la figure 3A, on recommence les tests 32 ou 36 et les étapes 34 ou 38 ou 40 pour un indice de boucle i=i-1 suivant (décrémentation 41), tant que l'indice courant i est supérieur ou égal à 0 (flèche N en sortie du test 42). Ainsi, une liste L" s'écrit L" = f" (L" )=f " (f" (L" �=f �f �...f� L" ))) ~ ro-1 1,,-2 yä0 avec : fa1(L"i-1)=QJ,ou - f"- 1(L"i_1) : (C; l g = hy ) A L"r_1, ou - f;°- , (L";_I):(C,/g=h7)v[(C; =h')AL";_1], selon le cas stocké en mémoire à l'une des étapes 34, 38 ou 40, en fonction de la valeur des composantes a;. Il faut donc calculer toutes les conditions possibles 34, 38 ou 40 sur les listes L°; jusqu'à la dernière liste L 0 portant sur la composante ao et remonter ensuite à une liste Lai, pour io supérieur ou égal à o, à partir de Lao . Au besoin, on fixera L = 0 pour i strictement inférieur à 0 (pour i=-1 typiquement). La construction de la liste L° nécessite donc une ré-incrémentation sur l'indice courant i. Ainsi, en référence maintenant à la figure 4, lorsque la valeur i=-1 a été atteinte par l'indice de boucle i (flèche O en sortie du test 42 de la figure 3A), on reconstruit progressivement la liste L°; . La dernière liste Lao ayant été déterminée pour la composante ao (dernière boucle de la figure 3A), l'expression de cette liste Lao est lue en mémoire (étape 43) et l'expression de la liste L°, se déduit de = fo (Lao ) que donne une nouvelle lecture en mémoire (étape 45). Plus précisément, on mène la détermination des listes L°; en boucle sur l'indice i (fixé initialement à i=0 à l'étape 44 et avec incrémentation à l'étape 46). On relèvera en revanche qu'un résultat possible issu de l'étape 34 de la figure 3A (La, = 0) n'est pas concerné par cette ré-incrémentation de l'indice i et peut être directement injecté avec la valeur que prenait l'indice i à cette étape 34, immédiatement après l'étape 44 de la figure 4 (donc sans fixer i=0). En revanche, un test (non représenté sur la figure 4) sur cette valeur courante de l'indice i sera mené pour vérifier que l'indice i n'est pas directement égal à io, auquel cas le traitement de la figure 4 s'arrête simplement à l'étape 48 en donnant directement la liste L = 0 (ou la liste Lh = 0 si le traitement mené commence par la figure 3B, comme on le verra plus loin). Lorsque la valeur courante de i atteint i=io-1 (flèche O en sortie du test 47), la dernière 5 liste calculée L +, à l'étape 45 correspond à la liste recherchée L°; et le premier sous-traitement s'achève (étape 48). En référence maintenant à la figure 3B, on décrit succinctement comment se déroule le deuxième sous-traitement. Globalement, les mêmes références 30, 41, 42 que sur la 10 figure 3B désignent les mêmes éléments ou des éléments similaires. Ainsi, le deuxième sous-traitement commence aussi par une étape 30 où la valeur de l'indice i à décrémenter est initialement fixée à une valeur io décrite plus loin. Le test 31 consiste à vérifier que tous les éléments b; de la décomposition binaire de la borne supérieure b, à partir de l'indice courant i (soit b, , ..., bo ), ne sont pas tous égaux à 1. Si tel est le cas 15 (flèche O en sortie du test 31), la liste Lb, des suites possibles pour les éléments x; , ..., xo est fixée à l'étape 33 à Ln, = . En revanche, si l'un au moins des éléments b; , ..., bo est nul (flèche N en sortie du test 31), le sous-traitement se poursuit en analysant une à une les composantes b; , b;_, bo de la borne b. Si une valeur courante d'une composante b; vaut 0 (flèche O en 20 sortie du test 35), alors la valeur d'une composante de même indice x; est 0, de sorte que C, = hr' . Il s'agit là d'une condition pour l'indice i de la liste courante Lb, , qui sera combinée par un "ET" à la liste L";_, trouvée pour un indice de boucle suivant i-1. On stocke alors en mémoire (étape 37) l'expression de la liste courante Lb, comme suit : Lh; :(C; =h�)ALh(-1 25 En revanche, si une valeur courante d'une composante b, vaut 1 (flèche N en sortie du test 35), alors la valeur d'une composante de même indice x, peut être aussi bien 0 ou 1, de sorte qu'on a respectivement C, = hr ou C, / g = hr . On stocke alors en mémoire (étape 39) l'expression de la liste courante Lh; comme suit : Lb, :(C, =h%)v[(C;lg=hr)ALh;_,] Selon la même remarque formulée précédemment en référence à la figure 3A, le traitement peut s'arrêter simplement ici à Lh; :(C, = hr) si la composante x; du secret est telle que x; =0. Sinon, le traitement se poursuit pour calculer la liste Ln;_, . On recommence alors les tests 31 ou 35 et les étapes 33, 37 ou 39 pour un indice de boucle i=i-1 suivant (décrémentation 41), tant que l'indice courant i est supérieur ou égal à 0 (flèche N en sortie du test 42). En référence maintenant à la figure 4, lorsque la valeur i=-1 a été atteinte par l'indice de boucle i (flèche O en sortie du test 42 de la figure 3B), on reconstruit progressivement la liste L", . La dernière liste Lho a été déterminée pour la composante bo (dernière boucle de la figure 3B) en fixant Lh; = 0 pour i=-1. Sur la figure 4, l'expression de cette liste Lho est lue en mémoire (étape 43) et l'expression de la liste Ln, se déduit de Lh, = f h (Lho) que donne une nouvelle lecture en mémoire (étape 45). Plus précisément, on mène la détermination des listes Lh; , en boucle sur l'indice i, avec, selon les expressions stockées en mémoire pour chaque indice i : Lb, = fh Lh;_, G =h nLh;_,, ou Lh;=fh~(Lh;_,):(C,=hr)v[(C,/g=hr)AL" On relèvera encore ici qu'un résultat possible issu de l'étape 33 de la figure 3B (Lb, = 0) n'est pas concerné par la ré-incrémentation de l'indice i et peut être directement injecté avec la valeur que prenait l'indice i à l'étape 33, immédiatement après l'étape 44 de la figure 4 (sans fixer i=0).25 Lorsque la valeur courante de l'indice i atteint i=io-1 (flèche O en sortie du test 47), la dernière liste calculée Lh,+, à l'étape 45 correspond à la liste recherchée Lh, et le deuxième sous-traitement s'achève (étape 48). On se réfère maintenant à la figure 5 pour décrire un exemple de réalisation du traitement global au sens de l'invention. On construit ici deux listes : - une première liste L représentant toutes les suites possibles pour les composantes du secret x, par rapport aux suites connues des composantes respectives des bornes a et b, et - une deuxième liste î représentant toutes les possibilités restantes pour chaque bit du secret (x,=0 ou x;=1). Par exemple, pour une décomposition sur 3 bits, si ao= ai= a2=0 et bo=0, b1=1 et b2=0, la première liste L précitée est : L:(C2=h72)n[(C,=le)v((Cl/g=hy')A(Co=hY°))], ce qui correspond à x2=0 et (x1=1 ou (xi=1 et xo=0)), et la deuxième liste L s'écrit simplement (puisque le choix pour x2 est fixé) : L:[(C, =h7'')v(Cl/g=h7')]A[(Co =hy')v(Colg=hY')], ce qui correspond à [(xi=0 ouxi=l) et (xo=O ouxo=l)]. Comme précédemment, on prévoit une boucle avec décrémentation de l'indice de boucle i, puis ré-incrémentation de cet indice de boucle (figure 6). Dans l'exemple de traitement illustré sur la figure 5, on commence par fixer (étape 50) la valeur de l'indice de boucle à i = l-1, car, comme on le verra plus loin, la preuve PK au sens de l'invention s'exprime en fonction des listes L et i calculées jusqu'à i = l-1. Pour un indice de boucle courant i, on analyse si toutes les composantes a;, ..., ao sont toutes nulles et si toutes les composantes b;, ..., bo sont toutes égales à 1 (tests 51 û 52). Si tel est le cas (flèches O en sortie des tests 51 et 52), on fixe une valeur courante de la première liste à L, = 0 à l'étape 53 et la deuxième liste à : L=TOT,:[(C,=hr)v(C,/g=hr)]n...A[(Co=h'°)v(Co/g=hr°)] correspondant à toutes les possibilités x, =0 ou x,=1 pour tout i. Si toutes les composantes a, ne sont pas toutes nulles et/ou si toutes les composantes b; ne sont pas toutes égales à 1 (au moins une flèche N en sortie de l'un des tests 51 et 52), le traitement se poursuit par le test 54 visant à déterminer, pour l'indice de boucle i courant, si on a : b, = a, =0. Si tel est le cas, alors la première liste L; associée à cet indice courant i est donnée, à l'étape 55, par l'expression suivante, stockée en mémoire : L, :(C, =h7 ) A L,_1 On teste aussi si b = a =1 (test 56), auquel cas on a (étape 57) l'expression suivante, stockée en mémoire : L,:(C,/g=h'')AL,_1 On relèvera que ces deux étapes 55 et 57 font intervenir la liste L;_1 associée à l'indice de boucle décrémenté i-1. Ainsi, à l'issue de ces deux étapes 55 et 57, on mène une décrémentation (étape 63) sur l'indice i pour calculer subséquemment au moins la liste L;_1, éventuellement la liste L1_2, et ainsi de suite si l'un des tests 54 et 56 est satisfait, et ce tant que l'indice i n'a pas atteint i=-1 (flèche N en sortie du test 64). Toutefois, on notera que l'indice i=-1 n'est atteint que si a=x=b. Dans ce cas, la seconde liste est telle que L = 0 et on notera la première liste Lo. En revanche, si aucun des tests 54 et 56 n'est satisfait, alors on a b,=1 et a;=0 (test 58) et la première liste L; est donnée par l'expression suivante, stockée en mémoire (étape 61) : L,:[(C,=h7)ALa,_,]v[(G,/g=h7)ALb,_1], ce qui nécessite alors de calculer les listes L°et Lb(étape 59) en faisant appel respectivement aux premier et deuxième sous-traitements des figures 3A, 3B et 4, et en fixant l'indice de départ io à l'étape 30 des figures 3A et 3B à la valeur de io = i-1 (étape 60), où i est la valeur courante de l'indice de boucle de la figure 5. A l'étape 62 de la figure 5, on calcule aussi la deuxième liste, simplement en fonction de la dernière valeur courante de l'indice de boucle i de la figure 5, comme suit : L=TOT,:[(C,=hr' )v(C,/g=h7)]A...A[(Co=hT')v(Co/g=h70)] On relèvera qu'en pratique, le "test" 58 n'est pas réellement un test dans la mesure où, si on avait a, =1 et b! 0, alors forcément il existait un entier positif k tel que a,+k=O et b,+k=1 (si a On se réfère à la figure 6 sur laquelle, comme décrit précédemment en référence à la figure 4, on reconstruit la liste complète L en incrémentant un indice de boucle courant i, comme suit. Le traitement commence : soit par la réponse positive (flèche O) en sortie du test 64 de la figure 5 (la valeur courante de l'indice de boucle i étant i=-1), soit par la dernière étape 48 de la figure 4 livrant et Lh soit par l'étape 53 de la figure 5 avec l'indice courant de boucle i en sortie de cette étape 53 et pour lequel L; = 0. Ainsi, on calcule : - soit Lo (étape 65) à partir de l'une ou l'autre des expressions définies aux étapes 55 et 57 et stockées en mémoire, à partir de L_, = 0 , puis on fixe l'indice de boucle à i=0 (étape 66), soit L, (étape 67) à partir de l'expression définie à l'étape 61 et avec les listes L,_, et Lb,' . Si le traitement commence par l'une des étapes 48 ou 53, on vérifie que l'indice i n'est pas déjà égal à l-1 (test 74) auquel cas la première liste L peut être donnée directement à l'étape 75, soit par le résultat de l'étape 67, soit par L = L, = 0 . Sinon (flèche N en sortie du test 74), le traitement se poursuit communément par l'étape 68, à laquelle on calcule une liste L;+1 (étape 68) en utilisant l'une ou l'autre des expressions définies aux étapes 55 et 57, en fonction de la liste L. La liste L,+1 trouvée est stockée en mémoire (étape 69) pour servir dans une boucle suivante où l'indice de boucle i a été incrémenté (étape 71), et ce jusqu'à ce que la dernière liste trouvée L;+1 soit telle que L;+, = (test 70). On obtient ainsi la liste finale L (étape 72 ou étape 75) qui va servir au calcul de la preuve PK (étape 73), laquelle est donnée par l'expression : PK:[(C=gahfl)A(CC-' =hs)ALAL] La deuxième liste i a son expression déterminée à l'issue de l'une des étapes 53 et 62 de la figure 5 et est telle que L = 0 s'il advient que le test 64 soit positif. Les deux listes obtenues L et i sont optimales. On relèvera que l'expression de la preuve PK ne fait plus apparaître, au sens de l'invention, un quelconque élément (ao, ..., a!-1, bo, ..., b1.1) relatif aux bornes a et/ou b, contrairement aux expressions des preuves au sens de l'art antérieur Bellare et al illustré sur les figures 1 et 2. Cette propriété découle avantageusement du fait que les bornes a et b sont censées être connues du prouveur et du vérificateur. Typiquement, le prouveur n'a pas besoin de démontrer au vérificateur sa connaissance des bornes et leurs composantes n'apparaissent plus dans l'expression de la preuve PK. Par ailleurs, la preuve PK est calculée une fois pour toutes pour un même intervalle [a, b], quand bien même la valeur du secret x pourrait varier dans cet intervalle, d'une authentification à l'autre. 22 On se réfère maintenant à la figure 7 illustrant la communication entre l'entité El (prouveur) et l'entité E2 (vérificateur) notamment pour une authentification de l'entité El, dans un contexte dit de "groupe inconnu" et dans lequel les paramètres publics sont : un nombre composé n, produit de deux nombres premiers forts p=2p'+1 et q=2q'+1, congrus à 3 modulo 4, dont la factorisation est connue seulement d'une autorité distincte du prouveur ou du vérificateur; un élément g de l'ensemble Z*,, (l'ensemble des entiers relatifs modulo n (avec n+1=1)), d'ordre p'q', de telle sorte que le problème du logarithme discret modulo n en base g soit un problème difficile, et qu'aucune racine e-iéme de �g ne soit connue ; trois paramètres de sécurité s, t et k ; un élément h du groupe engendré par g, tel que le logarithme discret de h en base g soit inconnu ; la fonction d'engagement E(x,r) = gxhr mod* n ; et deux bornes a et b de l'intervalle 1= [a, b]. Les paramètres secrets sont : - le nombre secret x tel que a Plus particulièrement, en référence à la figure 8, les deux entités El et E2 connaissent les bornes a et b et donc leur décomposition binaire. Le prouveur El connaît aussi le secret x et sa décomposition binaire.30 Le prouveur El tire aléatoirement des éléments ro, ri, ..., rl_i dans un même intervalle tel que : 2;+'+srr en rappelant que t, k et s sont les paramètres de sécurité précités. Le prouveur El calcule aussi : l'engagement, noté ici C et tel que C=g' h', les éléments C, = eh' , où les termes x, représentent les composantes issues de la décomposition binaire du secret x, r-1 ainsi que le produit C=-n( i )2 qui est noté = gxh' de sorte que r=o CC ' = gx-xh'-' , avec en particulier CC-' = h'-' si et seulement si les composantes x; sont bien issues de la décomposition binaire du secret x. 1-1 On notera alors que F = E r; .2` =o L'entité El calcule enfin la preuve PK comme décrit ci-avant en référence aux figures 3A,3B,4,5et6. L'entité El envoie à l'entité E2 : les éléments C;, l'entité E2 en déduisant C = gxh' = fil (C1 )2 , =o la valeur C de l'engagement, l'entité E2 en déduisant CC-' = gx-xh'-' , et la preuve PK, l'entité E2 vérifiant la preuve PK avec les données dont elle dispose, en considérant a priori que x = x . Dans un contexte dit "de groupe connu", il est possible de choisir certains paramètres du protocole dans l'ensemble Zq (l'ensemble des entiers relatifs modulo q (avec q+ 1=1)). Dans ce contexte, les paramètres publics sont maintenant, comme illustré sur la figure 9 : 24 un grand nombre premier p ; un grand nombre premier q tel que q divise p-1 ; un élément g de l'ensemble 7L~n d'ordre q ; un paramètre de sécurité k tel que 2k Les paramètres secrets sont : le nombre secret x tel que a x b, et le nombre r appartenant ici à l'intervalle [0, q-1], et l'engagement E est calculé en fonction de ces deux paramètres : E = E(x,r). Dans le protocole de la figure 9, la complexité est moins forte que lorsque les éléments du protocole sont d'ordre inconnu (technique dite de "groupe inconnu"). Toutefois, on devra choisir l'une ou l'autre des techniques (groupe connu ou groupe inconnu) en fonction de l'application visée. On donne d'ailleurs ci-après des comparaisons de complexités (en termes de nombres d'opérations de calcul), pour la technique Boudot et pour la technique au sens de l'invention. Ces calculs de complexité sont donnés pour les pires cas de mise en oeuvre de 25 l'invention, avec dans l'exemple ici a = 0 et b = bo + b, 2 +... + b,_, 21-1. Les complexités sont données alors par les expressions : 57/2 lei + 21 (InI+s) + 51 (t+k) + 22, pour la technique Boudot décrite ci-avant (laquelle, pour rappel, consistait à prendre initialement un intervalle d'appartenance plus grand que [a, b]); 12 lJgI + 11/2 1 û 3 Iql - 1, pour la technique au sens de la présente invention, en prenant un contexte de groupe connu (figure 9) ; et 12 lk + 15/2 lt + 15/2 11111 + 15/2 ls + 7 1 û 3 k + 3/2 s + 3/2t û 2, pour la technique au sens de la présente invention, en prenant un contexte de groupe inconnu (figures 7 et 8). Dans la figure 10, on donne un tableau des valeurs numériques des complexités de ces différents protocoles, calculées pour des valeurs successives de l'ordre 1, et en prenant In1=1024, s=40, t=40, k=80, IeH=512 et 1qI=160 pour la mise en oeuvre de l'invention en contexte de groupe connu (colonne GC, tandis que la colonne relative aux calculs en contexte de groupe inconnu est référencée GI). Il apparaît que pour des valeurs de secret trop grandes (1 supérieur ou égal à 16 pour la mise en oeuvre de l'invention en contexte de groupe connu GC et 1 supérieur ou égal à 3 pour la mise en oeuvre de l'invention en contexte de groupe inconnu GI), la technique de Fabrice Boudot paraît plus avantageuse car moins complexe. En revanche, pour des valeurs de secret plus petites, la technique au sens de l'invention est bien plus avantageuse, notamment en contexte de groupe connu. Par conséquent, on comprendra que la présente invention est particulièrement avantageuse avec un calcul d'engagement de la forme E(x,r) =g hr où le nombre r est très grand devant le secret x, lequel peut simplement alors être décomposé sur 3 ou 4 bits. Ainsi, en contexte de groupe d'ordre inconnu, le secret x pourra typiquement de l'ordre de 5 à 20 et préférentiellement compris entre 8 et 16, en considérant toujours le pire cas, tandis qu'en contexte de groupe d'ordre connu, en considérant encore le pire cas, le secret x peut avoir une valeur jusque de l'ordre de 216 (= 65536). En effectuant une analyse en moyenne (pas nécessairement du pire cas) de la complexité du traitement au sens de l'invention, dans le cas d'un groupe d'ordre connu, on arrive à des secrets pouvant avoir une valeur jusqu'à l'ordre de 225.30 La présente invention vise aussi un programme informatique, destiné à être stocké en mémoire d'une entité prouveuse El et/ou d'une entité vérificatrice E2, pour le calcul de preuve PK de la connaissance d'un secret x dans un intervalle donné [a, b], un tel programme comportant des instructions pour la mise en oeuvre du procédé au sens de l'invention, lorsqu'elles sont exécutées par un processeur de l'entité prouveuse E 1 et/ou de l'entité vérificatrice E2. Par exemple, un organigramme d'un tel programme pourrait correspondre à l'ensemble des figures 3A, 3B, 4, 5 et 6. La présente invention vise aussi une entité prouveuse, destinée à communiquer avec une entité vérificatrice, pour prouver la connaissance d'un secret dans un intervalle donné, et comportant une mémoire stockant un tel programme informatique. La présente invention vise aussi une entité vérificatrice, destinée à communiquer avec une entité prouveuse pour vérifier la preuve communiquée par l'entité prouveuse de la connaissance d'un secret dans un intervalle donné, et comportant une mémoire stockant un programme informatique du type précité. L'invention vise aussi un système pour la mise en oeuvre du procédé et comportant une telle entité prouveuse et une telle entité vérificatrice. Bien entendu, la technique au sens de l'invention est optimale par rapport à la technique Bellare et al. En effet, en comptant le nombre d'opération par calcul de preuve, on a : - 21+ 2 + 1(1û1) / 2 pour la preuve PK (x, r : E = E (x, r) A a x), comme pour la preuve PK (x, r : E = E (x,r ) n x b) , ce qui correspond à 12 + 1 + 2 pour la preuve globale PK8eäGre (x,r : E = E (x,r ) A a x b) au sens de Bellare et al, - contre 61û 2 pour le calcul de preuve PK;nvenl,(,n (x,r : E = E (x,r ) A a Bien entendu, la présente invention ne se limite pas à la forme de réalisation décrite ci-avant à titre d'exemple ; elle s'étend à d'autres variantes. Par exemple, on a décrit ci-avant une fonction d'engagement de la forme E (x, r) = gxh' mod n. Toutefois, la mise en oeuvre de l'invention admet des variantes possibles notamment quant à la fonction d'engagement qui peut être du type, par exemple, E(x2,r) = gx2 h' modn (ou E(x2,r) = gx2 h' modp en contexte de groupe connu). Plus généralement, l'invention trouve une application à tout protocole à divulgation nulle de connaissance, où un prouveur doit montrer qu'il connaît un secret dans un intervalle, en utilisant une décomposition binaire pour le calcul d'une preuve. REVENDICATIONS 1. Procédé de communication entre une première entité informatique et une deuxième entité informatique, pour une authentification sécurisée de la première entité auprès de la deuxième entité, dans lequel : la première entité (El) prouve à la deuxième entité (E2) qu'elle connaît un secret (x) dans un intervalle donné comportant une borne inférieure (a) et une borne supérieure (b), en mettant en oeuvre au moins les étapes de : - calcul d'un engagement (E) en fonction du secret, calcul d'une preuve (PK) de la connaissance du secret en utilisant une décomposition binaire au moins du secret et des bornes de l'intervalle donné, et - communication de l'engagement et de la preuve à la deuxième entité (E2), et la deuxième entité (E2) recalcule la preuve (PK) au moins en fonction de l'engagement (E) pour vérifier la preuve reçue de la première entité (El), caractérisé en ce que lesdites bornes inférieure et supérieure (a, b) sont connues de la première entité et de la deuxième entité, et en ce qu'un traitement préliminaire au calcul de la preuve est mis en oeuvre pour simplifier une expression de la preuve, ladite expression simplifiée de la preuve étant exempte de composantes (ai, bj) issues de la décomposition binaire desdites bornes. 2. Procédé selon la revendication 1, caractérisé en ce que la preuve (PK) s'exprime en fonction d'au moins une première liste (L) des suites possibles des composantes de la décomposition binaire du secret (x) en fonction des valeurs respectives des composantes de la décomposition binaire des bornes (a, b) de l'intervalle donné. 3. Procédé selon la revendication 2, dans lequel l'engagement comporte un produit : - d'un premier nombre g à la puissance d'un deuxième nombre x, et - d'un troisième nombre h à la puissance d'un quatrième nombre r, lesdits premier g et troisième h nombre étant des paramètres publics, 28le deuxième nombre x correspondant audit secret dans l'intervalle donné, et le quatrième nombre r étant un paramètre secret, caractérisé en ce que : * hormis le cas où toutes les composantes de la borne inférieure sont nulles et/ou toutes les composantes de la bornes supérieure valent 1, si une composante a; d'ordre i de la borne inférieure est nulle et si une composante b; de même ordre i de la borne supérieure vaut 1, ladite première liste (L) est donnée par (61) : L, :[(C, =hY)ALa,_,]v[(C, /g=hZ )ALh,_1], où : - un élément C; est défini par C, = gx hr , où x; est la composante d'ordre i de la décomposition binaire du secret x et r; est un aléa, - y; représente un élément r;, - le signe " n " désigne "ET" et le signe " v " désigne "OU-exclusif', - la notation L°désigne une liste obtenue par un premier sous-traitement donnant les suites possibles de valeurs de composantes du secret x en fonction des composantes a;_1, ar_2 , ..., ao de la borne inférieure a, et - la notation Lb, désigne une liste obtenue par un deuxième sous-traitement donnant les suites possibles de valeurs de composantes du secret x en fonction des composantes bi_2 , ..., bo de la borne supérieure b, * si une composante a; d'ordre i de la borne inférieure est nulle et si une composante b; de même ordre i de la borne supérieure est nulle, ladite première liste (L) est donnée par (55) : L, : (C, = hy ) n L ,_, , où L est une liste des suites possibles de valeurs de composantes du secret x en fonction des composantes ai_1, ar_2 , ..., ao de la borne inférieure a et/ou des composantes bi_1, b;_2 , ..., bo de la borne supérieure b, et * si une composante a, d'ordre i de la borne inférieure vaut 1 et si une composante b; de même ordre i de la borne supérieure vaut 1, ladite première liste (L) est donnée par (57) : L, :(C, /g=le )AL 4. Procédé selon la revendication 3, caractérisé en ce que :- la liste L°,_, issue du premier sous-traitement est donnée par (38, 40) : * L",_1 /g = hr'-') n L"J_2 si la composante a,_i = 1, et * _, : (C,_, / g = U-1) v [(C,_, = hr'-') n L°,_2 ] si la composante a,_, = 0, jusqu'à épuisement des composantes a,_,, a1_2, ..., ao, en considérant la liste La, comme équivalent à l'ensemble vide pour i = -1, et - la liste Lh,_, issue du deuxieme sous-traitement est donnée par (37, 39) : * (C,_, = hy-') n Lh,_2 si la composante h,_, = 0, et * Lh,_1 : (C,_, = h''-') v [(C,_, / g = hr'-') A Lh,_2 ] si la composante b,_, = 1, jusqu'à épuisement des composantes b,_,, b1_2, ..., bo, en considérant la liste Lh, comme équivalent à l'ensemble vide pour i = -1. 5. Procédé selon l'une des revendications 2 à 4, caractérisé en ce que la preuve (PK) s'exprime en outre en fonction d'une deuxième liste (L ), combinée par un "ET" à la première liste (L), et représentant, si une valeur de composante x, du secret a pu être déterminée en fonction de valeurs (a,, b,) de composantes des bornes de l'intervalle donné, toutes les possibilités de valeurs des composantes x,_,, x,_2, ..., xo d'ordres inférieurs à la composante x, dans la décomposition binaire du secret x. 6. Procédé selon la revendication 5, dans lequel l'engagement comporte un produit : - d'un premier nombre g à la puissance d'un deuxième nombre x, et - d'un troisième nombre h à la puissance d'un quatrième nombre r, lesdits premier g et troisième h nombre étant des paramètres publics, le deuxième nombre x correspondant audit secret dans l'intervalle donné, et le quatrième nombre r étant un paramètre secret, caractérisé en ce que la preuve est donnée par (73) : PK:[(C=gable )n(CC-' =hs)ALAL], où: - L désigne la première liste,L désigne la seconde liste, le signe " n " désigne "ET" et le signe " v " désigne "OU-exclusif', C est la valeur de l'engagement, 1-1 2' C est donné par C = eh = fi (C;) , avec C, = eh" , où un terme x; est la =o composante d'ordre i de la décomposition binaire du secret x et r, est un aléa, a représente le secret x, fi représente le quatrième nombre r, et 1-1 Ô représente la différence r ûF , où r = r,.2' . =o 7. Programme informatique, destiné à être stocké en mémoire d'une entité prouveuse (E 1), pour le calcul de preuve de la connaissance d'un secret dans un intervalle donné, caractérisé en ce qu'il comporte des instructions pour la mise en oeuvre du procédé selon l'une des revendications 1 à 6 lorsqu'elles sont exécutées par un processeur de l'entité prouveuse (E 1). 8. Programme informatique, destiné à être stocké en mémoire d'une entité vérificatrice (E2), pour recalculer la preuve de la connaissance d'un secret dans un intervalle donné en vue d'une vérification, caractérisé en ce qu'il comporte des instructions pour la mise en oeuvre du procédé selon l'une des revendications 1 à 6 lorsqu'elles sont exécutées par un processeur de l'entité vérificatrice (E2). 9. Entité prouveuse, destinée à communiquer avec une entité vérificatrice, pour prouver à l'entité vérificatrice la connaissance d'un secret dans un intervalle donné, notamment pour une authentification auprès de l'entité vérificatrice, l'entité prouveuse comportant des moyens pour : calculer un engagement (E) en fonction du secret, calculer une preuve (PK) de la connaissance du secret en utilisant une décomposition binaire au moins du secret et des bornes de l'intervalle donné, et communiquer l'engagement et la preuve à l'entité vérificatrice (E2),caractérisé en ce que, lesdites bornes inférieure et supérieure (a, b) étant connues de l'entité prouveuse et de l'entité vérificatrice, lesdits moyens pour calculer la preuve mettent en oeuvre un traitement préliminaire au calcul de la preuve pour simplifier une expression de la preuve, ladite expression simplifiée de la preuve étant exempte de composantes (a;, b;) issues de la décomposition binaire desdites bornes. 10. Entité vérificatrice, destinée à communiquer avec une entité prouveuse pour vérifier une preuve communiquée par l'entité prouveuse de la connaissance d'un secret dans un intervalle donné, l'entité vérificatrice comportant des moyens pour recalculer une preuve (PK) reçue de l'entité prouveuse au moins en fonction d'un engagement (E) reçu de l'entité prouveuse, pour vérifier ladite preuve reçue de l'entité prouveuse (E 1), caractérisé en ce que, lesdites bornes inférieure et supérieure (a, b) étant connues de l'entité prouveuse et de l'entité vérificatrice, lesdits moyens pour recalculer la preuve mettent en oeuvre un traitement préliminaire au calcul de la preuve pour simplifier une expression de la preuve, ladite expression simplifiée de la preuve étant exempte de composantes (a;, b;) issues de la décomposition binaire desdites bornes. 11. Système pour la mise en oeuvre du procédé selon l'une des revendications 1 à 6, caractérisé en ce qu'il comporte une entité prouveuse selon la revendication 9 et une entité vérificatrice selon la revendication 10.