Zastosowania XORification

XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k . $x$$k\geq 2$$x_1 \oplus \ldots \oplus x_k$

Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu uzyskania niższych granic przestrzeni dla systemów dowodu opartych na rozdzielczości, np. W pracy:

• Eli Ben-Sasson. Kompromisy przestrzeni wielkości dla rozdzielczości. STOC 2002, 457-464.
• Eli Ben-Sasson i Jakob Nordström. Zrozumienie przestrzeni w dowodowej złożoności: separacje i kompromisy poprzez zamiany. ICS 2011, 401–416.

Czy istnieją inne zastosowania tej techniki w innych obszarach?

Oto dość istotny przykład, który obecnie omawiamy w mojej klasie.

„Funkcja dostępu do pamięci” jest zdefiniowana dla bitów jako:$2^k+k$

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

gdzie jest unikalną liczbą całkowitą w { 1 , … , 2 k } odpowiadającą ciągowi 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)}$.

This is often called "Andreev's function" in the literature. Hastad proved (improving a component of Andreev's argument) that cubic-size formulas are essentially necessary. (It is not hard to find nearly cubic-size formulas for it, too.)

Może to być niewielki zasięg, ale w kryptografii pojawia się pomysł XOR'owania wielu rzeczy, aby uczynić zadanie „trudniejszym”. Po raz pierwszy pojawił się pod postacią lematu XOR Yao . Gdyby$X$ jest więc nieco nieprzewidywalną zmienną losową $Y = X_1 \oplus X_2 \oplus \cdots \oplus X_k$ jest wyjątkowo nieprzewidywalny, jeśli $k$ is large enough, where the $X_i$'s are independent draws of $X$.

Nowadays, this technique is quite standard in crypto, typically for amplifying a weak construction (commitment scheme, oblivious transfer protocol, etc) into a strong one.