algorithme polynomial-temps avec l'espace exponentiel est admissible?

Question

Je suis curieux de savoir deux choses.

1. Quand on définit la classe appelée « algorithme probabiliste polynomial » dans la science informatique, comprend-elle algorithme polynomial avec un espace exponentiel? Par exemple, lorsque l'algorithme est considéré comme donné une entrée de domaine $ \ {0,1 \} ^ n $, si l'algorithme interroge sa table interne de taille exponentielle (ex. $ 0 ^ n \ to0,0 ^ {n-1} 1 \ à1 $ et ainsi de suite ..) et sort le résultat? Est-il encore algorithme polynomial?

2. Dans la cryptographie théorique, à sens unique fonction $ f: \ {0,1 \} ^ * \ à \ {0,1 \} ^ * $ a une exigence, qui est lié avec dur -à-inverti propriété, comme bloc suivant. Si la réponse à la question ci-dessus est oui, est-il possible de construire l'algorithme $ A '$ pour simuler exactement le même que $ f $ pour chaque valeur dans $ \ {0,1 \} ^ n $ en utilisant le tableau exponentielle comme décrit ci-dessus en question ? Si donc, cela implique qu'il est impossible de concevoir la fonction à sens unique qui est certainement pas vrai. Alors qu'est-ce que je manqué?

   Pour chaque algorithme probabiliste polynomial $ A '$, tout polynôme positif $ p (\ cdot) $, et tout suffisamment large $ n $' s,

   $ Pr [A '(f (U_n), 1 ^ n) \ in f ^ {- 1} (f (U_n))] <\ frac {1} {p (n)} $

   où est variable aléatoire $ U_n $ réparti uniformément sur $ \ {0,1 \} ^ n $

Answer 1

En ce qui concerne votre première question, ce que vous êtes absent est où votre « tableau exponentielle » vient. Votre algorithme a une description finie et devrait fonctionner pour tous les n $ $. Donc, il ne peut pas contenir explicitement le $ n $ -table pour tout n $ $. Il pourrait contenir instructions pour calculer la table, mais il faudrait d'abord les exécuter, et la construction d'une table de taille exponentielle prend du temps exponentielle.

D'autre part, votre programme pourrait utiliser un (soi-disant) quantité exponentielle de non initialisée espace. Depuis son temps d'exécution est polynomiale, il accède uniquement des cellules polynomiale beaucoup. Vous pouvez mettre en œuvre un accès mémoire de manière à ce que si les cellules $ T $ sont toujours accessibles alors $ \ tilde {O} (T) $ mémoire est utilisée (exercice). Le temps d'exécution correspondant pourrait devenir bien pire, mais toujours polynomiale.

Une troisième possibilité est non uniforme modèles de calcul, qui sont très populaires en cryptographie. Ici, l'idée est que l'algorithme est autorisé à utiliser une certaine quantité codée en dur des données qui ne dépend que de $ n $. Toutefois, ces données doit être taille polynomiale. Cette restriction provient de l'interprétation du modèle en termes de circuits . Une machine en marche en correspond polynomiaux à des circuits pour chaque $ n $ de taille polynomiale. Si nous nous reposons maintenant la contrainte que tous ces circuits proviennent d'un algorithme unique, nous obtenons polynomiale non uniforme , qui est le même calcul avec des conseils en fonction de $ n $ de taille polynomiale (exercice) .

La réponse à la première question devrait permettre d'éviter le second. Je voudrais juste mentionner que parfois, au lieu des algorithmes probabilistes en temps polynomiale, on considère (déterministe) des circuits de taille polynomiale.

Answer 2

1. Non. Dans le cadre standard dans la communauté cryptographique, ce genre d'algorithme est généralement pas considéré polynomial probabiliste: si nécessaire, nous modifions la définition pour faire en sorte que ce n'est pas

   .

   Sur le plan technique, en cryptographie certaines personnes ont suggéré que nous utilisons la somme des temps d'exécution plus la taille du code du programme comme mesure du temps de l'attaque (vous pouvez penser comme ceci: si le code du programme est $ k bits $, il faudra $ k pas de temps de $ juste pour lire ce code dans la mémoire avant de vous lancer en cours d'exécution). Si vous entendez quelqu'un dire « temps d'exécution » dans la cryptographie, ils pourraient en fait signifier cette somme. Je pense que j'ai appris ce détail technique de Phil Rogaway, mais je ne sais pas s'il est tout d'abord.

   Si vous ne me croyez pas, voici une citation d'exemple à la littérature: vous pouvez regarder Bellare et al, la sécurité du message code d'authentification enchaînant bloc de chiffrement , Journal des sciences informatiques et du système. Voir la section 2.2, modèle de calcul, où ils écrivent:

   Nous Fixons Random Access particulière machine (RAM) comme modèle de calcul. [...] Quand on parle du temps d'exécution d'un comprendra ce temps d'exécution réelle A plus la longueur de la description de A (ce qui signifie la longueur du programme RAM qui décrit A). Cette convention élimine les pathologies causées si l'on peut intégrer de façon arbitraire les grandes tables de consultation dans la description A.

   Remarquez comment ils prévu ce cas de coin et ont choisi des définitions qui l'évitent d'être problématique. Avec cette définition, tout fonctionne de façon raisonnable, et votre algorithme proposé (avec une constante exponentielle de la taille) n'est pas un algorithme probabiliste polynomial.

   De nombreux cryptographes sont pas toujours attention à leur définition du temps en cours d'exécution. Il est très fréquent d'être un peu bâclée et omettre ce genre de détail. Souvent, il n'a pas d'importance. Mais quand on commence à parler de constantes exponentielle taille, ce détail fait matière, très bien, et que ce quand il est essentiel de connaître ce détail technique, si vous voulez discuter sur formalismes.

2. Non.

Par ailleurs, je maintiens ma réponse à ce sujet, malgré la (inexpliquée) downvote. Beaucoup de gens ne savent pas que d'autres dans la communauté des chercheurs ont déjà anticipé ce genre de subtilité, et quelques papiers font une grande partie de, donc je ne blâme pas les autres pour ne pas connaître les définitions pertinentes de la communauté cryptographique.