Usos da XORification

18

XORification é a técnica para dificultar uma função ou fórmula booleana substituindo cada variável pelo XOR de variáveis ​​distintas . xk2x1xk

Estou ciente dos usos dessa técnica na complexidade de provas, principalmente para obter limites inferiores de espaço para sistemas de provas baseados em resolução, por exemplo, nos documentos:

  • Eli Ben-Sasson. Dimensione as trocas de espaço para resolução. STOC 2002, 457-464.
  • Eli Ben-Sasson e Jakob Nordström. Entendendo o espaço na complexidade da prova: separações e trade-offs por substituições. ICS 2011, 401-416.

Existem outros usos dessa técnica em outras áreas?

Jan Johannsen
fonte

Respostas:

15

Aqui está um exemplo um tanto relevante que estamos cobrindo atualmente em minha turma.

A "função de acesso ao armazenamento" é definida em bits como:2k+k

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

em que é o número inteiro único em correspondente à sequência .bin(a1ak){1,,2k}a1ak

O ( k 2 k ) 2 k k a i 1 x iSA possui fórmulas de tamanho sobre sobre AND / OR / NOT: possui grupos de todos os -ANDs possíveis sobre as variáveis , de modo que exatamente um grupo produz em cada entrada. Então AND cada bit com a saída do grupo correspondente, ou OR todas essas saídas.O(k2k)2kkai1xEu

No entanto, a seguinte função "SA do XOR", em entradas, requer cerca de fórmulas de tamanho sobre AND / OR / NOT: 2 3 k2k+123k

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

Isso costuma ser chamado de "função de Andreev" na literatura. Hastad provou (melhorando um componente do argumento de Andreev) que fórmulas de tamanho cúbico são essencialmente necessárias. (Também não é difícil encontrar fórmulas de tamanho cúbico para isso.)

Ryan Williams
fonte
Obrigado Ryan, esse é exatamente o tipo de coisa que eu estava procurando.
Jan Johannsen 21/11
13

XY=X1X2XkkXEuX

Atualmente, essa técnica é bastante padrão em criptografia, normalmente para amplificar uma construção fraca (esquema de consolidação, protocolo de transferência inconsciente, etc.) em uma estrutura forte.

mikero
fonte
5
Para complementar este post: os lemas do XOR estão em toda parte. Por exemplo, veja este artigo e suas referências: theoryofcomputing.org/articles/v004a007
MCH
2
kkkk