Mengurangi anjak piutang produk utama menjadi anjak produk bilangan bulat (rata-rata)

Pertanyaan saya adalah tentang kesetaraan keamanan berbagai fungsi kandidat satu arah yang dapat dibangun berdasarkan kekerasan anjak piutang.

Dengan asumsi masalah

FAKTOR: [Diberikan untuk bilangan prima acak P , Q < 2 n , temukan P , Q. ]$N = PQ$$P, Q < 2^n$$P$$Q$

tidak dapat dipecahkan dalam waktu polinomial dengan probabilitas yang tidak dapat diabaikan, fungsinya

PRIME-MULT: [Diberikan bit string sebagai input, gunakan x sebagai seed untuk menghasilkan dua bilangan prima acak P dan Q (di mana panjang P , Q hanya lebih kecil secara polinomi dari panjang x ); kemudian output P. Q. ]$x$$x$$P$$Q$$P$$Q$$x$$PQ$

dapat ditampilkan sebagai satu arah.

Kandidat fungsi satu arah lainnya adalah

INTEGER-MULT: [Diberikan bilangan bulat acak sebagai input, output A B. ]$A, B < 2^n$$A B$

INTEGER-MULT memiliki keunggulan yang lebih mudah untuk didefinisikan dibandingkan dengan PRIME-MULT. (Perhatikan khususnya bahwa dalam PRIME-MULT, ada kemungkinan (walaupun untungnya dapat diabaikan) bahwa benih gagal menghasilkan P , Q yang prima.)$x$$P, Q$

Setidaknya di dua tempat berbeda (Arora-Barak, Kompleksitas Komputasi, halaman 177, catatan kaki 2) dan ( Pengantar Vadhan untuk catatan kuliah Kriptografi ) disebutkan bahwa INTEGER-MULT adalah satu arah dengan asumsi kekerasan rata-rata dari anjak piutang. Namun, tidak satu pun dari keduanya memberikan alasan atau referensi untuk fakta ini.

Jadi pertanyaannya adalah:

Bagaimana kita dapat mengurangi di polinomial waktu anjak dari dengan probabilitas nonnegligible untuk pembalik INTEGER-MULT dengan probabilitas nonnegligible?$N = PQ$

Berikut adalah pendekatan yang mungkin (yang akan kita lihat TIDAK bekerja!): Diberikan , kalikan N dengan banyak (meskipun secara polinomi) bilangan bulat acak A ′ lebih lama untuk mendapatkan A = N A ′ . Idenya adalah bahwa A ' adalah begitu besar bahwa ia memiliki banyak faktor prima dari ukuran kira-kira sama dengan P , Q , sehingga P , Q tidak "menonjol" di antara faktor prima dari A . Kemudian A memiliki kira-kira distribusi bilangan bulat acak seragam pada rentang tertentu (katakan [ $N = PQ$$N$$A'$$A = NA'$$A'$$P, Q$$P, Q$$A$$A$ ). Selanjutnya pilih integer B secara acak dari kisaran yang sama [ 0 , 2 n - 1 ] .$[0,2^n-1]$$B$$[0,2^n-1]$

Sekarang jika sebuah inverter untuk INTEGER-MULT dapat, diberi , dengan beberapa probabilitas menemukan A ′ , B ′ < 2 n sehingga A ′ B ′ = A B , harapannya adalah bahwa salah satu dari A ′ atau B ′ berisi P sebagai faktor dan yang lainnya mengandung Q . Jika itu terjadi, kita dapat menemukan P atau Q dengan mengambil FPB dari A ' dengan N = P Q .$AB$$A', B' < 2^n$$A'B' = AB$$A'$$B'$$P$$Q$$P$$Q$$A'$$N = PQ$

Masalahnya adalah bahwa inverter dapat memilih untuk memisahkan faktor-faktor prima, misalnya, menempatkan faktor-faktor kecil di A ′ dan yang besar di B ′ , sehingga P dan Q berakhir di A ′ atau keduanya di B ′ .$AB$$A'$$B'$$P$$Q$$A'$$B'$

Apakah ada pendekatan lain yang berhasil?

Ini sebenarnya bukan jawaban, namun menyoroti kesulitan menunjukkan pengurangan seperti itu.

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

$\mathcal{A}^*$$N$ $N = PQR$$P$$Q$$n/4$$R$$n/2$$N$$PQ$$R$$\mathcal{A}^*$$n$$\mathcal{A}^*$

$k$

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

$n$

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

$n$

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

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