### Toward Provable One Way Functions

Hagar Dolev and 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.

Note: Was presented in the PhD track of CSCML 2020

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.CSCML 2020 Phd Track, Technical Report
Keywords
one-way functions
Contact author(s)
shlomidolev @ gmail com
History
Short URL
https://ia.cr/2020/1358

CC BY

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},
note = {\url{https://eprint.iacr.org/2020/1358}},
url = {https://eprint.iacr.org/2020/1358}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.