Communications of the ACM

Latest Research

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... Gil Segev
From 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... Yanyi Liu, Rafael Pass
From Communications of the ACM | May 2023