This three-year, $1 million project grant from the National Science Foundation's Division of Computing and Communication Foundations, under the Computer and Information Science and Engineering program (CFDA 47.070), will support research exploring the theoretical underpinnings of one-way functions and their relationship to Kolmogorov complexity. Specifically, the principal investigator will further develop the established connection between the existence of one-way functions, which are necessary for most basic cryptographic building blocks, and the average-case hardness of problems related to time-bounded Kolmogorov complexity. This will include identifying additional natural problems whose average-case difficulty characterizes one-way functions, analyzing functions with additional structure relevant to advanced cryptographic primitives, and studying the possibility of basing cryptographic assumptions on the worst-case complexity of Kolmogorov-related problems. Taken together, the research aims to provide a stronger theoretical foundation for one-way functions and elucidate the extent to which standard complexity-theoretic assumptions could support their existence. The award was granted to Cornell University for performance at its Ithaca, New York campus.