Endliche Einwegpermutation mit unendlicher Domäne

Sei $\pi \colon \{0,1\}^* \to \{0,1\}^*$ eine Permutation. Beachten Sie, dass $\pi$ auf eine unendliche Domäne einwirkt, seine Beschreibung jedoch endlich sein kann. Mit Beschreibung meine ich ein Programm, das die Funktionalität von beschreibt $\pi$. (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

$\pi_k(\cdot)$ , 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 $\rm{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 = pq$$e = 65537$$\pi_n(x) = x^e \bmod n$

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.$\mathbb{Z}_n$$\{\pi_n\}_{n\in D}$$D$$D$

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.

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 ).$\{f_i\}_i$$f(r,s) = f_i(x)$$r$$i$$s$$x$$i$

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 } $f(r,s)$$f(r,s)$$\{f_i\}_i$