Utilisations de XORification

La XORification est la technique pour rendre plus difficile une fonction ou une formule booléenne en remplaçant chaque variable par le XOR de k ≥ 2 variables distinctes x 1 ⊕ … ⊕ x k . $x$$k\geq 2$$x_1 \oplus \ldots \oplus x_k$

Je connais les utilisations de cette technique dans la complexité de la preuve, principalement pour obtenir des limites inférieures d'espace pour les systèmes de preuve basés sur la résolution, par exemple dans les articles:

• Eli Ben-Sasson. Taille des compromis d'espace pour la résolution. STOC 2002, 457-464.
• Eli Ben-Sasson et Jakob Nordström. Comprendre l'espace dans la complexité de la preuve: séparations et compromis via les substitutions. ICS 2011, 401-416.

Y a-t-il d'autres utilisations de cette technique dans d'autres domaines?

Voici un exemple quelque peu pertinent que nous couvrons actuellement dans ma classe.

La "fonction d'accès au stockage" est définie sur bits comme:$2^k+k$

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

où est l'entier unique dans { 1 , … , 2 k } correspondant à la chaîne a 1 ⋯ a k .$bin(a_1 \cdots a_k)$$\{1,\ldots,2^k\}$$a_1 \cdots a_k$

a des formules de taille environ O ( k ⋅ 2 k ) sur AND / OR / NOT: avoir 2 k groupes de tous les k possibles$SA$$O(k \cdot 2^k)$$2^k$$k$ -ANDs sur les des variables, de sorte que exactement une des sorties du groupe 1 sur chaque entrée. Puis ET chaque bit x i avec la sortie du groupe correspondant, puis OU toutes ces sorties.$a_i$$1$$x_i$

Cependant, la fonction "SA of XOR" suivante, sur les entrées , nécessite environ 2 formules de taille 3 k sur AND / OR / NOT:$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)}$

Ceci est souvent appelé "la fonction d'Andreev" dans la littérature. Hastad a prouvé (améliorant une composante de l'argument d'Andreev) que les formules de taille cubique sont essentiellement nécessaires. (Il n'est pas difficile non plus de trouver des formules presque cubiques.)

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

De nos jours, cette technique est assez standard en crypto, généralement pour amplifier une construction faible (schéma d'engagement, protocole de transfert inconscient, etc.) en une construction forte.