Cryptology ePrint Archive: Report 2021/1275

Counterexample to OWF Self-XOR Being a DOWF

Nathan Geier

Abstract: We study the effects of the XOR transformation, that is, $f^{\oplus 2}(x_1,x_2):= f(x_1)\oplus f(x_2)$, on one-wayness. More specifically, we present an example showing that if one-way functions exist, there also exists a one-way function $f$ such that $f^{\oplus 2}$ is not even a distributional one-way function, demonstrating that one-wayness may severely deteriorate.

Category / Keywords: foundations / one-way functions, distributional one-way functions, XOR

Date: received 22 Sep 2021

Contact author: nathangeier at mail tau ac il

Available format(s): PDF | BibTeX Citation

Version: 20210924:174912 (All versions of this report)

Short URL: ia.cr/2021/1275


[ Cryptology ePrint archive ]