Un distiguisher PRF peut-il invoquer l'algorithme de la fonction?

Question

La définition d'une fonction $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ étant une famille de fonctions pseudo aléatoires (PRF), c'est qu'elle est implémentable par un algorithme PPT $\mathcal F$, et il n'y a pas d'algorithme PPT $\mathcal A$ capable de distinguer $x\mapsto F(k,x)$ à partir d'une fonction aléatoire pour aléatoire inconnu $k$ et probabilité de non-disparition.

Est l'algorithme $\mathcal A$ autorisé à invoquer l'algorithme $\mathcal F$ exécution $(k,x)\mapsto F(k,x)$? Ou plus généralement, une partie de celui-ci?

---

Cela semble nécessaire pour décider si ce qui suit $G$ est un PRF ou non.

• Laisser $H:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ être un PRF.
• Laisser $P_c:\ \{0,1\}^n\to\{0,1\}^n$ être un PRP avec une clé fixée à une constante arbitraire $c$, avec les deux $P$ et ${P_c}^{-1}$ calculable par un algorithme PPT.
• Définir $G:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ by (assimilant des chaînes de bits à des entiers par convention big-endian) $$G(k,x)\underset{\text{def}}=\begin{cases} {P_c}(k\bmod2^{\lfloor n/2\rfloor})&\text{if }x=0^n\\ 1^n&\text{if }x=1^n\text{ and }P_c^{-1}(k)<2^{\lfloor n/2\rfloor}\\ H(k,x)&\text{otherwise} \end{cases}$$

Essentiellement, $G$ est le PRF $H$, sauf qu'il a un jeu de touches faibles $k$ de taille $2^{\lfloor n/2\rfloor}$, tel que peu importe $k$, $G(k,0^n)$est une clé faible; et quand$k$ est une clé faible, $G(k,1^n)$ est $1^n$.

Nous pouvons construire un distinctif pour $G$ cette

• soumet $x=0^n$, obtient $y$
• applique l'algorithme pour $G$ saisir $(y,1^n)$
• teste si le résultat est $1^n$, ce qui sera toujours le cas pour $G$, et seulement avec une probabilité de disparition pour une fonction aléatoire.

Cependant, il ne semble pas y avoir de distinction si nous ne pouvons ni appliquer l'algorithme pour $G$, ni l'analyser pour extraire $c$.

---

La motivation est cette question , qui demande si$F_2(k,x)\underset{\text{def}}=F(F(k,0^n),x)$ est un PRF, en supposant $F$est un PRF. Si ce qui précède$G$ était un PRF, $F=G$ serait un contre-exemple.

Answer 1

L'adversaire $\mathcal{A}$ est autorisé à invoquer l'algorithme $\mathcal{F}$ (si c'est PPT) dans n'importe quelle définition PRF connue de moi.

Nous sommes généralement intéressés par la sécurité contre tous les algorithmes PPT possibles $\mathcal{A}$ et exiger que pour chacun de ces algorithmes $\mathcal{A}$ ça tient ça $\mathcal{A}$peut seulement distinguer d'une fonction aléatoire avec une probabilité non négligeable.
Si$\mathcal{F}$ est un algorithme PPT, il existe un adversaire $\mathcal{A}$ qui inclut le $\mathcal{F}$Fonctionnalité. Cet adversaire est capable d'invoquer$\mathcal{F}$et nous exigeons de notre PRF, qu'il soit également à l'abri de cet adversaire. Le même argument vaut pour certaines parties de l'algorithme$\mathcal{F}$.

---

Pour autant que je l'ai compris, pour votre exemple, la question importante est la suivante:

Est-ce que l'adversaire $\mathcal{A}$ connaître $c$?

Encore une fois, nous avons besoin d'une indiscernabilité contre tous les adversaires d'un PRF, ce qui signifie que nous avons besoin d'indiscernabilité même contre un adversaire qui connaît ce fixe. $c$.

Answer 2

Oui, les adversaires peuvent coder en dur beaucoup de choses. C'est un thème général de la crypto et du TCS.

Dans cet article, je présenterai un point de vue plus fondamental et passerai en revue certaines définitions formelles pour répondre, espérons-le, (1) pourquoi / quel codage en dur est autorisé, et (2) comment cela est traité dans les définitions cryptographiques. Puisque la réponse à (2) est si fondamentale, en voici une copie ci-dessous:

À retenir: lors de la formalisation des définitions de sécurité, les valeurs que les adversaires ne devraient pas être en mesure de connaître sont modélisées par des variables aléatoires sur lesquelles la probabilité de gagner l'expérience est prise en compte, souvent échantillonnées uniformément au hasard dans un ensemble de taille exponentielle.

Discussion basée sur la définition des PRF

Regardons une définition assez formelle d'un PRF (cf. [KL14]):

Def. (PRF): une fonction calculable efficacement$F\colon\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$s'appelle une fonction pseudo-aléatoire (PRF) si pour tous les adversaires PPT$\mathcal{A}$ il y a une fonction négligeable $\mathrm{negl}\colon\mathbb{N}\to\mathbb{N}$ tel que pour tous $n \in \mathbb{N}$ nous avons $$\left|\Pr_{k\leftarrow_€\ \{0,1\}^n}[\mathcal{A}(1^n, F(k,-))=1] - \Pr_{f\leftarrow_€\ \{0,1\}^n\to\{0,1\}^n}[\mathcal{A}(1^n, f(-))=1]\right|\leq \mathrm{negl}(n).$$

Si vous ne connaissez pas la notation: la notation $\Pr_{k\leftarrow_€\ \{0,1\}^n}[\cdot]$ signifie que la probabilité de $\cdot$est repris l'échantillonnage de$k$ de $\{0,1\}^n$ uniformément au hasard (signifié par $\leftarrow_€$; devrait en fait être un signe dollar, mais le moteur de rendu de StackExchange n'aime pas ça). De manière analogue pour le bon terme dans l'inégalité ci-dessus où$f\leftarrow_€\{0,1\}^n\to\{0,1\}^n$ signifie que $f$est échantillonné à partir de toutes les fonctions$\{0,1\}^n\to\{0,1\}^n$ uniformément au hasard.

Considérons maintenant cette définition dans le contexte suivant:

Selon le message original, laissez $H$ être PRF, $c$ une constante fixe arbitraire, $P_c$ un PRP, et $G$ une fonction.

Maintenant demandez-vous:

Pourquoi les adversaires ne devraient-ils pas être autorisés à utiliser $H$, $c$, $P_c$, ou $G$?

De toute évidence, la définition s'étend à tous les adversaires PPT.

Même si cela avait du sens, comment interdiriez-vous (dans la formalisation mathématique) aux adversaires d'utiliser des «variables extérieures»? Que sont les "variables extérieures" de toute façon?

Je n'ai pas de réponse concise à ces questions moi-même; au lieu de cela, ils devraient simplement recalibrer votre intuition actuelle au formalisme. Interdire des choses qui ne sont même pas clairement spécifiées («choses extérieures») n'est pas trivial et n'a pas de sens la plupart du temps. En effet, nous pourrions faire croire au principe de Kerckhoff que l'adversaire est autorisé à coder en dur tout sauf la clé, celle-ci est interdite. Mais ici, "la clé" est une spécification claire et interdite qui peut être très bien gérée dans le formalisme. Voir ci-dessous.

Dans la définition formelle ci-dessus, comment les adversaires sont-ils interdits de coder en dur la clé $k$?

Bien que cette question puisse avoir un sens intuitivement, elle est mal posée! (Certains logiciens préfèrent répondre à ces questions par "mu". )

Que signifie "la clé $k$"faire référence? Voulez-vous dire le $k$de la définition? Mais ce n'est pas visible pour les adversaires$\mathcal{A}$: jetez un œil à l'ordre des quantificateurs. En gros, vous avez la chaîne de variables suivante en cours d'introduction («lié» dans le jargon CS):

$\forall \mathcal{A}\ \exists \mathrm{negl}\ \forall n\ \ldots\ \Pr_{k\leftarrow_€\ \{0,1\}^n}[\ldots]\ \ldots$

Depuis les adversaires $\mathcal{A}$ sont liés plus à l'extérieur (c'est-à-dire en premier) que $k$, du POV des adversaires il n'y a pas de "clé $k$". Surtout, cet argument dit que les adversaires ne peuvent pas comprendre syntaxiquement " la clé$k$". ^* Le seul endroit dans la définition ci-dessus où" la clé$k$"a un sens syntaxiquement dans le corps de $\Pr_{k\leftarrow_€\ \{0,1\}^n}[\mathcal{A}(1^n, F(k,-))=1]$, c'est-à-dire le sous-terme $\mathcal{A}(1^n, F(k,-))=1$. C'est le seul terme ayant un accès syntaxique à "la clé$k$".

Attention, il y a au moins deux manières sémantiques différentes (mais non mutuellement exclusives) auxquelles je peux penser pour obtenir une / plusieurs clé (s):

1. Les adversaires pourraient énumérer toutes les valeurs possibles de $\{0,1\}^n$ cette $k$peut être lié à. Heureusement, pour les adversaires PPT, un tel renforcement brutal est impossible avec une taille exponentielle (voire superpolynomiale) dans le paramètre de sécurité$n$.
2. Pour chaque valeur possible de $k$ (c'est-à-dire dans $\{0,1\}^n$), il pourrait y avoir un adversaire$\mathcal{A}_k$ cela dépend de $k$ et remplit réellement $\Pr[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$ et $\Pr_{f\leftarrow_€\ \{0,1\}^n\to\{0,1\}^n}[\mathcal{A}(1^n, f(-)) = 1] = 0$. Cela semble presque rendre inutile toute notre définition de la sécurité pour les PRF depuis$|1 - 0| = 1$et cela ne peut jamais être moins qu'une fonction négligeable. Cependant, notez de manière cruciale que j'ai dit qu'il remplit$\Pr[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$ et pas $\Pr_{k\leftarrow_€\{0,1\}^n}[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$. Cela fait une grande différence que la probabilité soit prise sur un échantillon d'une variable aléatoire ou non.

Conditions nécessaires pour les définitions de sécurité

En résumé, il y a trois conditions nécessaires pour l'expression intuitive mais informelle «les adversaires ne connaissent pas la clé»:

1. syntaxiquement, les clés sont inaccessibles à l'endroit où les adversaires sont liés,
2. sémantiquement, les clés sont échantillonnées à partir d'un ensemble de taille superpolynomiale dans le paramètre de sécurité,
3. et sémantiquement encore, les clés sont des variables aléatoires liées dont les probabilités sont prises en charge.

Si l' une de ces conditions n'est pas remplie, il est fort probable que la définition de la sécurité n'a pas de sens et ne capture pas ce que nous pensons qu'elle devrait capturer.

À retenir: lors de la formalisation des définitions de sécurité, les valeurs que les adversaires ne devraient pas être en mesure de connaître sont modélisées par des variables aléatoires sur lesquelles la probabilité de gagner l'expérience est prise en compte, souvent échantillonnées uniformément au hasard dans un ensemble de taille exponentielle.

Ceci conclut la réponse à la question (1) sur pourquoi / quel codage en dur est autorisé.

Un autre exemple avec des "valeurs publiques" en crypto

Voici un autre exemple de définition de sécurité tirée de [Sch20]:

Def. (Confidentialité de RingCT): un schéma RingCT$\Omega$est privé si pour tous les adversaires PPT$\mathcal{A}$ et entiers positifs $\alpha, \beta \in \mathrm{poly}(\lambda)$, $$\Pr[\mathrm{Privacy}_{\Omega,\mathcal{A}}(\lambda, \alpha, \beta) = 1] \leq \frac{1}{2} + \mathrm{negl}(\lambda)$$

Qu'est-ce qu'un schéma RingCT et comment$\mathrm{Privacy}$est défini n'a pas d'importance du tout. Plus utile pour cette discussion est la portée de$\alpha$ et $\beta$.

Adversaires de mai $\mathcal{A}$ hardcode $\alpha$ et $\beta$?

Oui, ils peuvent, même pour deux raisons différentes (dont une suffirait): - La condition 1. d'en haut est cassée: syntaxiquement - comme on le sait de la logique, on peut réorganiser les quantificateurs universels consécutifs comme dans $\forall \mathcal{A} \forall \alpha \forall \beta \ldots$autant que nous aimons. Par conséquent, nous pouvons réorganiser pour$\forall \alpha \forall \beta \forall \mathcal{A} \ldots$. - La condition 3. d'en haut est cassée:$\alpha, \beta$ne sont pas des variables aléatoires liées sur lesquelles la probabilité est prise. Ainsi, pour chaque$\alpha, \beta$ vous pouvez trouver un adversaire $\mathcal{A}_{\alpha, \beta}$.

Un autre exemple de TCS

Au début, j'ai promis que (dés) autoriser les choses à coder en dur est aussi un thème de l'informatique théorique. Plus précisément, cela se produit dans la théorie de la complexité , un sous-domaine qui est également étroitement lié à la cryptographie.

Là, on définit les langues $L \subseteq \{0,1\}^\ast$ comme ensembles et ensuite se demander à quel point il est difficile pour une machine de Turing de décider pour certains $w \in \{0,1\}^\ast$ qu'il obtient comme entrée si $w \in L$ou pas. Concrètement, nous définissons:

Def. (Langue décidable): Une langue$L$est décidable s'il y a une machine de Turing$M$ tel que

• pour tous $w \in L$, $M$ avec entrée $w$ s'arrête avec acceptation,
• et pour tous $w' \not\in L$, $M$ avec entrée $w'$ rejette.

Rappelez-vous les trois conditions ci-dessus nécessaires pour que les définitions de sécurité dans la cryptographie aient un sens. Comment s'intègrent-ils ici?

La condition 1 est remplie depuis $w$ et $w'$ sont plus liés que $M$. Même si$M$ reçoit les deux comme entrées - ce qui serait inimaginable en crypto s'il s'agissait de clés, il y a toujours une différence cruciale entre $M$ nécessaire pour faire face à tous ces intrants et $M$nécessaire pour exister pour toutes ces entrées. (Ce dernier serait$\forall w \in L.\ \exists M.\ \ldots$) Cette différence est un point commun de confusion lorsque nous prenons $L$être le problème Halting ( un langage indécidable). Pour chaque ("fixe")$w \in H$ il y a une machine de Turing $M_w$ qui accepte siff. $w \in H$. ²

De plus, la condition 2. est également remplie ici puisque les langues sont généralement infinies. (Sinon, s'ils étaient finis, il serait ennuyeux de parler de complexité de calcul.)

Enfin, la condition 3 n'est pas applicable ici car aucune probabilité n'est impliquée.

---

Notes de bas de page et références

¹ : L'explication de ce que je veux dire "syntaxiquement" nécessite un peu de contexte CS: chaque fois que vous instanciez la définition de sécurité, à l'endroit où vous instanciez l'adversaire$\mathcal{A}$ avec un terme $t$, $t$ ne peut pas en inclure $k$ car $k$ n'est tout simplement pas visible dans ce contexte.

² : Avec la logique classique, vous pourriez soutenir que pour tous$w \in \{0,1\}^\ast$, Soit $w \in H$ ou $w \not\in H$. Dans le premier cas, prenez la machine qui accepte immédiatement comme$M_w$, et dans le second cas, prenez la machine qui rejette immédiatement.

[KL14]: Katz, J., et Lindell, Y. (2014). Introduction à la cryptographie moderne. CRC Press.

[Sch20]: Dominique Schröder. (2020). Crypto-monnaies préservant la confidentialité. Notes de cours inédites pour un cours équinomé donné par l'auteur à l'été 2020 à FAU Erlangen-Nürnberg.https://www.chaac.tf.fau.eu/teaching/lectures/.