Zredukowanie podstawowych produktów faktoringowych do faktoringowych liczb całkowitych (w przeciętnym przypadku)

Moje pytanie dotyczy równoważności bezpieczeństwa różnych kandydujących funkcji jednokierunkowych, które można zbudować w oparciu o twardość faktoringu.

Zakładając problem

FAKTORING: [Biorąc pod uwagę dla losowych liczb pierwszych , znajdź , ]P , Q < 2 n P $N = PQ$$P, Q < 2^n$$P$$Q$

funkcja nie może być rozwiązana w czasie wielomianowym z nieistotnym prawdopodobieństwem

PRIME-MULT: [Biorąc pod uwagę ciąg bitów jako dane wejściowe, użyj jako zarodka do wygenerowania dwóch losowych liczb pierwszych i (gdzie długości , są tylko wielomianowo mniejsze niż długość ); następnie .]x P Q P Q x P $x$$x$$P$$Q$$P$$Q$$x$$PQ$

może być pokazany jako jednokierunkowy.

Inną kandydującą funkcją jednokierunkową jest

INTEGER-MULT: [Podane losowe liczby całkowite jako wejście, wyjście .] A $A, B < 2^n$$A B$

INTEGER-MULT ma tę zaletę, że jest łatwiejszy do zdefiniowania w porównaniu do PRIME-MULT. (Zwróć uwagę w szczególności, że w PRIME-MULT istnieje szansa (choć na szczęście nieistotna), że ziarno nie wygeneruje które są pierwsze.)P , $x$$P, Q$

Przynajmniej w dwóch różnych miejscach (Arora-Barak, Złożoność obliczeniowa, strona 177, przypis 2) oraz ( Nota wykładu Wprowadzenie do kryptografii Vadhana ) wspomina się, że INTEGER-MULT jest jednokierunkowy przy założeniu średniej twardości faktoringu. Jednak żadne z tych dwóch nie podaje przyczyny ani odniesienia do tego faktu.

Pytanie brzmi:

Jak możemy zredukować w wielomianowym rozkładzie czasu z nieistotnym prawdopodobieństwem do odwrócenia INTEGER-MULT z nieistotnym prawdopodobieństwem?$N = PQ$

Oto możliwe podejście (które, jak zobaczymy, NIE działa!): Biorąc pod uwagę , pomnóż przez znacznie (choć wielomianowo) dłuższą losową liczbę całkowitą aby uzyskać . Chodzi o to, że jest tak duża, że ma wiele czynników pierwszych wielkości w przybliżeniu równa , dzięki czemu nie«wyróżniać»wśród głównych czynników . Wtedy ma w przybliżeniu rozkład jednolicie losowej liczby całkowitej w danym zakresie (powiedzmy ). Następnie losowo wybierz liczbę całkowitą z tego samego zakresu .N A ′ A = N A ′ A ′ P , Q P , Q A A [ 0 , 2 n - 1 ] B [ 0 , 2 n - 1 $N = PQ$$N$$A'$$A = NA'$$A'$$P, Q$$P, Q$$A$$A$$[0,2^n-1]$$B$$[0,2^n-1]$

Teraz, jeśli falownik dla INTEGER-MULT może, biorąc pod uwagę , z pewnym prawdopodobieństwem znaleźć tak, że , istnieje nadzieja, że ​​jeden z lub zawiera jako czynnik a drugi zawiera . W takim przypadku możemy znaleźć lub , biorąc gcd z z .A ′ , B ′ < 2 n A ′ B ′ = A B A ′ B ′ P Q P Q A ′ N = P $AB$$A', B' < 2^n$$A'B' = AB$$A'$$B'$$P$$Q$$P$$Q$$A'$$N = PQ$

Problem polega na tym, że falownik może rozdzielić czynniki pierwsze, na przykład umieszczając małe czynniki w i duże w , tak aby i kończyły się w lub oba w .A ′ B ′ P Q A ′ B $AB$$A'$$B'$$P$$Q$$A'$$B'$

Czy działa inne podejście?

To nie jest tak naprawdę odpowiedź, ale rzuca nieco światła na trudność wykazania takich redukcji.

Problem można streścić w następujący sposób: Niech będzie algorytmem, który rozwiązuje problem INTEGER-MULT z nieistotnym prawdopodobieństwem. Niech to prawdopodobieństwo będzie wynosić co najmniej n - c , dla pewnej stałej c ∈ N (gdy wielkość wejściowa wynosi n ). Dowodzą, że istnieje PPT (probabilistyczny wielomian Time) algorytm A " , która wykorzystuje A jako podprogram i rozwiązuje wystąpienie problemu FAKTORINGU wielkości n z prawdopodobieństwa co najmniej n - D , dla pewnej stałej d ∈ N .$\mathcal{A}$$n^{-c}$$c \in \mathbb{N}$$n$$\mathcal{A}'$$\mathcal{A}$$n$$n^{-d}$$d \in \mathbb{N}$

Rozważmy algorytm który rozwiązuje problem INTEGER-MULT wtedy i tylko wtedy, gdy wejście N ma specjalną wartość od N = P Q R , gdzie P i Q są liczbami pierwszymi o rozmiarze n / 4, a R jest liczbą pierwszą o rozmiarze n / 2 i inaczej zawodzi. Ponadto, na wejściu liczbę całkowitą N powyższej postaci wyprowadza P Q i R . Najpierw pokazujemy, że A$\mathcal{A}^*$$N$ $N = PQR$$P$$Q$$n/4$$R$$n/2$$N$$PQ$$R$$\mathcal{A}^*$ma niemałe prawdopodobieństwo rozwiązania problemu INTEGER-MULT. W tym celu wystarczy znaleźć ułamek bitowych liczb całkowitych formy specjalnej, ponieważ ułamek ten ogranicza prawdopodobieństwo sukcesu A ∗ od dołu.$n$$\mathcal{A}^*$

Według twierdzenia o liczbie pierwszych liczba liczb pierwszych, których rozmiar to bitów, wynosi:$k$

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

Dlatego ułamek liczb całkowitych bitowych postaci specjalnej wynosi:$n$

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

co nie jest bez znaczenia w .$n$

$\mathcal{A}'$$\mathcal{A}^*$$n$$n^{-d}$$d \in \mathbb{N}$

$\mathcal{A}^*$$PQ$