XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k .
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?
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= X1⊕ X2)⊕ ⋯ ⊕ 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.
źródło