Communications of the ACM
Research Archive
The Research archive provides access to all Research articles published in past issues of Communications of the ACM.
May 2023
From Communications of the ACM
Toward Basing Cryptography on the Hardness of EXP
We show that the only "gap" toward getting (infinitely-often) OWFs from the assumption that EXP ≠ BPP is the seemingly "minor" technical gap between two-sided error and errorless average-case hardness of the MKtP problem.
From Communications of the ACM
Technical Perspective: Finding Connections between One-Way Functions and Kolmogorov Complexity
"Toward Basing Cryptography on the Hardness of EXP," by Yanyi Liu and Rafael Pass, establishes surprisingly tight bidirectional connections between one-way functions and the cross-domain notion of Kolmogorov complexity.