Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

ePrint Report: Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass

Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption---the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity.
Roughly speaking, the promise problem requires telling apart tuples of strings $(\pi,x,y)$ with …

candidates complexity computational eprint report imply key pass protocols quantum report safe