PPAD dan Quantum

Hari ini di New York dan di seluruh dunia Ulang tahun Christos Papadimitriou dirayakan. Ini adalah kesempatan yang baik untuk bertanya tentang hubungan antara PPAD kelas kompleksitas Christos (dan kelas terkait lainnya) dan komputer kuantum. Dalam makalahnya yang dirayakan tahun 1994, Papadimitriou memperkenalkan dan secara sistematis mempelajari beberapa kelas kompleksitas penting seperti PLS, PPAD, dan lainnya. (Makalah Papadimitriou mengandalkan beberapa makalah sebelumnya dan, khususnya, seperti yang dicatat Aviad, PLS diperkenalkan oleh Johnson-Papadimitriou-Yannakakis pada tahun 1988.)

Pertanyaan utama saya adalah:

Apakah komputer kuantum memberikan beberapa keuntungan bagi masalah di $PPAD$ ? atau dalam $PLS$ ? atau dalam $PLS \cap PPAD$ ? dll ...

Pertanyaan lain adalah apakah ada beberapa analog kuantum dari PLS dan PPAD dan kelas Christos lainnya.

Saya perhatikan bahwa hubungan luar biasa baru-baru ini PPAD dengan kriptografi ditemukan dalam makalah ini: Pada kekerasan kriptografi menemukan keseimbangan Nash oleh N Bitansky, O Paneth, A Rosen dan Dapatkah kekerasan PPAD didasarkan pada asumsi kriptografi standar? oleh A Rosen, G Segev, I Shahaf, dan Menemukan Keseimbangan Nash Tidak Lebih Mudah Daripada Memecah Fiat-Shamir oleh Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum. Saya juga mencatat bahwa menurut pendapat saya, kelas Christos sangat dekat dengan matematika dan bukti matematika.

Pembaruan: Ron Rothblum berkomentar (lebih dari FB) bahwa hasil Choudhuri, Hubacek, Kamath, Pietrzak, Rosen, dan Rothblum menyiratkan bahwa PPAD masuk akal di luar kekuatan komputer kuantum. (Saya akan senang melihat jawaban yang rumit menjelaskannya.)

$n$$PLS$$PPAD$$LP$

Selamat ulang tahun, Christos!

Dua jawaban yang saya pelajari saat menulis posting blog tentang pertanyaan ini

1. Tidak : Dalam varian kotak hitam, kompleksitas kueri / komunikasi kuantum menawarkan percepatan kuadrat Grover, tetapi tidak lebih dari itu. Seperti yang ditunjukkan oleh Ron, ini mencakup kompleksitas komputasi dengan asumsi yang masuk akal.

2. Mungkin : Ekuilibrium Nash bisa dibilang masalah utama "kelas Christos". Di sini, memberikan pemain akses ke keterikatan kuantum menyarankan konsep solusi baru "kesetimbangan berkorelasi kuantum" yang menggeneralisasi kesetimbangan Nash. Kompleksitasnya masih terbuka. Lihat makalah keren ini oleh Alan Deckelbaum.

Dan satu catatan sejarah: PLS sebenarnya diperkenalkan oleh Johnson-Papadimitriou-Yannakakis pada tahun 1988 .

$\mathsf{PPAD}$

Pada level tinggi, CHKPRR membangun distribusi melalui instance end-of-line di mana menemukan solusi diperlukan untuk:

• mematahkan kesehatan sistem bukti yang diperoleh dengan menerapkan heuristik Fiat-Shamir ke protokol sumcheck yang terkenal, atau
• $\sharp \mathsf{P}$

$\sharp \mathsf{SAT}$$\mathsf{PPAD}$

$\sum_{\vec z \in \{0,1\}^n} f(\vec z) = x$$f$$n$$\mathbb{F}$, yang akan bekerja dengan baik dalam pengaturan ini: protokol sumcheck . Mengubah bukti interaktif menjadi bukti non-interaktif (menjaga kebenaran dan kekompakan publik) adalah persis seperti yang dilakukan heuristik Fiat-Shamir.

Instantiating Fiat-Shamir

Heuristik Fiat-Shamir sangat sederhana: perbaiki beberapa fungsi hash, mulai dengan bukti interaktif publik-koin, dan ganti setiap pesan acak verifier dengan hash seluruh transkrip sejauh ini. Pertanyaannya adalah kemudian di mana properti dari fungsi hash kita dapat membuktikan bahwa protokol yang dihasilkan masih sehat (perhatikan bahwa itu tidak dapat secara statistik lagi sehat; harapannya adalah bahwa itu tetap baik secara komputasi).

Sebelum saya menguraikan ini, izinkan saya menjawab komentar Anda:

Saya masih tidak mengerti 1. Tentu saja ada asumsi kekerasan kriptografis yang tidak berlaku dalam kasus kuantum. Apa yang membuat "melanggar Fiat-Shamir" sulit untuk QC tidak seperti, katakanlah "melanggar RSA".

Deskripsi tingkat tinggi yang saya berikan harus menjelaskan, saya harap, bahwa "melanggar Fiat-Shamir" dan "melanggar RSA" bukan masalah yang benar-benar sebanding. RSA adalah asumsi kekerasan yang spesifik dan spesifik, dan jika Anda dapat memfaktorkan bilangan bulat besar, maka Anda dapat mematahkannya.

$\mathsf{PPAD}$dari fungsi hash yang mendasarinya. Pada tingkat intuitif, ini bukan komputer kuantum yang baik, karena ini adalah masalah yang tampaknya tidak selalu memiliki struktur yang kuat yang dapat dieksploitasi (tidak seperti, misalnya, logaritma diskrit dan RSA): fungsi hash biasanya dapat sangat "tidak terstruktur".

Dalam istilah yang lebih konkret, ada dua alternatif alami ketika memilih fungsi hash untuk membuat Instansiate Fiat-Shamir:

Pendekatan heuristik, efisien secara konkret:

pilih fungsi hash favorit Anda, katakanlah, SHA-3. Kami tentu saja tidak memiliki bukti bahwa instantiating Fiat-Shamir dengan SHA-3 memberi kita masalah yang sulit; tetapi kita juga tidak tahu adanya serangan non-sepele terhadap kesehatan sistem bukti yang diperoleh dengan menerapkan Fiat-Shamir dengan SHA-3 ke sistem bukti interaktif non-degenerasi. Ini meluas ke pengaturan kuantum juga: kita tidak tahu adanya serangan kuantum yang melakukan lebih baik daripada speedup kuadratik biasa yang diberikan oleh algoritma Grover. Setelah beberapa dekade upaya cryptanalysis, konsensus dalam komunitas kriptografi adalah bahwa algoritma kuantum tampaknya tidak , sejauh yang dapat kita lihat, untuk memberikan percepatan superpolynomial untuk primitif "Minicrypt-style" (fungsi hash, PRGs, block ciphers, dll) tanpa beberapa struktur aljabar kuat yang mendasarinya - seperti SHA-2, SHA-3, AES, dll.

Pendekatan keamanan yang terbukti:

di sini tujuannya adalah untuk mengisolasi properti bersih dari fungsi hash yang membuat suara heatistik Fiat-Shamir, dan untuk membangun fungsi hash yang memenuhi properti ini berdasarkan asumsi kriptografi yang masuk akal.

$R$$K$$x$$(x, H_K(x)) \in R$$R$$R$

Pertanyaannya sekarang adalah bagaimana membangun fungsi hash yang tidak dapat dipecah-belah untuk hubungan yang kita pedulikan - dan dalam konteks khusus ini, untuk hubungan yang terkait dengan protokol pemeriksaan balik. Di sini, garis pekerjaan baru-baru ini (pada dasarnya 1 , 2 , 3 , 4 , 5 , 6 ) telah menunjukkan bahwa, bagi banyak hubungan yang menarik, seseorang dapat benar-benar membangun fungsi hash yang tidak dapat dielakkan berdasarkan asumsi berbasis kisi.

$\mathsf{PPAD}$

Kita sebenarnya tidak ada di sana. Hasil terobosan terbaru dari Peikert dan Shiehian (makalah terakhir dalam daftar yang saya berikan sebelumnya) menunjukkan bahwa untuk hubungan penting, kita dapat membangun fungsi hash yang tidak dapat dikorelasikan dalam masalah kisi yang sudah mapan, seperti belajar dengan kesalahan, atau masalah SIS ; Namun, hubungan sumcheck tidak ditangkap oleh karya ini.

Namun, CHKPRR, yang membangun karya ini menunjukkan bahwa seseorang dapat membangun fungsi hash yang tidak dapat dikorelasikan dengan asumsi bahwa salah satu dari banyak konstruksi konkrit dari skema enkripsi yang sepenuhnya homomorfik memiliki keamanan melingkar yang cukup optimal terhadap serangan waktu superpolinomial.

Mari kita uraikan asumsi ini:

• Enkripsi sepenuhnya homomorfis (FHE) adalah primitif yang kita tahu bagaimana membangun di bawah berbagai asumsi kisi. Jika skema hanya harus mengevaluasi sirkuit ukuran terbatas, kita tahu sebenarnya bagaimana membangunnya di bawah pembelajaran standar dengan asumsi kesalahan.
• Keamanan sirkular menyatakan bahwa FHE harus sulit dipecahkan bahkan ketika digunakan untuk mengenkripsi kunci rahasianya sendiri. Ini lebih kuat dari dugaan keamanan yang biasa, yang tidak memungkinkan pesan-pesan yang bergantung pada kunci. Ini adalah masalah besar dan lama berdiri untuk membangun FHE-aman melingkar di bawah asumsi kisi standar, seperti LWE. Namun, satu dekade setelah konstruksi FHE pertama Gentry dan banyak upaya cryptanalysis, keamanan melingkar kandidat FHE yang mapan telah menjadi asumsi yang relatif aman (bahkan terhadap komputer kuantum), dan kami tidak mengetahui adanya serangan yang mengeksploitasi kunci Enkripsi -dependen dengan cara nontrivial.
• $2^{\omega(\log \lambda) - \lambda}$$\lambda$$2^{c\lambda}$$c < 1$$2^{-c \lambda}$$c < 1$
• Akhirnya, kami ingin semua hal di atas tetap berlaku jika kami mengizinkan waktu lari superpolinomial ke penyerang. Ini masih sejalan dengan apa yang dapat dicapai algoritma yang dikenal.

$\mathsf{PPAD}$

Tentu saja, salah satu pertanyaan terbuka utama yang ditinggalkan oleh CHKPRR adalah untuk membangun fungsi hash yang tidak dapat dikoreksi untuk hubungan sumcheck di bawah asumsi berbasis kisi yang lebih baik - idealnya, asumsi LWE. Ini tampaknya tidak sepele, tetapi tidak tidak masuk akal, mengingat bahwa ini adalah pekerjaan yang sangat baru, di mana banyak hasil mengejutkan telah dicapai untuk hubungan menarik lainnya.