RSA- und Rabin-Funktionen: Bestimmte Teile sind genauso schwer wie das Ganze

Die RSA- und Rabin-Verschlüsselungsfunktionen EN () sind jeweils definiert, indem x ZN auf die Potenz e (wobei e relativ prim zu (N) ist) erhöht und modulo N quadriert wird (d. h. , EN (x) = xᵉ (N), EN (x) = x² (N), jeweils). Wir beweisen, dass für beide Funktionen die folgenden Probleme rechnerisch äquivalent sind (jedes ist probabilistisch polynomialzeit-reduzierbar auf das andere): (1) Gegeben EN (x), finde x. (2) Gegeben EN (x), errate das wenig-signifikante Bit von x mit einer Erfolgswahrscheinlichkeit von 12 + 1 {{poly (n) }} (wobei n die Länge des Modulus N ist). Diese Äquivalenz impliziert, dass ein Angreifer, der den RSA/Rabin-Verschlüsselungstext hat, keinen nicht vernachlässigbaren Vorteil (im Vergleich zu einem zufälligen Münzwurf) beim Erraten des wenig-signifikanten Bits des Klartexts haben kann, es sei denn, er kann RSA umkehren/faktorieren N. Die Beweistechniken liefern auch die gleichzeitige Sicherheit der n wenig-signifikanten Bits. Unsere Ergebnisse verbessern die Effizienz der pseudorandomen Zahlen-Generierung und der probabilistischen Verschlüsselungsschemata, die auf der Unlösbarkeit des Faktorisierens basieren.