Penggunaan XORification

XORifikasi adalah teknik untuk membuat fungsi atau rumus Boolean lebih sulit dengan mengganti setiap variabel dengan XOR k ≥ 2 variabel berbeda x 1 ⊕ … ⊕ x k . $x$$k\geq 2$$x_1 \oplus \ldots \oplus x_k$

Saya menyadari penggunaan teknik ini dalam kompleksitas bukti, terutama untuk mendapatkan ruang batas bawah untuk sistem bukti berbasis resolusi, misalnya, dalam makalah:

• Eli Ben-Sasson. Ukuran pengorbanan ruang untuk resolusi. STOC 2002, 457-464.
• Eli Ben-Sasson dan Jakob Nordström. Memahami Ruang dalam Kompleksitas Bukti: Pemisahan dan Pertukaran melalui Substitusi. ICS 2011, 401-416.

Apakah ada kegunaan lain dari teknik ini di daerah lain?

Inilah contoh yang agak relevan yang saat ini kami bahas di kelas saya.

"Fungsi akses penyimpanan" didefinisikan pada bit sebagai:$2^k+k$

$SA(x_1,...,x_{2^k}, a_1,...,a_k) = x_{bin(a_1 \cdots a_k)}$

di mana adalah bilangan bulat unik dalam { 1 , … , 2 k } yang sesuai dengan string a 1 ⋯ a k .$bin(a_1 \cdots a_k)$$\{1,\ldots,2^k\}$$a_1 \cdots a_k$

$SA$$O(k \cdot 2^k)$$2^k$$k$$a_i$$1$$x_i$

$2^{k+1}$$2^{3k}$

$SA(x_1,...,x_{2^k}, \bigoplus_{j=1}^{2^k/k} a_{1,j},..., \bigoplus_{j=1}^{2^k/k} a_{k,j}) = x_{bin(a_1 \cdots a_k)}$

Ini sering disebut "fungsi Andreev" dalam literatur. Hastad membuktikan (memperbaiki komponen argumen Andreev) bahwa formula ukuran kubik pada dasarnya diperlukan. (Tidak sulit untuk menemukan formula ukuran hampir kubik untuk itu juga.)

$X$$Y = X_1 \oplus X_2 \oplus \cdots \oplus X_k$$k$$X_i$$X$

Saat ini, teknik ini cukup standar dalam crypto, biasanya untuk memperkuat konstruksi yang lemah (skema komitmen, protokol transfer terlupa, dll) menjadi yang kuat.