Cryptology ePrint Archive: Report 2020/1358
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.
Category / Keywords: cryptographic protocols / one-way functions
Original Publication (with minor differences): CSCML 2020 Phd Track, Technical Report
Date: received 28 Oct 2020, last revised 28 Oct 2020
Contact author: shlomidolev at gmail com
Available format(s): PDF | BibTeX Citation
Note: Was presented in the PhD track of CSCML 2020
Version: 20201029:145939 (All versions of this report)
Short URL: ia.cr/2020/1358
[ Cryptology ePrint archive ]