One-Way Functions and Local Descriptions of Random DataResearch Paper
A one-way function is a map that is easy to evaluate and hard to invert on a random input. Its existence is the minimal assumption of private-key cryptography, and it is not known to follow from . A line of work started by Liu and Pass (arXiv:2009.11514) characterizes one-way functions by meta-complexity: the average-case hardness…