Konsekuensi Anjak berada di P?

Anjak piutang tidak dikenal sebagai NP-complete. Pertanyaan ini menanyakan konsekuensi dari Anjak piutang menjadi NP-lengkap. Anehnya, tidak ada yang meminta konsekuensi Anjak di P (mungkin karena pertanyaan seperti itu sepele).

Jadi pertanyaan saya adalah:

Yang akan menjadi konsekuensi teoritis dari Anjak berada di P? Bagaimana gambaran keseluruhan kelas kompleksitas akan dipengaruhi oleh fakta seperti itu?
Yang akan menjadi konsekuensi praktis dari Anjak berada di P? Tolong jangan katakan bahwa transaksi perbankan bisa dalam bahaya, saya sudah tahu konsekuensi sepele ini.

cc.complexity-theory cr.crypto-security conditional-results factoring Giorgio Camerani
sumber

Saya mengajukan pertanyaan serupa beberapa hari yang lalu: "Apa kekuatan P dengan oracle faktorisasi bilangan bulat?" cstheory.stackexchange.com/questions/4765/…

Marzio De Biasi

Terkait juga: Apa konsekuensi dari anjak piutang menjadi NP-lengkap?

Kaveh

@ Kaveh, pertanyaannya sudah terhubung ke yang itu.

Peter Taylor

Jawaban:

Hampir tidak ada konsekuensi teoretis kompleksitas dari Anjak berada di P. Ini berarti bahwa tidak ada pembenaran yang baik untuk anjak menjadi sulit, selain itu tidak ada yang mampu memecahkannya sejauh ini.

Anjak-waktu polinomial akan memungkinkan untuk mengambil akar kuadrat dari (dan juga pada kelas cincin yang jauh lebih umum juga), dan memberikan algoritme waktu polinomial untuk sejumlah masalah teoretik-bilangan lainnya yang menjadi penghambat dalam Algoritma saat ini anjak piutang. $Z_n$

Adapun konsekuensi praktis, transaksi perbankan mungkin tidak terlalu menjadi masalah - begitu diketahui bahwa anjak piutang ada di P, bank akan beralih ke beberapa sistem lain, mungkin hanya menyebabkan periode penundaan yang singkat sementara ini sedang dilakukan. diimplementasikan. Decoding transaksi perbankan masa lalu mungkin tidak akan menimbulkan masalah serius bagi bank. Masalah yang jauh lebih serius adalah bahwa semua komunikasi yang sebelumnya dilindungi oleh RSA sekarang akan dalam bahaya dibaca.

Peter Shor
sumber

Agak di luar topik, tetapi as soon as it was known that factoring was in P, the banks would switch to some other systemsebagian besar angan-angan. Saya menemukan pada bulan Desember bahwa perusahaan yang tidak melakukan apa pun kecuali memproses rincian kartu kredit menggunakan varian Vigenère dengan kunci yang lebih pendek daripada beberapa versi plaintext yang dikenal. Lebih buruk lagi, direktur teknis perusahaan tidak akan percaya saya bahwa itu tidak aman sampai saya mengiriminya beberapa kode serangan. MD5, meskipun secara luas dianggap rusak, masih banyak digunakan dalam perbankan.

Peter Taylor

@PeterTaylor, segera setelah diketahui bahwa anjak piutang berada di P, bank-bank akan beralih ke beberapa sistem lainnya adalah angan-angan ". Dengan harga murah memori Flash saat ini, sangat layak untuk membuat solusi One Time Pad untuk perbankan, pengguna akan pergi dari waktu ke waktu ke ATM untuk mengunduh byte acak tambahan. RSA hanya lebih murah dan lebih sederhana.

Flávio Botelho

Memiliki sandi simetris yang kuat bukanlah pengganti untuk sandi asimetrik, meskipun cukup untuk tugas-tugas spesifik tertentu. Anda mengalami masalah karena tidak bisa menggunakan tanda tangan digital, dll.

Joe Fitzsimons

Sebenarnya Anda dapat memiliki tanda tangan digital dengan sandi simetris! Itu hanya jauh lebih rumit dan Anda perlu lebih percaya diri pada pihak ke-3 yang tepercaya. Lihatlah Buku Pegangan bab Kriptografi Terapan 11.6 dan 11.7.

Flávio Botelho

@ Flavio: Tapi penolakan adalah tidak bekerja dengan cara yang sama, bukan?

Joe Fitzsimons

RSA adalah salah satu skema enkripsi / tanda tangan paling penting yang rusak jika FACTORING ada di P. Namun, ada banyak lagi. Beberapa (tetapi tidak semua) dari mereka didasarkan pada asumsi bahwa kuadrat membedakan dan modulo non-kuadrat angka komposit sulit :

Dan banyak skema lainnya. Namun, perhatikan bahwa skema yang didasarkan pada kekerasan log diskrit (katakanlah, protokol Diffie-Helmann atau skema enkripsi / tanda tangan Elgamal ) akan tetap aman.

MS Dousti
sumber

Tampaknya sangat mungkin bagi saya bahwa jika anjak dalam P, maka demikian juga masalah log diskrit. Tentu saja kebalikannya benar.

Joe Fitzsimons

@ Jo: Saya punya perasaan yang sama, tetapi apakah ada bukti atau bukti matematika?

MS Dousti

Ada bukti mudah dari kebalikannya, karena . Ambil . Jadi jika dan , maka , dan , dan Anda memiliki faktor Anda. Saya tidak berpikir ada bukti yang diketahui tentang kebalikannya, tetapi saya mungkin salah. Either way, keduanya adalah contoh dari masalah subkelompok tersembunyi abelian, dan dihubungkan melalui teorema Euler, jadi ada kesamaan.

a^{p q} \equiv a^{p + q - 1} (mod p q)

$a^{pq} \equiv a^{p+q-1}~(\mbox{mod } pq)$

c_{a} = \log_{N} (a^{N} mod N)

$c_a = \log_N(a^N \mbox{mod }N)$

p = x + y

$p = x + y$

q = x - y

$q = x - y$

x = \frac{c_{a} + 1}{2}

$x = \frac{c_a + 1}{2}$

y = \sqrt{x^{2} - N}

$y = \sqrt{x^2 - N}$

Joe Fitzsimons

@ Jo: Sangat menarik! Komentar Anda memotivasi saya untuk menggali lebih dalam hal ini, dan menemukan hasil oleh Eric Bach yang menyatakan bahwa " memecahkan masalah logaritma diskrit untuk modulus komposit sama sulitnya dengan memfaktorkan dan menyelesaikannya modulo primes. "

MS Dousti

Crypto berbasis kisi semoga tetap aman.

Antimony

Konsekuensi utama dari Anjak berada di adalah bahwa perkalian (dua bilangan bulat ukuran yang sama) bukan fungsi satu arah. Ini akan menjadi hasil yang sangat mengejutkan karena perkalian diyakini sebagai kandidat terkuat untuk fungsi satu arah. Namun, ini mungkin tidak mengubah gambar kelas kompleksitas. $P$

Mohammad Al-Turkistany
sumber