Permutation pseudo-aléatoire - Pseudorandom permutation

En cryptographie , une permutation pseudo - aléatoire (PRP) est une fonction qui ne peut être distinguée d'une permutation aléatoire (c'est-à-dire une permutation choisie au hasard avec une probabilité uniforme, dans la famille de toutes les permutations sur le domaine de la fonction) avec un effort pratique.

Définition

Soit F une application . F est un PRP si et seulement si ${\displaystyle \left\{0,1\right\}^{n}\times \left\{0,1\right\}^{s}\rightarrow \left\{0,1\right\}^{ n}}$

• Pour tout , F est une bijection de à .${\displaystyle K\in \left\{0,1\right\}^{s}}$${\displaystyle \left\{0,1\right\}^{n}}$${\displaystyle \left\{0,1\right\}^{n}}$
• Pour tout , il existe un algorithme "efficace" à évaluer pour tout ,.${\displaystyle K\in \left\{0,1\right\}^{s}}$${\style d'affichage F_{K}(x)}$${\displaystyle x\in \left\{0,1\right\}^{n}}$
• Pour tous les distinguateurs probabilistes en temps polynomial : , où est choisi uniformément au hasard et est choisi uniformément au hasard à partir de l'ensemble des permutations sur les chaînes de n bits.${\style d'affichage D}$${\displaystyle \left|Pr\left(D^{F_{K}}(1^{n})=1\right)-Pr\left(D^{f_{n}}(1^{n}) =1\right)\right|<\varepsilon (s)}$${\displaystyle K\in \left\{0,1\right\}^{s}}$${\style d'affichage f_{n}}$

Une famille de permutations pseudo-aléatoires est une collection de permutations pseudo-aléatoires, où une permutation spécifique peut être choisie à l'aide d'une clé.

Le modèle de chiffrement par bloc

L'abstraction idéalisée d'un chiffrement par bloc (à clé) est une permutation vraiment aléatoire sur les mappages entre le texte en clair et le texte chiffré. S'il existe un algorithme distinctif qui obtient un avantage significatif avec moins d'effort que spécifié par le paramètre de sécurité du chiffrement par bloc (cela signifie généralement que l'effort requis doit être à peu près le même qu'une recherche par force brute dans l'espace de clé du chiffrement), alors le chiffrement est considéré comme cassé au moins dans un sens de certification, même si une telle rupture ne conduit pas immédiatement à une défaillance pratique de la sécurité .

On s'attend à ce que les chiffrements modernes aient un super pseudo-aléatoire. C'est-à-dire que le chiffre doit être indiscernable d'une permutation choisie au hasard sur le même espace de message, même si l'adversaire a un accès de boîte noire aux directions avant et inverse du chiffre.

Connexions avec fonction pseudo-aléatoire

Michael Luby et Charles Rackoff ont montré qu'une permutation pseudo-aléatoire "forte" peut être construite à partir d'une fonction pseudo - aléatoire en utilisant une construction Luby-Rackoff qui est construite en utilisant un chiffrement de Feistel .

Concepts associés

Permutation imprévisible

Une permutation imprévisible ( UP ) F _k est une permutation dont les valeurs ne peuvent être prédites par un algorithme randomisé rapide . Des permutations imprévisibles peuvent être utilisées comme primitive cryptographique , un bloc de construction pour les systèmes cryptographiques avec des propriétés plus complexes.

Un adversaire pour une permutation imprévisible est défini comme un algorithme qui a accès à un oracle pour les opérations de permutation directe et inverse. L'adversaire reçoit une entrée de défi k et est invité à prédire la valeur de F _k . Il est permis de faire une série de requêtes à l'oracle pour l'aider à faire cette prédiction, mais n'est pas autorisé à interroger la valeur de k elle-même.

Un algorithme aléatoire pour générer des permutations génère une permutation imprévisible si ses sorties sont des permutations sur un ensemble d'éléments (décrites par des chaînes binaires de longueur n ) qui ne peuvent pas être prédites avec une précision significativement meilleure que aléatoire par un adversaire qui fait un polynôme (en n ) nombre de requêtes à l'oracle avant le tour de défi, dont le temps d'exécution est polynomial en n , et dont la probabilité d'erreur est inférieure à 1/2 pour toutes les instances. C'est-à-dire qu'il ne peut pas être prédit dans la classe de complexité PP , relativisée par l'oracle pour la permutation.

Propriétés des permutations imprévisibles

On peut montrer qu'une fonction F _k est pas sécurisé code d'authentification de message (MAC) si elle ne satisfait que l'exigence d'imprévisibilité. On peut également montrer qu'on ne peut pas construire un MAC à longueur d'entrée variable efficace à partir d'un chiffrement par bloc qui est modélisé comme un UP de n bits. Il a été montré que la sortie d'une construction de Feistel ronde k  =  n / ω (log  λ ) avec des fonctions d'arrondi imprévisibles peut laisser échapper toutes les valeurs d'arrondi intermédiaires. Même pour des fonctions imprévisibles (UF) réalistes, certaines informations partielles sur les valeurs d'arrondi intermédiaires peuvent être divulguées via la sortie. Il a été montré plus tard que si un nombre super-logarithmique de tours dans la construction de Feistel est utilisé, la construction UP résultante est sécurisée même si l'adversaire obtient toutes les valeurs de tours intermédiaires avec la sortie de permutation.

Il y a aussi un théorème qui a fait ses preuves à cet égard qui stipule que s'il existe un adversaire UP efficace A _π qui a l' avantage non négligeable e _π dans le jeu de l' imprévisibilité contre la construction UP ψ _{U, k} et qui fait un nombre polynôme de requêtes au challenger, alors il existe également un UF adversaire A _f qui a un avantage non négligeable dans le jeu d'imprévisibilité contre un UF échantillonné dans la famille UF  F . De ce fait , il peut être montré que le maximum d' avantages de l'adversaire UP A _π est - ε _π = O ( ε _{f .} ( Qk ) ⁶ ). Ici ε _f désigne l'avantage maximal d'un adversaire UF courant dans le temps O( t + ( qk ) ⁵ ) par rapport à un UF échantillonné à partir de F , où t est le temps d'exécution de l'adversaire PRP A _ψ et q est le nombre de requêtes effectuées par cela.

De plus, un schéma de signature qui satisfait la propriété d'imprévisibilité et pas nécessairement de pseudo-aléatoire est essentiellement une fonction vérifiable imprévisible (VUF). Une fonction vérifiable imprévisible est définie de manière analogue à une fonction pseudo-aléatoire vérifiable (VRF), mais le pseudo-aléatoire est remplacé par une imprévisibilité plus faible. Les permutations imprévisibles vérifiables sont les analogues de permutation des VUF ou les analogues imprévisibles des VRP. Un VRP est également un VUP et un VUP peut en fait être construit en construisant un VRP via la construction Feistel appliquée à un VRF. Mais cela n'est pas considéré comme utile car les VUF semblent être beaucoup plus faciles à construire que les VRF.

Applications

• DES

K x X → X ∀ X={0,1} ⁶⁴ , K={0,1} ⁵⁶

• AES-128

K x X → X ∀ k=X={0,1} ¹²⁸

Voir également

• Chiffrement par bloc (familles de permutation pseudo-aléatoire fonctionnant sur des blocs de bits de taille fixe)
• Chiffrement préservant le format (familles de permutation pseudo-aléatoire opérant sur des ensembles finis arbitraires)

Les références