Existe-t-il des classes de fonctions qui nécessitent des ressources prouvablement différentes pour calculer ou calculer leur inverse?

Toutes mes excuses à l'avance si cette question est trop simple.

Fondamentalement, ce que je veux savoir, c'est s'il existe des fonctions $f(x)$ avec les propriétés suivantes:

Prenez pour être lorsque le domaine et le domaine de codage sont limités à des chaînes à bits. alors $f_n(x)$ $f(x)$ $n$

$f_n(x)$ est injective
$f_n(x)$ est surjectif
$f_n(x)$ prend strictement moins de ressources (espace / temps / profondeur de circuit / nombre de portes) pour calculer sous un modèle raisonnable que , où . $f^{-1}_n(y)$ $y=f_n(x)$
La différence de ressources pour vs est une fonction strictement croissante de . $f_n(x)$ $f^{-1}(y)$ $n$

Je peux trouver des exemples où la fonction est soit surjective soit injective, mais pas les deux, sauf si je recourt à un modèle de calcul artificiel. Si je choisis un modèle de calcul qui permet des décalages à gauche en temps unitaire sur certains anneaux, mais pas des décalages à droite, alors il est bien sûr possible de trouver un linéaire au-dessus de la tête (ou plus si vous considérez une permutation plus compliquée comme une primitive) . Pour cette raison, je ne m'intéresse qu'aux modèles raisonnables, par lesquels je veux dire principalement les machines de Turing ou les circuits NAND ou similaires.

Évidemment, cela doit être vrai si $P\neq NP$ , mais il semblerait que cela soit également possible si $P=NP$ , et ne devrait donc pas équivaloir à trancher cette question.

Il est tout à fait possible que cette question ait une réponse évidente ou un obstacle évident à la réponse que j'ai manqué.

cc.complexity-theory Joe Fitzsimons
la source

Ce n'est pas un domaine que je comprends bien, mais il semble que vous recherchiez une permutation sur n bits difficile à inverser. Je me souviens avoir lu dans un article de Hastad ( nada.kth.se/~johanh/onewaync0.ps ) qu'il existe des permutations qui sont en

, mais qui sont P-difficiles à inverser.

N C^{0}

$NC^0$

Robin Kothari

Voir également les références à des travaux antérieurs dans l'article de Håstad de 1987. Il mentionne que Boppana et Lagarias (1986) donnent un exemple de permutation qui est dans NC

, mais ne peut pas être inversée dans NC

^{0}

$^0$

^{0}

$^0$

Jukka Suomela

Merci, c'est exactement ce que je cherchais. Peut-être que l'un de vous veut republier comme réponse? Savez-vous s'il existe quelque chose de similaire pour la complexité du temps?

Joe Fitzsimons

Réponses:

On m'a demandé de republier mon commentaire. J'ai souligné cet article de Hastad, qui montre qu'il existe des permutations dans qui sont P-difficiles à inverser: $NC^0$

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)

Robin Kothari
la source

Merci, cela et le suivi de Jukka étaient exactement le genre de chose que je cherchais.

Joe Fitzsimons

Pour les circuits booléens sur une base binaire complète (la mesure de complexité étant le nombre de portes dans un circuit minimal), le meilleur rapport connu pour les permutations $C(f)$ $\frac{C(f^{-1})}{C(f)} = const$ . Pour autant que je sache, la meilleure constante a été obtenue dans ce travail par Hiltgen et est égale à 2.

Éditer. Comme vous voulez que le ratio augmente lorsque augmente, cela ne répond pas à votre question. Cependant, pour les circuits booléens sur une base binaire complète, rien de mieux n'est connu. $n$

Grigory Yaroslavtsev
la source

Eh bien, le fait que rien de mieux ne soit connu est en effet une réponse.

Joe Fitzsimons

Je suggère également de lire la section 1.2 «Asymétrie computationnelle» de l'article suivant: Jean-Camille Birget, Permutations unidirectionnelles, asymétrie et distorsion computationnelles, Journal of Algebra, 320 (11), Algèbre computationnelle, 1er décembre 2008, pages 4030-4062 . De plus, ce lien peut vous intéresser: springerlink.com/content/4318u2t21682752u

MS Dousti

Un suivi du travail de Hiltgen est un article de Hirsh et Nikolenko montrant une fonction avec un écart constant entre le calculer et l'inverser, mais où il y a aussi une trappe permettant une inversion plus facile: logic.pdmi.ras.ru/~hirsch/ papers / 09csr.ps.gz

user686

Voir aussi cette conférence de Massey: iacr.org/publications/dl/massey96/html/massey.html

user686

Enfin, permettez-moi d'ajouter que ce serait une avancée majeure de montrer l'existence d'une famille de fonctions avec un intervalle super constant: montrer un tel intervalle impliquerait que (la version de recherche de) circuit-SAT n'a pas de circuits de taille linéaire .

user686

Tout d'abord, je voulais souligner que la surjectivité n'est pas bien définie sans d'abord définir le codomaine de la fonction. Donc, dans ma description ci-dessous, je ferai explicitement référence au domaine de codage sur lequel la fonction est surjective.

Le logarithme discret ou les fonctions RSA sont tous deux des permutations qui sont difficiles à inverser. Ci-dessous, je décrirai la fonction de logarithme discret.

Soit un nombre premier , et un générateur du groupe multiplicatif . Définissez comme $p_n$ $n$ $g$ $\mathbb{Z}_{p_n}^*$ $f_n \colon \mathbb{Z}_{p_n} \to \mathbb{Z}_{p_n}$ $f_n(x) = g^x \pmod{p_n}$ .

Ensuite, est une fonction dont les propriétés sont telles qu'indiquées dans votre question: elle est à la fois injective et surjective (sur le codomaine ), elle est calculable en temps polynomial, mais on suppose qu'aucun algorithme efficace ne peut inverser sur moyenne. $f_n$ $\mathbb{Z}_{p_n}$ $f_n$

MS Dousti
la source

Eh bien, ils ont la même complexité à calculer et à inverser sur un ordinateur quantique, donc je supposais en quelque sorte qu'il n'y avait aucune preuve qu'ils nécessitaient des ressources différentes, seulement un tas de tentatives infructueuses pour trouver des algorithmes polynomiaux.

Joe Fitzsimons

D'accord, je pense que vous avez peut-être mal compris le point de ma question. Je sais qu'il existe une multitude de fonctions qui sont difficiles à inverser, et cela constitue la base de la cryptographie à clé publique. Ce que je recherche, c'est un cas où il y a une différence prouvée, même si elle est relativement légère (je serais parfaitement satisfait d'une fonction qui prend O (n) pour calculer et O (n log n) pour inverser par exemple).

Joe Fitzsimons

[Concernant le 1er commentaire] Vous recherchez une famille de permutations à sens unique. La simple existence de telles constructions, même sur le modèle de calcul de Turing Machine, reste à prouver (la preuve en résulte une preuve de l'existence de la cryptographie à clé publique. Voir le cas 5 dans cstheory.stackexchange.com/questions/ 1026 /… ) Par conséquent, vous ne pouvez pas vous fier à des hypothèses non prouvées. Cependant, si vous voulez une hypothèse qui fonctionne à la fois dans le modèle de Turing Machine et le modèle Quantum, je peux vous fournir des détails sur les hypothèses basées sur la dureté du "problème de réseau".

MS Dousti

Je ne cherche qu'une forme très faible de fonction à sens unique, et je ne suis pas certain de l'état du problème pour des conditions suffisamment faibles. Je n'ai certainement pas besoin d'une différence exponentielle.

Joe Fitzsimons

Non, la complexité temporelle est régie par la complexité temporelle de l'exponentielle modulaire dans tous les cas que vous mentionnez. L'exponentielle modulaire est la partie lente de l'algorithme de Shor, il n'y a donc pas plus qu'une différence constante dans la mise à l'échelle asymptotique.

Joe Fitzsimons