Apakah mungkin mengenkripsi CNF?

Apakah mungkin untuk mengubah CNF menjadi CNF lain sedemikian rupa $\mathcal C$ $\Psi(\mathcal C)$

Fungsi dapat dihitung dalam waktu polinomial dari beberapa parameter acak rahasia . $\Psi$ $r$
memiliki solusi jika dan hanya jika memiliki solusi. $\Psi(\mathcal C)$ $\mathcal C$
Setiap solusi dari dapat secara efisien dikonversi menjadi solusi menggunakan . $x$ $\Psi(\mathcal C)$ $\mathcal C$ $r$
Tanpa , solusi (atau properti lainnya dari ) tidak memberikan bantuan dalam memecahkan . $r$ $x$ $\Psi(\mathcal C)$ $\mathcal C$

Jika ada seperti itu , maka dapat digunakan untuk membuat orang lain memecahkan tantangan komputasi bagi kita (dengan kemungkinan mengganti memecahkan CNF dengan masalah lain - saya memilih CNF karena saya ingin membuat masalah lebih spesifik), sedemikian rupa bahwa mereka tidak dapat mengambil untung dari solusi yang mungkin bahkan jika mereka tahu masalah apa yang telah kita gunakan untuk menyelesaikannya. Sebagai contoh, kita dapat menanamkan masalah faktorisasi ke dalam permainan komputer, yang memungkinkan pemain untuk bermain hanya jika mereka mengatasi masalah kita di latar belakang, dari waktu ke waktu mengirim kembali bukti perhitungan. Mungkin perangkat lunak bahkan dapat dibuat "gratis" dengan cara ini, di mana "gratis" menyembunyikan biaya (mungkin lebih tinggi) dalam tagihan listrik orang tua Anda. $\Psi$

cc.complexity-theory cr.crypto-security one-way-function cryptojacking domotorp
sumber

Typo "... tidak memberikan bantuan apa pun dalam menyelesaikan

"? By the way, jika Anda tidak khawatir tentang struktur

yaitu "pemain" tidak memiliki akses ke

tetapi hanya untuk solusi

, maka permutasi acak sederhana dari tanda variabel (

) dan permutasi acak dari indeks dari variabel harus membuat solusi

dari

benar-benar tidak dapat digunakan untuk memecahkan

C

$\mathcal C$

Ψ

$\Psi$

Ψ (C)

$\Psi(\mathcal C)$

x

$x$

π_{ℓ} (ℓ_{i}) = \pm ℓ_{i}

$\pi_{\ell}(\ell_i) = \pm \ell_i$

x

$x$

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

Marzio De Biasi

@ Marszio Thx, kesalahan ketik tetap. Tapi saya tidak mengerti komentar Anda - apakah Anda berasumsi bahwa "pemain" tidak memiliki akses ke

tetapi hanya untuk

? Itu harus jelas dari deskripsi yang dia miliki.

Ψ (C)

$\Psi(\mathcal C)$

x

$x$

domotorp

ya sederhana "mengocok literal dan indeks variabel" pasti bekerja jika pemain tidak memiliki akses ke struktur

(saya adalah hanya komentar singkat). Tapi mungkin ide "shuffle" dapat diperluas dengan cara ini: jika

adalah 3-CNF maka hanya ada

kemungkinan klausa yang berbeda dan mengetahui

(versi

dikocok ) hanya bisa membantu jika mengetahui cara yang efisien untuk menemukan isomorfisma antara

dan

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

(2 n)^{3}

$(2n)^3$

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

Marzio De Biasi

@ Marszio Saat semuanya sedang menuju, mungkin (hiper) graphisomorphism cepat dipecahkan.

domotorp

Lihat konjektur set lengkap terenkripsi. Itu menunjukkan bahwa proposal Anda masuk akal. Ini menyatakan bahwa ada injeksi panjang

fungsi satu arah yang aman

sehingga SAT dan

tidak p-isomorfik.

2^{n^{ϵ}}

$2^{n^\epsilon}$

f

$f$

f (S A T)

$f(SAT)$

Mohammad Al-Turkistany

Jawaban:

Feigenbaum in, Encrypting Problem Instances , mengusulkan definisi (Def. 1) fungsi enkripsi untuk masalah NP-complete yang memenuhi kebutuhan Anda. Dia membuktikan bahwa masalah NP-komparatif Ketidaksetaraan Vektor Komparatif mengakui fungsi enkripsi tersebut. Dia menyimpulkan dengan teorema utama bahwa semua masalah NP-lengkap yang p-isomorfik ke CNF-SAT dapat dienkripsi.

Mohammad Al-Turkistany
sumber

Dan dalam tindak lanjut mereka menyimpulkan bahwa masalah NP-complete tidak mungkin dienkripsi! doi.org/10.1016/0022-0000(89)90018-4 Koran-koran ini hanya apa yang saya cari. Saya bertanya-tanya mengapa saya dapat memahaminya jauh lebih baik daripada hasil terbaru dalam kriptografi - mungkin bidang ini telah menyimpang terlalu banyak dari teori kompleksitas sejak saat itu ...

domotorp

Aplikasi yang Anda sebutkan disebut "bukti kerja bermanfaat" dalam literatur, lihat misalnya artikel ini .

Anda dapat menggunakan skema enkripsi homomorfik sepenuhnya (di mana teks teks adalah contoh CNF) untuk mendelegasikan perhitungan kepada pihak yang tidak dipercaya tanpa mengungkapkan input.

Ini tidak menjawab pertanyaan Anda dengan tepat, karena skema semacam itu tidak memetakan CNF ke CNF lain, tetapi itu berfungsi untuk aplikasi yang dimaksud.

Diego de Estrada
sumber

Afaik, enkripsi homomorfik adalah untuk membuat perhitungan pada beberapa angka. Bagaimana tepatnya Anda menggunakannya untuk masalah saya?

domotorp

FHE didefinisikan untuk sirkuit boolean. Perlakukan instance CNF sebagai vektor bit. Diberikan ukuran input, Anda dapat membuat sirkuit boolean yang menampilkan tugas jika ada (lihat cs.stackexchange.com/q/72289/627 ).

Diego de Estrada

Saya pikir perbedaannya ada pada solusi Anda, sementara privasi tetap terjaga, pengodeannya cukup mahal dibandingkan dengan tugas yang ingin kami selesaikan. Saya ingin menyandikan dalam waktu polinomial jumlah pekerjaan yang eksponensial.

domotorp

@domotorp saya mengerti. Ada cara untuk menggunakan FHE tanpa sirkuit, lihat eprint.iacr.org/2013/229.pdf

Diego de Estrada

Karena semakin banyak pengguna meningkatkan jawaban Anda, mungkin itu berisi sesuatu yang saya lewatkan. Apakah Anda mengklaim saat ini berfungsi untuk pertanyaan saya atau hanya untuk aplikasi? Saya juga sudah melihat kertasnya, tetapi tidak mudah untuk dipahami. Bisakah Anda memberi tahu saya hasil / teorema spesifik mana yang dapat diterapkan dalam kasus saya?

domotorp