Amplifying the Security of One-Way Functions -- A Proof of Yao's XOR-Lemma

Damm, Frank and Heider, Franz-Peter (1996) Amplifying the Security of One-Way Functions -- A Proof of Yao's XOR-Lemma.
Technical Report , 13 p.

Abstract

In this paper we give a consistent and simple proof for the XOR-Lemma which was hinted at by Yao and subsequently presented by him in lectures. It can be found in print in "E. Kranakis, Primality and Cryptography, Wiley-Teubner Series in Computer Science, 1986". By the lemma we know that the security of any one-way function f:Xlongrightarrow { 0,1} can be substantially amplified if the function is replaced by the XOR with itself, namely by foplus f:X imes Xlongrightarrow { 0,1}, (x,y)longrightarrow f(x)oplus f(y). Applications are in cryptography and complexity theory. However, the existence of one-way functions still remains an open problem.


Actions:
Download: [img] Postscript
Download (150Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-240
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/240