Permutation unidirectionnelle finie avec domaine infini

10

Soit une permutation. Notez que tandis que agit sur un domaine infini, sa description peut être finie. Par description , je veux dire un programme qui décrit les fonctionnalités de . (Comme dans la complexité de Kolmogorov.) Voir les explications ci-dessous. π ππ:{0,1}{0,1}ππ

Par exemple, la fonction NOT est l'une de ces permutations:

fonction NOT (x)
    Soit y = x
    Pour i = 1 à | x |
        Retournez le ième bit de y
    retourner y

πk() , défini ci-dessous, est un autre cas:

fonction pi_k (x)
    retourne x + k (mod 2 ^ | x |)

Ma question concerne une classe spéciale de permutations, appelées permutations unidirectionnelles . De manière informelle, ce sont des permutations faciles à calculer, mais difficiles à inverser (pour une machine ). La simple existence de permutations à sens unique est un problème ouvert de longue date en cryptographie et en théorie de la complexité, mais dans le reste, nous supposerons qu'elles existent.BPP

Comme exemple d'une permutation unidirectionnelle conjecturée, on peut considérer le RSA : Soit un entier de Blum , et soit . La permutation unidirectionnelle est définie par: .n=pqe=65537πn(x)=xemodn

Notez que RSA est défini sur le domaine fini . En fait, pour obtenir une permutation de domaine infinie, il faut considérer une famille de permutations RSA , où est un ensemble infini d'entiers Blum. Notez que est la description de la famille, et par définition, elle est infinie.Zn{πn}nDDD

Ma question est (en supposant l'existence de permutations à sens unique):

Existe - t-il des permutations unidirectionnelles à description finie sur un domaine infini ?

La réponse peut varier: elle peut être positive, négative ou ouverte (soit susceptible d'être positive , soit susceptible d'être négative ).

Contexte

La question s'est posée lorsque je lisais un article de l' ASIACRYPT 2009 . Là, l'auteur a implicitement (et dans le contexte d'une preuve) supposé que de telles permutations à sens unique existent.

Je serai heureux si c'est effectivement le cas, même si je n'ai pas trouvé de preuve.

MS Dousti
la source
Ne pouvons-nous décrire finement ? Il existe un algorithme fini recherchant un plus petit nombre de Blum plus grand qu'un certain nombre d'entrée, donc le calcul de pourrait être décrit par exemple comme "trouver le plus petit nombre de Blum plus grand que , puis calculer ". Pourtant, il n'est pas évident pour moi que la fonction que vous obtiendrez en collant ensemble un nombre infini de sera nécessairement une permutation. Pourriez-vous expliquer? Dπ(x)bxπb(x)πb
Karolina Sołtys
@Karolina: Merci pour la réponse. Je pense que l'algorithme "trouver le plus petit nombre de Blum plus grand que , puis calculer " affichera nécessairement des informations supplémentaires sur , telles que sa factorisation. Par conséquent, un tel algorithme ne peut pas être utilisé pour décrire des permutations unidirectionnelles . Êtes-vous d'accord? bxπb(x)b
MS Dousti
Ok, je pense que je comprends - vous voulez que la description finie décrive la fonction d'une manière facile à calculer. Je pense que nous pourrions encoder la partie "trouver le plus petit nombre Blum ..." sans divulguer aucune information sur (implémenter simplement la recherche par force brute pour ), mais alors ce ne serait pas efficacement calculable. bb
Karolina Sołtys
Peut-être que cette question vous aidera avec des idées: cstheory.stackexchange.com/questions/1378
Matt Groff
@Matt: Merci. Dans cette question, la condition "facile à calculer mais difficile à inverser" ne concerne pas les machines limitées dans le temps.
MS Dousti

Réponses:

14

L'article Sur la construction de fonctions à sens unique 1-1 , par Goldreich, Levin et Nisan montre comment construire des fonctions 1-1 préservant la longueur avec des domaines infinis et une description finie. La dureté de l'inversion des fonctions est basée sur des hypothèses courantes, telles que la dureté de l'inversion du RSA ou la recherche de logarithmes discrets.

Leur construction est une torsion de l'idée simple de convertir une famille, , de fonctions unidirectionnelles en une seule fonction unidirectionnelle en définissant où est le le caractère aléatoire utilisé pour sélectionner les indices et est le caractère aléatoire utilisé pour sélectionner l'entrée (compte tenu de l'indice ).{fi}if(r,s)=fi(x)risxi

Le problème avec l'idée ci-dessus est que n'est pas nécessairement 1-1. Ils modifient ce problème en modifiant légèrement et en faisant valoir que, sous certaines conditions sur la famille , la nouvelle construction est bien 1-1. Ils montrent ensuite que ces conditions sont satisfaites par les fonctions basées sur RSA / Log discret.f(r,s)f(r,s){fi}i

Alon Rosen
la source
1
Merci Alon pour votre excellente réponse. Hors sujet: je suis très heureux de vous voir ici. J'adore votre livre et vos articles sur la connaissance zéro concurrente !
MS Dousti
Thans, Sadeq. Heureux d'apprendre que vous l'aimez :-)
Alon Rosen