Toward Provable One Way Functions

Hagar Dolev; Shlomi Dolev

Paper 2020/1358 Original: eprint.iacr.org/2020/1358 ↗

Toward Provable One Way Functions

Hagar Dolev

Shlomi Dolev

Abstract

The existence of a provable one-way function is a long-standing open problem. This short note presents an example towards the existence a provable one-way function, example in which both directions are polynomial. Namely, we prove that given a sorted array it takes O(n) operations to randomly permute the array values uniformly over the permutation space, while (comparison based) sorting of the permuted array (of big enough values) requires in the worst case (and in the average case) Omega(n log n) compare operations . We also present a candidate cryptosystem based on permutations of random polynomial values.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
History: 2020-10-29: last updated; 2020-10-29: published
Short URL: https://ia.cr/2020/1358
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2020/1358,
      author = {Hagar Dolev and Shlomi Dolev},
      title = {Toward Provable One Way Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1358},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1358}
}