Verwendung von XORification

XORification ist die Technik, um eine Boolesche Funktion oder Formel zu erschweren, indem jede Variable durch das XOR von k ≥ 2 verschiedenen Variablen x 1 ⊕ … ⊕ x k ersetzt wird . $x$$k\geq 2$$x_1 \oplus \ldots \oplus x_k$

Ich bin mir bewusst, dass diese Technik bei der Komplexität von Beweisen eingesetzt wird, hauptsächlich, um Raumuntergrenzen für auflösungsbasierte Beweissysteme zu erhalten, z. B. in den Abhandlungen:

• Eli Ben-Sasson. Größenkompromisse für die Auflösung. STOC 2002, 457-464.
• Eli Ben-Sasson und Jakob Nordström. Raum in der Beweiskomplexität verstehen: Trennungen und Kompromisse durch Substitutionen. ICS 2011, 401-416.

Gibt es andere Anwendungen dieser Technik in anderen Bereichen?

Hier ist ein etwas relevantes Beispiel, das wir derzeit in meiner Klasse behandeln.

Die "Speicherzugriffsfunktion" ist für Bits definiert als:$2^k+k$

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

Dabei ist die eindeutige Ganzzahl in { 1 , … , 2 k } , die der Zeichenfolge a $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$ an jedem Eingang . Dann UND jedes Bit$x_i$ mit dem Ausgang der entsprechenden Gruppe, dann ODER alle diese Ausgänge.

$2^{k+1}$$2^{3k}$ Formeln mit einer Größe von über AND / OR / NOT:

$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.)

This might be a slight reach, but the idea of XOR'ing a bunch of things to make a task "harder" shows up in cryptography. It first appeared in the guise of Yao's XOR lemma. If $X$ is a slightly unpredictable random variable, then $Y = X_1 \oplus X_2 \oplus \cdots \oplus X_k$ is extremely unpredictable if $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.