Counterexample to OWF Self-XOR Being a DOWF

Nathan Geier

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

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: one-way functions distributional one-way functions XOR
Contact author(s): nathangeier @ mail tau ac il
History: 2021-09-24: received
Short URL: https://ia.cr/2021/1275
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1275,
      author = {Nathan Geier},
      title = {Counterexample to {OWF} Self-{XOR} Being a {DOWF}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1275},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1275}
}