Fonction pseudo-aléatoire

L'existence d'une fonction pseudo-aléatoire ${\displaystyle {\mathcal {F}}}$ rend possible la conception d'un schéma de chiffrement symétrique sémantiquement sûr par la construction qui suit[1]. Intuitivement, elle consiste à utiliser la sortie de la fonction pseudo-aléatoire comme une sortie uniforme pour l'utiliser comme masque jetable. L'avantage réside en le fait que la clef n'est ici plus aussi longue que le message, mais va dépendre de la clef utilisée et de la taille de l'aléa (qui est dépendante de l'entrée de la fonction pseudo-aléatoire ${\displaystyle {\mathcal {F}}}$).

• Génération de la clef: Une clef ${\displaystyle k\gets _{\$}{\mathcal {K}}}$ est générée aléatoirement dans l'espace des clefs de la PRF.
• Chiffrer: Pour chiffrer un message ${\displaystyle m}$ sous la clef ${\displaystyle k}$, on calcule le message chiffré de la manière suivante:
  • Tirer un aléa ${\displaystyle r\gets _{\$}{\mathcal {X}}}$.
  • Renvoyer le message chiffré: ${\displaystyle C=(r,F(k,r)\oplus m)}$, où ${\displaystyle \oplus }$ représente le ou exclusif bit à bit.
• Déchiffrer: Pour déchiffrer un message ${\displaystyle C=(c_{1},c_{2})}$ avec la clef ${\displaystyle k}$, on calcule: ${\displaystyle m'=F(k,c_{1})\oplus c_{2}}$.

La correction se vérifie par le fait que ${\displaystyle \oplus }$ est involutif.

La sécurité s'obtient par réduction polynomiale depuis la sécurité du chiffrement pseudo-aléatoire. En d'autres termes, si un adversaire était capable de distinguer entre le schéma présenté ci-dessus et une chaîne aléatoire, alors on pourrait directement l'utiliser pour distinguer entre un message construit à l'aide d'une fonction pseudo-aléatoire d'une vraie fonction aléatoire, auquel cas le chiffré ${\displaystyle (c_{1},c_{2})}$ serait distribué uniformément sur l'espace des chiffrés (le ou exclusif d'une constante (ici un message)par une fonction uniforme est distribué comme une fonction uniforme).