[Resource Topic] 2020/1358: Toward Provable One Way Functions

Welcome to the resource topic for 2020/1358

Title:
Toward Provable One Way Functions

Authors: 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.

ePrint: https://eprint.iacr.org/2020/1358

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .