Utilisations de XORification

18

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 1x k . xk2x1xk

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?

Jan Johannsen
la source

Réponses:

15

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:2k+k

SA(x1,...,x2k,a1,...,ak)=xbin(a1ak)

est l'entier unique dans { 1 , , 2 k } correspondant à la chaîne a 1a k .bin(a1ak){1,,2k}a1ak

a des formules de taille environ O ( k 2 k ) sur AND / OR / NOT: avoir 2 k groupes de tous les k possiblesSAO(k2k)2kk -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.ai1xi

Cependant, la fonction "SA of XOR" suivante, sur les entrées , nécessite environ 2 formules de taille 3 k sur AND / OR / NOT:2k+123k

.SA(x1,...,x2k,j=12k/ka1,j,...,j=12k/kak,j)=xbin(a1ak)

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

Ryan Williams
la source
Merci Ryan, c'est exactement le genre de chose que je cherchais.
Jan Johannsen
13

XY=X1X2XkkXiX

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.

mikero
la source
5
Pour compléter cet article: les lemmes XOR sont partout. Par exemple, voir cet article et ses références: theoryofcomputing.org/articles/v004a007
MCH
2
kkkk