Zastosowania XORification

18

XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k 2 odrębnych zmiennych x 1x k . xk2x1xk

Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu uzyskania niższych granic przestrzeni dla systemów dowodu opartych na rozdzielczości, np. W pracy:

  • Eli Ben-Sasson. Kompromisy przestrzeni wielkości dla rozdzielczości. STOC 2002, 457-464.
  • Eli Ben-Sasson i Jakob Nordström. Zrozumienie przestrzeni w dowodowej złożoności: separacje i kompromisy poprzez zamiany. ICS 2011, 401–416.

Czy istnieją inne zastosowania tej techniki w innych obszarach?

Jan Johannsen
źródło

Odpowiedzi:

15

Oto dość istotny przykład, który obecnie omawiamy w mojej klasie.

„Funkcja dostępu do pamięci” jest zdefiniowana dla bitów jako:2)k+k

S.ZA(x1,...,x2)k,za1,...,zak)=xbjan(za1zak)

gdzie jest unikalną liczbą całkowitą w { 1 , , 2 k } odpowiadającą ciągowi a 1a k .bjan(za1zak){1,,2)k}za1zak

S.ZAO(k2)k)2)kkzaja1xi

2k+123k

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

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

Ryan Williams
źródło
Dzięki Ryan, właśnie tego szukałem.
Jan Johannsen
13

Może to być niewielki zasięg, ale w kryptografii pojawia się pomysł XOR'owania wielu rzeczy, aby uczynić zadanie „trudniejszym”. Po raz pierwszy pojawił się pod postacią lematu XOR Yao . GdybyX jest więc nieco nieprzewidywalną zmienną losową Y=X1X2)Xk jest wyjątkowo nieprzewidywalny, jeśli k is large enough, where the Xi'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.

mikero
źródło
5
To complement this post: XOR lemmas are everywhere. Eg, see this paper and its references: theoryofcomputing.org/articles/v004a007
MCH
2
The XOR lemma is different from what I look for: here a k-ary parity gate is added at the output, with kwprowadzono do niej kopie funkcji. Z drugiej strony XORification dodajek-aryjna bramka parzystości na każdym wejściu, z kwprowadzono do niego nowe zmienne.
Jan Johannsen