Endliche Einwegpermutation mit unendlicher Domäne

10

Sei π:{0,1}{0,1} eine Permutation. Beachten Sie, dass π auf eine unendliche Domäne einwirkt, seine Beschreibung jedoch endlich sein kann. Mit Beschreibung meine ich ein Programm, das die Funktionalität von beschreibt π. (Wie bei der Komplexität von Kolmogorov.) Siehe Erläuterungen unten.

Zum Beispiel ist die NOT-Funktion eine solche Permutation:

Funktion NICHT (x)
    Sei y = x
    Für i = 1 bis | x |
        Drehe das i-te Bit von y um
    return y

πk() , wie unten definiert, ist ein anderer Fall:

Funktion pi_k (x)
    return x + k (mod 2 ^ | x |)

Meine Frage bezieht sich auf eine spezielle Klasse von Permutationen, die als Einwegpermutationen bezeichnet werden . Informell gesehen sind dies Permutationen, die leicht zu berechnen, aber schwer zu invertieren sind (für eine BPP Maschine). Die bloße Existenz von Einwegpermutationen ist ein seit langem offenes Problem in der Kryptographie und Komplexitätstheorie, aber im Rest werden wir annehmen, dass sie existieren.

n=pqe=65537πn(x)=xemodn

Beachten Sie, dass RSA über die endliche Domäne . Um eine unendliche Domänenpermutation zu erhalten, muss man eine Familie von RSA-Permutationen , wobei eine unendliche Menge von Blum-Ganzzahlen ist. Beachten Sie, dass die Beschreibung der Familie ist und per Definition unendlich ist.Zn{πn}nDDD

Meine Frage ist (unter der Annahme der Existenz von Einwegpermutationen):

Gibt es Einwegpermutationen mit endlicher Beschreibung über eine unendliche Domäne ?

Die Antwort kann variieren: Sie kann positiv, negativ oder offen sein (entweder wahrscheinlich positiv oder wahrscheinlich negativ ).

Hintergrund

Die Frage stellte sich, als ich einen Artikel von ASIACRYPT 2009 las . Dort nahm der Autor implizit (und im Zusammenhang mit einigen Beweisen) an, dass solche Einwegpermutationen existieren.

Ich würde mich freuen, wenn dies tatsächlich der Fall ist, obwohl ich keinen Beweis finden konnte.

MS Dousti
quelle
Können wir nicht endlich beschreiben ? Es gibt einen endlichen Algorithmus, der nach einer kleinsten Blum-Zahl sucht, die größer als eine Eingangszahl ist. könnte die Berechnung von beispielsweise als "Finde die kleinste Blum-Zahl größer als und berechne dann " beschrieben werden. Dennoch ist mir nicht klar, dass die Funktion, die Sie durch Zusammenkleben einer unendlichen Anzahl von , notwendigerweise eine Permutation ist. Könntest du erklären? Dπ(x)bxπb(x)πb
Karolina Sołtys
@ Karolina: Danke für die Antwort. Ich denke, der Algorithmus "finde die kleinste Blum-Zahl größer als , dann berechne " wird notwendigerweise zusätzliche Informationen über , wie z. B. seine Faktorisierung. Daher kann solcher Algorithmus nicht verwendet werden , um zu beschreiben Einweg Permutationen. Sind Sie einverstanden? bxπb(x)b
MS Dousti
Ok, ich glaube ich verstehe - Sie möchten, dass die endliche Beschreibung die Funktion auf einfach zu berechnende Weise beschreibt. Ich denke, wir könnten den Teil "Finde die kleinste Blum-Zahl ..." codieren, ohne irgendwelche Informationen über preiszugeben (implementiere einfach die Brute-Force-Suche nach ), aber dann wäre er nicht effizient berechenbar. bb
Karolina Sołtys
Vielleicht hilft diese Frage bei Ideen: cstheory.stackexchange.com/questions/1378
Matt Groff
@ Matt: Danke. In dieser Frage bezieht sich die Bedingung "leicht zu berechnen, aber schwer zu invertieren" nicht auf polyzeitlich begrenzte Maschinen.
MS Dousti

Antworten:

14

Die Arbeit über die Konstruktion von 1-1- Einwegfunktionen von Goldreich, Levin und Nisan zeigt, wie man längenerhaltende 1-1-Funktionen mit unendlichen Domänen und endlicher Beschreibung konstruiert. Die Härte beim Invertieren der Funktionen basiert auf gängigen Annahmen, wie z. B. der Härte beim Invertieren von RSA oder dem Auffinden diskreter Logarithmen.

Ihre Konstruktion ist eine Wendung der einfachen Idee, eine Familie von Einwegfunktionen in eine einzelne Einwegfunktion umzuwandeln, indem wobei ist Die Zufälligkeit, die zum Auswählen des Index und ist die Zufälligkeit, die zum Auswählen des Eingangs (unter Berücksichtigung des Index ).{fi}if(r,s)=fi(x)risxi

Das Problem mit der obigen Idee ist, dass nicht unbedingt 1-1 ist. Sie ändern dieses Problem, indem sie leicht modifizieren und argumentieren, dass unter bestimmten Bedingungen für die Familie die neue Konstruktion tatsächlich 1-1 ist. Anschließend zeigen sie, dass diese Bedingungen von den auf RSA / Discrete-Log basierenden Funktionen erfüllt werden.f ( r , s ) { f i } if(r,s)f(r,s){fi}i

Alon Rosen
quelle
1
Danke Alon für deine hervorragende Antwort. Off-Topic: Ich freue mich sehr, Sie hier zu sehen. Ich liebe dein Buch und deine Papiere über gleichzeitiges Nullwissen !
MS Dousti
Dann, Sadeq. Freut mich zu hören, dass es dir gefällt :-)
Alon Rosen