1. Domaine technique de l'invention

L'invention appartient au domaine des systèmes de communication cryptographiques.

2. Etat de la technique antérieure

La cryptographie moderne repose en majorité sur des problèmes mathématiques très difficiles à résoudre dans l'état actuel des connaissance et des moyens de calcul, tels que par exemple la factorisation de grands nombres premiers, ou le calcul de logarithmes discrets, appartenant à la théorie de la complexité. Du fait qu'aucune certitude n'existe quant à la difficulté réelle de ces problèmes, pas même la fameuse conjecture P≠NP, d'autres méthodes ont été développées depuis le début des années 90. Ces méthodes s'appuient sur des hypothèses relatives à l'adversaire (comme « l'adversaire à mémoire limitée » [6]) ou relatives au canal de communication (comme les « canaux bruités indépendants » [5]) ; malheureusement, s'il a été montré que la confidentialité parfaite pouvait être atteinte pour ces méthodes sous certaines hypothèses données, aucune de ces hypothèses n'est facile à garantir en pratique. Enfin, d'autres méthodes, basées elles sur des théories physiques, telles que l'indétermination quantique [3] ou les systèmes dynamiques chaotiques ont été décrites et expérimentées, mais elles sont complexes à mettre en œuvre et, là encore, elles reposent sur des théories non prouvées.

Considérant cette situation théorique non satisfaisante, nous proposons une nouvelle méthode, grâce à laquelle la confidentialité parfaite peut être atteinte et prouvée, sans aucune hypothèse relative à l'adversaire, qui est supposé doté de capacités de calcul et de stockage de données illimitées, ni au canal de communication, qui est supposé parfaitement public et équivalent pour tous les participants (partenaires légitimes et adversaires). L'adversaire considéré est passif, ce qui veut dire qu'il n'interfère pas dans le protocole de communication entre les partenaires légitimes en ajoutant, modifiant ou supprimant des données aux informations échangées ; il a en revanche un accès total à ces informations. Les adversaires actifs peuvent également être considérés en ajoutant au protocole un schéma d'authentification des messages entre les partenaires légitimes.

Références

[1] C E. Shannon, « Communication theory of secrecy Systems », Bell Syst. Tech. J., Vol. 28, pp. 656-715, Oct. 1949

[2] A. N. Kolmogorov, « On Tables of Random Numbers », Sankhya. Indian Journal of Statistics A, 25(4) :369-376

[3] C. H. Bennet and G. Brassard, « Quantum cryptography and its application to provable secure key expansion, public-key distribution and coin-tossing », Proc. ΓΕΕΕ International Conférence on Computers, Systems and Signal Processing, Bangalore, India, pp. 175-179, Dec. 1984

[4] C. H. Bennet, G. Brassard and J.-M. Robert, « Privacy Amplification by Public Discussion », SIAM J. COMPUT., Vol. 17, No. 2, Apr. 1988

[5] U. M. Maurer, « Secret Key Agreement by Public Discussion from Common Information », ΓΕΕΕ Transactions on Information Theory, Vol. 39, No. 3, May 1993

[6] C. Cachin and U. M. Maurer, « Unconditional Security Against Memory- Bounded Àdversaries », Proceeding of CRYPTO '97, Lecture Notes in Computer Science, Springer, 1997

3. Exposé de l'invention

Nous considérons deux Entités Autonomes (EA), appelées correspondants EA légitimes, désirant communiquer sur un canal de communication public non sûr. Comme dans toute modélisation de protocole de communication, ces EA sont des entités capables de générer des séquences de bits aléatoires, de publier des séquences de bits, de lire des séquences de bits publiées par d'autres EA, de stocker des séquences de bits, d'effectuer des calculs sur des séquences de bits. La principale différence de notre procédé est que la génération aléatoire de séquences de bits inclut la génération de Hasard Profond. Le Hasard Profond est une source d'information numérique aléatoire telle qu'un observateur extérieur ne peut pas connaître la distribution de probabilité de la variable aléatoire associée à cette source d'information, à part un ensemble de caractéristiques publiques. De ce fait, de telles variables aléatoires par Hasard Profond ne sont pas sujettes à une évaluation par inférence bayesienne.

Une EA est constituée (Fig. 1) des 2 composants suivants :

• Le Générateur de Hasard Profond (GHP). Un GHP est capable de :

o Produire de manière continue de nouvelles distributions de probabilités, appelées distributions par Hasard Profond, dont les caractéristiques sont décrites ci-après

o Générer et stocker, sur requête d'un MCI autorisé, une information numérique aléatoire en utilisant ses distributions par Hasard Profond, ces informations devant rester secrètes pour assurer la confidentialité de la communication

o Réaliser, sur requête d'un MCI autorisé, des calculs sur les dites informations numériques aléatoires

• Le Module de Communication Interactive (MCI). Un MCI est capable de :

o Publier de l'information sur le canal de communication public (à l'attention du correspondant E A légitime)

o Lire de l'information sur le canal de communication o Exécuter un type particulier de protocole de communication appelé Protocole à Confidentialité Parfaite, dont les caractéristiques sont décrites ci-après

Les deux caractéristiques principales de la présente invention sont (i) la génération de distributions par Hasard Profond, et (ii) l'exécution de Protocole à Confidentialité Parfaite. Ils sont conçus (GHP et MCI) pour fonctionner ensemble, ce qui donne l'unicité de l'invention. Ils permettent d'obtenir une confidentialité parfaite sans besoin de distribution préalable d'une clé secrète et sans condition ou limitation sur le canal de communication ou sur les capacités de l'adversaire, ce qui donne l'utilité et le caractère innovant de l'invention. Ils peuvent être réalisés sous différentes formes, sachant qu'au moins une est décrite à la section 5 de la présente description ci-après, ce qui assure que l'invention peut faire l'objet d'application industrielle. De plus, l'inventeur a obtenu une preuve mathématique de la parfaite confidentialité, ce qui n'est pas le cas de la plupart des autres procédés de communication cryptographique brevetés précédamment ; toutefois, les détails de cette preuve mathématique sont complexes et ne sont pas présentés dans la présente description par souci de concision.

(i) Caractéristiques du Générateur de Hasard Profond :

Le Hasard Profond généré par une EA appelée A est une source de hasard telle que sa distribution de probabilité est inconnaissable (ou cachée) pour un ensemble donné d'EA appelées adversaires, chacune notée ξ. En pratique, cet ensemble d'EA est généralement toute EA autre que A. Plus généralement, la distribution de probabilité peut être cachée à part un ensemble de caractéristiques publiques / (on note £l _l l'ensemble des distributions de probabilité qui vérifient les caractéristiques /). De telles sources de hasard ont la propriété suivante :

Si X et Y sont deux variables aléatoires, et si X a une distribution de probabilité cachée pour ξ en dehors des caractéristiques /, alors :

Ε[φ(Χ) \Υ] _ξ ne dépend pas de la distribution de probabilité de X au sein de il;

où £'[φ(.Χ ^, ) | ν ^, ] désigne l'espérence conditionnelle de <p(X) à partir de la connaissance réduite à Y par ξ. φ étant une fonction déterministe quelconque.

Nous pouvons donner une formulation plus faible mais plus concrète de cette propriété, avec les variables engendrées. A titre de défintion, si V est une variable aléatoire à valeurs dans un ensemble E, une variable aléatoire V à valeurs dans l'ensemble F est dite engendrée par V s'il existe une distribution d'engendrement ψ E x F κ> [0,1] telle que Vx G E ,∑y _£ p ip(y, x)dy— 1 et correspondant à la distribution de probabilité de V :

La formulation affaiblie de la propriété est alors : soit Y une variable aléatoire à valeurs dans un ensemble F, engendrée par n'importe quelle variable aléatoire à valeur dans E par la même distribution d'engendrement xp: E x F ^ [0,1]· Si X et X' sont deux variables aléatoires à valeurs dans E dont les distributions de probabilité sont dans Ω _; chacune cachée pour ξ en dehors des caractéristiques /, alors :

Ε[φ(Χ) \Υ] _ξ = Ε[φ(Χ') \Υ] _ξ

m

Vu de 1ΈΑ pour qui la distribution de probabilité d'une variable aléatoire est cachée, la capacité d'estimation relative à cette variable est bien sûr plus limitée que pour une variable aléatoire traditionnelle dont la distribution est connue. Le concept de pondération des valeurs possibles est remplacé par le concept de simple existence de telles valeurs.

Il est important de comprendre que le fait d'affirmer que la distribution d'une variable aléatoire est inconnaissable pour une EA ne veut pas dire que cette distribution n'existe pas. Cela veut simplement dire qu'elle est cachée pour cette EA. Pour toute autre EA (connaissant la distribution), la variable aléatoire reste gouvernée par la théorie des probabilités traditionelle.

Il peut apparaître comme un non sens de vouloir générer du Hasard Profond à l'aide de ressources informatiques programmables. Dans le monde réel, même un ordinateur a accès à des sources de hasard dont les distributions de probabilité sont au moins partiellement inconnues, mais cela ne veut pas dire qu'il est possible d'obtenir du Hasard profond directement à partir de ces sources, utilisable pour une application de communication cryptographique.

3 méthodes existent pour générer programmatiquement du Hasard profond au sein d'une EA :

1) La programmation sécurisée : dans le cadre de cette méthode, le programme qui génère le Hasard Profond (GHP) est élaboré secrètement au sein d'un processus industriel isolé, et est gardé secret à toute EA extérieure. Pour les applications industrielles, le programme est embarqué dans un dispositif résistant à l'investigation, et ne peut être sollicité que pour fournir un signal de sortie généré de manière interne à l'aide dudit programme.

2) La génération récursive : dans le cadre de cette méthode, le programme de GHP exécute une suite récursive continue de génération, dans laquelle, à chaque étape m + 1, la distribution de probabilité est créée / sélectionnée pour mettre en échec la stratégie d'estimation optimale pour les distributions des étapes < m. Cette méthode peut être implémentée dans un programme qui s'exécute de manière continu au sein d'un environnement d'exécution, et qui puisse être sollicité à tout moment par ΕΑ pour fournir un signal aléatoire généré à l'aide d'un tirage aléatoire basé sur la valeur courante de la suite de distribution. Une telle implémentation peut être réalisée en logiciel ou en matériel pour améliorer la confidentialité de l'état courant de la suite. Pour qu'une telle méthode soit sure, l'entropie du signal aléatoire de sortie ne devrait pas être plus grande que l'entropie de la valeur de l'indice de la suite. Un exemple d'une telle méthode est donné à la section 5 de la présente description.

3) La combinaison : dans le cadre de cette méthode, différentes sources de Hasard Profond sont combinées. Ces sources peuvent provenir d'une EA externe collaborative, comme représenté en Fig. 3. Dans ce cas, un Protocole à Confidentialité Parfaite est utilisé pour échanger les paramètres de la distribution de probabilité, d'une ou plusieurs EA collaboratives de niveau 1 vers ΓΕΑ de niveau 2 considérée. Les méthodes de combinaison sont telles que si au moins une des sources est réellement du Hasard Profond, alors la résultante de la combinaison est encore du Hasard Profond, autrement dit que la distribution de probabilité obtenue reste cachée pour les adversaires.

Concernant la génération récursive, si un observateur ne connaît ni la date de démarrage ni la vitesse d'exécution d'un compteur incrémental infini, aucune distribution de probabilité ne peut estimer même approximativement la valeur courante du compteur à un instant donné, de part sa nature illimitée. De plus, s'il s'exécute dans un dispositif informatique, la vitesse réelle du compteur est impactée par des tâches et des événements externes au sein des processeurs, pour lesquels aucune distribution de probabilité fiable ne peut être utilisée ; la seule chose qu'un adversaire puisse faire est d'estimer une borne supérieure très approximative de la valeur du compteur et de sa vitesse.

(ii) Caractéristiques d'un Protocole de Confidentialité Parfaite :

Définissons d'abord notre modèle général de protocoles de communication.

Un protocole de communication est une procédure impliquant 2 correspondants EA légitimes 04 et β) ; qui peut être décomposée en un nombre fini d'étapes t ₁₍ ... , t _R telles que, à chaque étape r < R :

a) _: A et B génèrent respectivement une nouvelle information x _r et y _r (en utilisant potentiellement du hasard classique ou du Hasard Profond grâce à leur GHP comme représenté en Fig. 1 - interaction 100 & 101), impliquant potentiellement la connaissance respectivement de {Xm}i≤m<r _> {im m}i≤m<r, et {y _m } _1≤m<r , {t _m ,j _m )i< _m<r . Pour cela, le GHP peut être sollicité par le MCI comme représenté en Fig. 1 - interaction 101, et le MCI lit Tinformation publiée par l'autre partie lors de l'étape précédante comme représenté en Fig. 1 - interaction 103.

b) A et B publient respectivement une information t _r et j _r qui peut dépendre resptivement de {½)i< _m≤r , {'mJm}l≤7n<r> ^et { m}l≤? ≤ > {½Jm}l≤ _? n<r-

Pour cela, le MCI écrit l'information sur le canal public comme représenté en Fig. 1 - interaction 102.

A la dernière étape R, A et B réalisent uniquement des calculs basés sur la connaissance respective de {Xm)i≤m<K _> {im _> jm i≤m<R _> et {y _m }i {i _m , _Tn }i _<m < _/î - L'un des résultats de ces calculs (comme représenté en Fig. 1 - interaction 104) est une estimation de l'information secrète partagée. Ces estimations sont respectivement notées V _A et V _B .

{ _v ] _v est appelé un protocole configurable, avec v un vecteur de paramètres numériques fixé avant l'exécution du protocole, si la description de l'implémentation du protocole (incluant la capacité de générer du Hasard Profond) a une taille majorée par H (y) + K, où H représente la fonction d'entropie et K est une constante indépendante de v.

Les Protocoles à Confiddentialité Parfaite sont un type spécial de protocoles appartenant au modèle général décrit ci-dessus, pour lesquels, en supposant les hypothèses (H) et (//') présentées ci-avant vraies pour des signaux générés par des GHP, la stratégie de l'adversaire la plus efficace (espérence conditionnelle) pour estimer par exemple V _A est strictement moins performante que V _B (Distillation d'Avantage [4]). De tels protocoles incluent également des méthodes, déjà connues et largement étudiées dans la littérature publique, de Réconciliation et d'Amplification de Confidentialité [4] pour transformer ledit Avantage en une information secrète et partagée exclusivement entre les correspondants légitimes. Cette information secrète partagée, qui peut être d'une taille aussi longue que souhaité (par exemple par répétition du protocole), peut être utilisée pour échanger entre les correspondants légitimes de manière parfaitement sécurisée un message signifiant, soit directement (utilisation d'un masque jetable XOR) ou en échangeant une clé cryptographique symétrique, utilisable ensuite avec un système de chiffrement par bloc ou un système de chiffrement en continu.

De manière plus formelle, si l'on considère un protocole T, l 'ensemble total des informations aléatoires générées respectivement par A et B obéit à des distributions de probablité appartenant respectivement à des ensembles que l'on note ¾CP) et Ά _Β ( ). L 'usage du Hasard Profond permet de considérer, dépendant de T, plusieurs sous-ensembles de Q _A P) X &B(P)■' (Ηι · H ), ... tels qu 'ils contiennent seulement des distributions qui sont non distinguables les unes des autres pour l'adversaire. Ces sous-ensembles sont supposés être maximaux (parceque sinon on peut les compléter). On peut considérer le groupe des transformations réversibles {/im(s)} _m (supposé être dénombrable) de & _A P) x Ά _Β (Τ) >→ Q _A P) X Q _B (P). qui laisse (β^, Ηξ) stable. Chacune de ces transformations induit également une transformation réversible m _m (s dans l'ensemble des stratégies possibles de l 'adversaire = Ωρ. On note alors Ωφ(β) le sous-ensemble de Ωγ qui contient les stratégies invariantes par l 'action du groupe induit vs _m {s) } _m . Les hypothèses du Hasard Profond (H) et (Η') permet alors de restreindre le choix de la stratégie de l 'adversaire à un élément quelconque du sous-ensemble i¾>(s).

On note Η _Ρ ε, ε') la quantité minimale d'information (nombre de bits) devant être échangée à travers T pour obtenir : ^■

(i) d _h (V _A , V _B )≤ EH(V _B )

(ii) inf _s (su _{Pcùesl s)} E'H(V _B )

où d _h désigne la distance de Hamming, et H(-) désigne l'entropie de Shannon [1]. Si les 2 conditions ci-dessus ne peuvent pas être satisfaites, alors Η _Ρ (ε, ε') =∞. Un protocole configurable {Ρ _υ } _υ est appelé un Protocole à Confidentialité Parfaite si, νε, ε' > 0, il existe ν(ε, ε') sous les hypothèses du Hasard Profond (H) et (W), tel que :

Η _Ρν ε, ε') <∞

Les trois caractéristiques minimales d'un Protocole à Confidentialité Parfaite :

1) Le Hasard Profond (HP) : Les 2 correspondants légitimes impliqués dans le protocole font usage du Hasard Profond

2) La Dégradation : Pour chacun des 2 correspondants légitimes impliqués dans le protocole, l'information qu'il publie est au moins partiellement dégradée à partir du signal de sortie généré par son GHP. Cela signifie que l'information publiée est le résultat d'une variable aléatoire engendrée à partir dudit signal de sortie généré par le GHP, telle que la précision du signal de sortie de ladite variable engendrée est rendue strictement plus faible (à travers ce processus de Dégradation) que la précision du signal de sortie généré par le

GHP.

3) La Distillation d'Avantage sous les hypothèses du Hasard Profond ((H) et (H')) : Sous les hypothèses (H) et (Η'), aucune stratégie de l'adversaire ne peut être considérée plus efficace qu'au moins une autre stratégie appartenant à un ensemble donné Ω, appelé sous-ensemble de restriction pour le protocole ; et pour toute stratégie de Ω adoptée par l'adversaire, l'estimation de l'information secrète partagée donnée par ladite stratégie est strictement moins précise que les estimations des correspondants légitimes.

Pour illustrer le phénomène de Dégradation, donnons un exemple simple : considérons une EA observant une épreuve d'une variable aléatoire binaire V de paramètre Θ 6 [0,1]· Si l 'EA veut générer une nouvelle variable aléatoire binaire basée sur le résultat de l'épreuve, elle peut uniquement affecter des paramètres [θ ₀ , dépendant du résultat binaire {0,1} de l'épreuve de V. Le paramètre de cette nouvelle variable aléatoire binaire V est alors :

0„ + («, - θ ₀ )ΰ

Si maintenant on remplace Θ par θ/k où k est un nombre > 1 ; est alors impossible d'engendrer à partir de V une nouvelle variable aléatoire binaire de paramètre Θ (parce que \θ-ι— θ ₀ \ < 1). L 'EA qui observe peut bien sûr multiplier le résultat par k (engendrant ainsi une variable à valeur cette fois dans {0, k] au lieu de {0,1},), pour obtenir une variable engendrée avec la même moyenne (moment d'ordre 1) que V, mais alors la variance (moment d'ordre 2, représentant la précision) de cette variable engendrée est strictement plus élevée que celle de V, autrement dit sa précision est strictement plus faible. L ΈΑ doit donc «faire un choix » entre moment d'ordre 1 et moment d'o dre 2, mais ne peut pas égaler les deux moments dans une même variable engendrée.

Un exemple de Protocole à Confidentialité Parfaire est donné dans la section 5 de la présente description, comme mode de réalisation spécifique pour cette invention.

4. Brève présentation des dessins

La Fig. 1 montre le modèle général d'un Protocole à Confidentialité Parfaite basé sur le Hasard Profond, dans lequel chaque EA impliquée dans le protocole (désignées par A et β), dispose d'un GHP fonctionnant en continu, et d'un MCI. Les MCI de A et de B sont connectés par un canal de communication public, sans erreur, sur lequel une EA (dite « adversaire ») est supposée avoir un accès total en lecture.

La Fig. 2 montre le mode de réalisation spécifique d'un Protocole à Confidentialité Parfaire basé sur le Hasard Profond (correspondant à la section 5) avec les interactions successives exécutées entre les EA impliquées dans le protocole (désignées par A et B). Chacune de ces interactions est décrite dans la section 5.

La Fig. 3 montre un modèle de collaboration entre 2 Générateurs de Hasard Profond, dans lequel une ou plusieurs EA de niveau 1 (désignées par A. x, A. y) peuvent transmettre de manière sécurisée les paramètres de leur distribution de probablité à Hasard Profond à une EA de niveau 2 (désignée par B). B peut alors combiner ces sources potentiellement ensemble et / ou avec les siennes propres, pour générer de nouvelles sources de Hasard Profond.

La Fig 4. montre un Générateur de Hasard Profond fonctionant avec la méthode de génération continue récursive, schématisé sous la forme d'un diagramme de blocs. Le GHP est implémenté dans un environnement physique résistant aux intrusions informatiques ou électromagnétiques et est logiquement constitué de 4 sous- modules : le Générateur Récursif Interne de Hasard Profond (GRIHP), le Générateur Interne de Hasard Standard, la Mémoire Interne, et l'Interface de Communication, qui est le seul des 4 sous-modules à pouvoir communiquer avec l'environnement extérieur.

5. Description d'un mode de réalisation spécifique i) Description d'un mode de réalisation spécifique d'un Générateur de Hasard Profond

Le mode de réalisation spécifique présenté dans cette section correspond à avec la méthode de génération continue récursive, comme décrit dans la section 3. (i) 2), associée à une méthode par combinaison, comme décrit dans la section 3. (i) 3). Il peut être implémenté sous forme logicielle ou dans un dispositif matériel résistant aux intrusions informatiques ou électromagnétiques.

La Fig 4. montre un Générateur de Hasard Profond fonctionant avec la méthode de génération continue récursive, schématisé sous la forme d'un diagramme de blocs. Le GHP est logiquement constitué de 4 sous-modules :

• le Générateur Récursif Interne de Hasard Profond (GRIHP), qui produit [Fig4-400] une suite continue et récursive de distributions de probabilité et est capable de mettre à disposition, sur sollicitation de l'Interface de Communication [Fig4-420] une épreuve obtenue à partir de la valeur courante de la suite de distributions de probabilité

• le Générateur Interne de Hasard Standard, qui produit et met à disposition sur sollicitation de l'Interface de Communication [Fig4-430] une épreuve à partir d'une distribution de probabilité connue ; cette distribution de probablité peut nécessiter un paramètre d'entrée tel que par exemple le signal de sortie du GRIHP (auquel cas il génère une variable aléatoire engendrée par la distribution de probablité à Hasard Profond)

• l'Interface de Communication, qui permet de recevoir un ordre d'un MCI associé au GHP, et de donner un signal de sortie en retour [Fig4-410, 411, 412]

· la Mémoire Interne, qui permet à l'Interface de Communication de stocker, retrouver ou effacer [Fig4-440, 441, 442] un signal de sortie du GRIHP.

Dans la suite de cette section 5.i), on présente plus particulièrement un exemple de GRIHP.

On définit les notations suivantes; considérant x— (x _lt ... , x _n ) et y = (y ₁₍ ... , y _n ) des vecteurs de paramètres de [0,l] ⁿ et i— ... , i _n ) et = (Ji, - ,jn) des vecteurs d'épreuve de {0,l} ⁿ , l,r £ deux entiers, et Θ G [0,1], on définit :

x. y (resp. i.j) le produit scalaire de x et y (resp. i et j)

On manipulera également des opérateurs de permutation sur les vecteurs. Pour σ G S _n , on écrit supp(a) = ker(cr— id _Sn ) = {i, σ(ί)≠ i] et |σ| = card(supp(a)). La permutation de vecteur correspond à l'application linéaire suivante :

\ σ G Q _n , σ(χ) = (* _{σ ΐ)} , ... , χ _σ(η) ) où Q _n représente le groupe symétrique

Φ, Φ _τη désignent des distributions de probabilité à valeurs dans [0,1] ^η · Pour une telle distribution Φ, Φ ° σ désigne une autre distribution à valeurs dans [0,l] ⁿ telle que :

Probtp aCx = Prob _< t _> (a ¹ ( )) La matrice quadratique d'une telle distribution Φ est :

Μ _Λ ^χ _η ^χ _ν Φ(χ)άχ

S _n désigne l'ensemble des sous-ensembles / de {1, ...,n] de taille n/2 ; on définit Il ^■ Il _c , appelée la norme-c, par :

V/ G 5 _η ,ί;(Μ _φ ) = Τ ^M <t>( ^u > ^v ; ||Μ _φ || _ε = max| _C/ (M )|

η ^Δ L-i _ i€S _n

u.v&lxl

A chaque distribution de matrice quadratique Μ _φ est associée la matrice _φ définie par : Φ Η→¾ =™ _Φ |: joùm _φ =~—^∑ _u≠v M(u,v) On notera dans la suite :

< _ω ,Φ,Φ')^[( _ωυ -¾ ² ] _φφ , <ω,Φ> ê, (ω,Φ,Φ)

où ω désigne toute stratégie de l'adversaire, dépendant des informations publiques i,j (cet ensemble de stratégies possibles est noté Ω), pour estimer le plus précisément possible la quantité i,j sont des vecteurs d'épreuves de {0,l} ⁿ générés par une distribution de Bernoulli à x y

partir respectivément des vecteurs de paramètres La transformation (x, y) ·→ (-,-) est la Dégradation (comme introduite au 3.(ii)) utilisée pour le présent mode de réalisation, à la fois pour le GHP et le Protocole à Confidentialité Parfaite décrit ci- après en section 5.ii).

Enfin, on note :

Protocole à Confidentialité Parfaire présenté ci-après, ((a) correspond à l'ensemble des distributions qui sont « loin » d'être symétriques. Seules de telles distributions peuvent être considérées dans le Protocole à Confidentialité Parfaite présenté ci- après pour être capable d'assurer l'efficacité de l'étape de Synchronisation (Etape 4).

Ayant défini ces notations, il est maintenant possible de décrire précisément le processus de construction de la suite récursive de distributions {Φ[ρ]τη}ρε¾,ηι _ε Ν exécuté par le GRIHP du GHP objet du présent mode de réalisation de GHP, appelé dans la suite GHP(iV, n, k) :

Processus de Génération Récursive Unitaire :

L'ensemble des matrices quadratiques de distributions possibles (en supposant Φ restreinte à l'ensemble des distributions à valeurs dans {0,l} ⁿ ) est l'enveloppe convexe de toutes les matrices de l'ensemble :

{a(S _r ) \a e e _n) r e M _n }

{1 si 1 * 7" 6t V < T

„ . qui correspond à la matrice quadratique de la

0 sinon

distribution de Dirac pour le vecteur {1, l _r , 0, ... ,0}.

Il est facile de calculer que, pour tout r pas trop proche de 0 ou 1 :

et donc de déterminer si une distribution de Dirac δ _χ e ζ(α).

L'amorce initiale Φ ₀ du processus est choisie parmi tout sous-ensemble prédéfini de ζ(α) qui puisse être parcouru algorithmiquement. Dans le présent mode de réalisation, on considère par exemple le sous-ensemble des combinaisons linéaires convexes des distributions qui restent dans ζ μ). σ. = Id _Sn Φι = Φο ° ^σ ι

to _m réalise le minium :

où { _m<s } ^ est appelée fonction caractéristique du GHP, qui vérifie À _{m s} > 0, et

∑m T _ Λ .

s=l Λπι,ε ~ ^± ' Ψ est choisie au hasard dans le sous-ensemble initial, et il peut être prouvé (les détails sont complexes et ne sont pas présentés dans cette description) qu'il est possible de choisir _m+1 telle que :

<ώ _ιη , ψ ο σ _τιι+1 > >

n

On détermine alors _m+1 par :

cû _m et o _m+1 peuvent être ainsi déterminés (en utilisant également du hasard classique pour Ψ et o _m+1 ) à chaque étape par le GRIHP.

On peut également utiliser une méthode pour combiner les distributions dans ζ(α) : Processus de Combinaison Interne :

On commence par sélectionner Ψ dans ζ( ), et un ensemble {Ψ ₅ } _ΪΕ {Ι,...,Ν} de distributions « à combiner », toutes également dans ζ(α). Soit a _s une permutation telle que Δ ₀ (Ψ, Ψ ₅ o a _s )≥ (^— < (^j , il peut être prouvé (les détails sont complexes et ne sont pas présentés dans cette description) qu'une telle permutation existe toujours. De ce fait,

et la distribution combinée est alors : Φ— ∑^ ₌₁ Ψ ₅ ° r _s . L'association du Processus de Génération Récursive Unitaire et du Processus de Combinaison Interne présentés plus haut donne la description suivante du GRIHP de GHP(N, n, k) (comme représenté en [Fig4-400]) :

L'EA exécute un processus de génération continu et récursif dans lequel N suites continues {Φ[ρ]τη}ρερ¾,77ΐεΝ progressent en parallèle en suivant chacune un Processus de Génération Récursive Unitaire tel que présenté ci-dessus. Il peut également être décidé (sur décision aléatoire) de mettre à jour la valeur courante d'une suite donnée par une combinaison des valeurs courantes des suites en utilisant le Processus de Combinaison Interne tel que présenté ci-dessus. La qualité du Hasard Profond dépend de la- variété du sous-ensemble initial ainsi que du nombre grandissant d'itérations exécutés sur chaque suite. Le GRIHP devrait exécuter au moins n x N itérations avant de commencer à recevoir des requêtes d'un MCI. N devrait être approximativement de l'ordre de ln(n!)~nln(n), qui représente l'entropie nécessaire pour encoder un élément de l'ensemble des permutations S _n . Au moment où un MCI sollicite la sélection d'une distribution auprès du GHP (comme représenté en [Fig4-410]), un traitement supplémentaire est réalisé pour la sélection de la distribution par l'Interface de Communication (comme représenté en [Fig4-420]) : l'Interface de Communication choisit aléatoirement ([Fig4-430]) un entier c parmi {1, ... , N] ; la probabilité de choisir c est de N /c(c + l)(iV + 1) ; de telle manière qu'ainsi la distribution de probabilité de 1/c est équirépartie sur [0,1]. L'EA sélectionne ensuite aléatoirement c suites parmi N ([Fig4-430]) et établit sa distribution

Φ comme la combinaison linéaire ^~ ∑r=i Φ[ τ·]ηι _Γ ( _£ ) ; ^ou t désigne l'instant d'exécution du processus, [p ₁ , ... , p _r ] désignent les indices des c suites sélectionnées, m _r (t) désigne la valeur courante du compteur de la suite Φ [ρ _Γ ] à l'instant de l'exécution. La justification de ce traitement supplémentaire est que la distribution finalement choisie doit appartenir à un ensemble quasi convexe, et donc doit aussi avoir son paramètre-a dans un segment convexe. En effet, l'étape de Dispersion (Etape 2) du Protocole à

Confidentialité Parfaite présenté ci-après utilise la transformation convexe Φ >→ i

- (Φ + Ψ), et cette transformation diminue la valeur du paramètre-a ; de manière générale une transformation linéaire convexe avec c distributions sommées diminue la valeur du paramètre-α d'une constante multiplicative de l'ordre de 1/c. Bien sûr, même si ce processus permet alors de pouvoir appliquer de manière effective les hypothèses (H) et ( /') présentée dans l'exposé de l'invention, le prix à payer est qu'il introduit l'apparition d'occurrences à faible probablité pour lesquelles l'adversaire peut estimer efficacement l'information secrète partagée avec la stratégie séparable ω = -^j^ car, en diminuant la valeur du paramètre-a, on obtient une distribution qui se rapproche d'une distribution symétrique. Ces occurrences à faible probabilité correspondent donc aux cas de plus grandes valeurs de c, ce qui correspond également aux plus faibles valeurs du paramètre-a.

Enfin, la distribution choisie Φ est également transformée (toujours dans le cadre de l'interaction [Fig4-420]) par une transformation dite de « lissage permutatif » :

où y, appelé noyau de lissage permutatif, est une fonction de → [0,1] (remarquez qu'il est impossible que \σ\ = 1 et donc la composante d'indice 1 peut être ignorée) qui vérifie :

Cette transformation finale est nécessaire pour « adoucir » les distributions de Dirac, et éviter des biais spécifiques à certaines distributions à variation trop rapide (les détails techniques sont trop complexes pour être présentés dans cette description). Le noyau de lissage permutatif y est choisi comme un paramètre fixe du GHP. Sans rentrer dans la justification théorique complète qui dépasse le cadre de cette description, l'explication du choix de conception du Processus de Génération Récursive Unitaire dans le cadre du mode de réalisation spécifique GHP(N, n, k) est la suivante :

Avec un compteur inifïni s'incrémentant de manière isolée et sécurisée au sein du GRIHP, les instants m et m + 1 sont non distinguables pour l'adversaire ξ. Si un ensemble H _m de stratégies permettant une estimation précise de l'information secrète partagée existait à l'instant m our ξ , alors pour toute distribution Φ :

et donc, en choisissant à l'instant m + 1 la distribution ,η+ι telle que :

(ce qui est toujours possible comme expliqué ci-avant) ΓΕΑ guarantit que, pourvu que ^ « C, aucune stratégie absolue n'existe pour estimer de manière précise à tout x y .

instant l'information secrète partagée -^, car les instants d'observation ne peuvent être distingués par l'adversaire comme étant plutôt m ou m + 1.

x j i y

Et d'autre part, en notant V _A — V _B — où x, y correspondraient à des épreuves indépendantes suivant la même distribution peut calculer que :

Ce processus génère donc en effet du Hasard Profond car, sinon, l'adversaire serait

. x y capable par inférence bayesienne d'estimer l'information secrète partagée -j— à partir des informations publiques i,j avec une précision égale ou supérieure à celle de V _A ou de V _B .

ii) Description d'un mode de réalisation spécifique de Protocole à Confidentialité Parfaite

La Fig 2. montre un mode de réalisation spécifique d'un Protocole à Confidentialité Parfaite noté Ρ(λ, Θ, Ν, n, k) à l'aide d'un diagramme de blocs, où (A, θ, N, n, k) sont des paramètres publics du protocole, dont les correspondants légitimes sont notés A et fi. A et B sont deux EA équipées chacune d'un GHP et d'un MCI. Les 2 MCI sont connectés par un canal de communication public et sans erreur, de telle manière que A et B peuvent publier de l'information sur le canal et y lire de l'information publiée par l'autre partie.

5 Les étapes du protocole Τ(λ, θ, N, n, k) sont les suivantes :

Etape 1 - Génération de Hasard Profond :

A et B exécutent chacun de manière indépendante un processus de génération continue et récursive de distributions de probabilité à Hasard Profond [Fig2-200] en utilisant typiquement un générateur GHP(N, n, k) tel que décrit ci-avant dans la

10 sous-section 5.i). A et B désirent entrer en communication sécurisée et démarrent le protocole en choisissant chacun de manière indépendante une distribution de probabilité, respectivement Φ et Φ' en sollicitant leur GHP( , n, /c) comme représenté en [Fig2-210&211&213&214, Fig4-410&420]. Le résultat de cette étape est que A (resp. B) génère aléatoirement le vecteur de paramètre x ₀ G [0,1]" à partir

15 de Φ (resp. y ₀ £ [0,1]" à partir de Φ'), et stocke x ₀ (resp. y ₀ ) dans la mémoire interne de son GHP comme représenté en [Fig4-440].

Etape 2 - Dispersion :

A choisit également une seconde distribution Ψ toujours en solliciatnt son GHP(N, n, k) comme représenté en [Fig2-210&211&213&214]. Ψ est utilisée pour

20 « brouiller » les épreuves répétées à partir de Φ. A sollicite encore son GHP(N, n, k) pour générer aléatoirement N vecteurs de paramètres {x _lr ... , x _N } G {[0,l] ⁿ } ^w à partir de la distribution combinée ^ (Φ + Ψ). B génère aléatoirement N vecteurs de paramètres {y _ll ... , y _N ) G {[0,1]"}^ à partir de Φ'. A (resp. B) stocke {χ _ΐΊ ...; Χ _Ν } (resp. {y ₁ , ... , yw}) dans la mémoire interne de son GHP comme représenté en [Fig4-

25 440].

Etape 3 - Dégradation :

A génère N + 1 vecteurs d'épreuves de Bernoulli {i ₀ , ... , i _N ]€ {{0,l} ⁿ } ^N+1 respectivement à partir des vecteurs de paramètres —z ~j~j comme représenté en

[Fig2-210&211, Fig4-430&441]. A publie {i _0l ... , i _N } comme représenté en [Fig2- 30 220].

Etape 4 - Synchronisation :

B lit {i ₀ , ... , i _N } sur le canal public comme représenté en [Fig2-221] et calcule une permutation de synchronisation σ _β = σ _β [{ί ₅ } ^* , { _s } ^* ] _s6M ^ G S _n qui satisfasse la condition : puis génère un vecteur d'épreuves de Bernoulli j ₀ G {0,l} ⁿ à partir de— ^ ² -. B publie y ^' ₀ comme représenté en [Fig2-230&231&232&240].

Etape 5 - Distillation d'Avantage :

A lit o sur la canal public comme représenté en [Fig2-241] et calcule V _A = comme représenté en [Fig2-253&254&255, Fig4-412&441&442], B calcule V _B = ^ comme représenté en [Fig2-250&251&252, Fig4-412&441&442]

Etape 6 - Réconciliation et Amplification de Confidentialité :

Enfin, un processus classique de Réconciliation et d'Amplification de Confidentialité [4] permet d'obtenir à la fois une précision aussi proche que souhaité de la perfection pour les correspondants légitimes, et une connaissance de l'information secrète aussi proche que souhaité du néant pour tout adversaire doté de puissances de calcul et de stockage illimitées.

Il peut être prouvé (les détails sont complexes et ne sont pas présentés dans cette description) qu'un choix approprié des paramètres (λ, θ, N, n, k) permet de rendre possible les étapes 4 et 6 sous les hyporthèses du Hasard Profond (H) et (//'), ce qui constitue le cœur de la présente invention. Nous donnons toutefois maintenant quelques explications. L'utilisation du Hasard Profond telle que décrite aux étapes 1 et 2 permet de restreindre l'ensemble des stratégies de l'adversaire comme suit : · L'étape de Dispersion du protocole permet de restreindre une première fois l'ensemble des stratégies de l'adversaire aux stratégies ( j _0i i ₀ ne dépendant que des informations publiques j ₀ , i _Q

• L'étape de Synchronisation conduit à restreindre une seconde fois l'ensemble des stratégies de l'adversaire à l'ensemble des stratégies telles que ω _έ = ω _σ( ; _σ( ; , Va G Q _n , autrement dit l'ensemble des stratégies invariantes par permutation commune sur i ₀ ,; ₀ .

Ces deux restrictions conduisant finalement à l'ensemble des stratégies restreint Ω _# : Ω _# = [ω G [0,1] ^22η ; = Vf N _n ³ [0,1]}

L'étape 4 est nécessaire pour garantir que l'adversaire ne peut pas tirer avantage de l'indépendance entre les processus de sélection de Φ et Φ' par A et B, ce qui pourrait lui permettre d'estimer efficacement ^ en utilisant la stratégie séparable ^fc ^°^ ^Jo ^.

Grâce à l'étape de synchronisation, une telle stratégie devient inefficace, du fait de la nature de l'amorce initiale Φ ₀ utilisée dans le GHP(iV, n, k). Les tirages aléatoires répétés à partir de Φ sont utilisés pour « synchroniser » Φ et Φ', mais ne peuvent pas être utilisés par l'adversaire ξ pour obtenir une connaissance accrue de la distribution Φ. C'est le rôle de l'étape de Dispersion 3.

Il est important de remarquer que le calcul de la permutation de synchronisation ^σ Β — < _¾ [0 _s } ^* > {)¾} ^* ] à l'étape 4 ne dépend que des indices s £ N _N ^* , donc excluant 0. En effet, le choix de σ _Β doit demeurer indépendant de i ₀ , de telle sorte que i ₀ et j ₀ demeurent des épreuves indépendantes de variables de Bernoulli, permettant ainsi d'appliquer la majoration (E) pour les correspondants légitimes.

L'explication pour ce mode de réalisation spécifique est la suivante : il peut être prouvé que (les détails sont complexes et ne sont pas présentés dans cette description), quelle que soit la stratégie de l'adversaire ω dans l'ensemble restreint Ω ₍₍ :

où C' est une constante. Et d'autre part, on a toujours :

et donc, pourvu que - « C', une Distillation d'Avantage est obtenue à l'étape 5.

Il est également obtenu par l'analyse théorique du protocole que N doit encore être de l'ordre de ln(n!)~nln(n), pour avoir une probabilité satisfaisante de satisfaire à la consdition de synchronisation de l'étape 4 avec le choix σ _Β .

6. Applications industrielles

Une réalisation industrielle d'un Protocole à Confidentialité Parfaite permet à deux entités communiquant au travers d'un canal de communication non sûr, de générer une information secrète partagée. Cette information, qui peut être d'une longueur en bits aussi grande que souhaité (en répétant par exemple le protocole de manière séquentielle) peut être utilisée soit pour échanger directement de manière parfaitement sure un message signifiant entre les correspondants légitimes, (en utilisant l'information secrète comme masque jetable combinée par XOR au message signifiant), soit pour échanger une clé de chiffrement partagée utilisable avec un algorithme de chiffrement par blocs ou un algorithme de chiffrement en continu.

Elle peut donc être utilisée pour sécuriser des communications très sensibles, pour lesquelles des méthodes cryptographiques dont la sécurité n'est pas prouvée, ou n'est pas résistante à un adversaire doté d'une puissance de calcul importante, peuvent apparaître comme insuffisantes. Elle permet également de s'affranchir des processus non automatisés de distribution de clés partagées dans les équipements de communication sécurisée ; ces processus étant difficiles à mettre en œuvre, coûteux et susceptibles de failles de sécurité.

Une telle réalisation peut être faite sous forme de programme ou de librairie logiciels, pouvant être embarqués dans des équipement de communication ou intégrés dans des applications Γ. Elle peut également être faite sous forme d'un équipement de communication spécialement protégé, conçu pour être déployé en coupure, résistant aux intrusions informatiques et électromagnétiques.