Использование XORification

18

XORification - это метод усложнения булевой функции или формулы путем замены каждой переменной на XOR k 2 различных переменных x 1x k . xk2x1xk

Мне известно об использовании этого метода для усложнения доказательства, главным образом для получения нижних границ пространства для систем доказательства на основе разрешения, например, в статьях:

  • Эли Бен-Сассон. Размеры пространства компромиссы для разрешения. STOC 2002, 457-464.
  • Эли Бен-Сассон и Якоб Нордстрем. Понимание пространства в сложности доказательств: разделения и компромиссы через замены. ICS 2011, 401-416.

Есть ли другие применения этой техники в других областях?

Ян Йоханнсен
источник

Ответы:

15

Вот несколько уместный пример, который мы сейчас рассматриваем в моем классе.

«Функция доступа к хранилищу» определяется для битов как:2k+k

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

где - единственное целое число в { 1 , , 2 k }, соответствующее строке a 1a k .bin(a1ak){1,,2k}a1ak

имеет формулы размером около O ( k 2 k ) над AND / OR / NOT: имеет 2 k групп всех возможных k -AND для переменных a i , так что ровно одна группа выводит 1 на каждый вход. Затем И каждый бит x i с выходом соответствующей группы, затем ИЛИ все эти выходы.SAO(k2k)2kkai1xi

Однако для следующей функции "SA of XOR" на входах требуются формулы размером примерно 2 3 k над AND / OR / NOT:2k+123k

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

В литературе это часто называют «функцией Андреева». Хастад доказал (улучшая компонент аргумента Андреева), что формулы кубического размера по существу необходимы. (Нетрудно также найти формулы почти кубического размера.)

Райан Уильямс
источник
Спасибо Райан, это именно то, что я искал.
Ян Йоханнсен
13

XY=X1X2XkkXiX

В настоящее время этот метод является довольно стандартным в криптографии, как правило, для усиления слабой конструкции (схема фиксации, забытый протокол передачи и т. Д.) В сильную.

mikero
источник
5
В дополнение к этому посту: XOR леммы везде. Например, см. Этот документ и его ссылки: theoryofcomputing.org/articles/v004a007
MCH
2
Лемма XOR отличается от того, что я ищу: здесь КНа выходе добавляется четность Ккопии функции подаются в нее. XORification, с другой стороны, добавляетК-все четность на каждом входе, с Кновые переменные вводятся в него.
Ян Йоханнсен