TY - GEN

T1 - Kolmogorov Comes to Cryptomania

T2 - 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023

AU - Ball, Marshall

AU - Liu, Yanyi

AU - Mazor, Noam

AU - Pass, Rafael

N1 - Publisher Copyright:
© 2023 IEEE.

PY - 2023

Y1 - 2023

N2 - 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 (π, x, y) with relatively (w.r.t. K(π)) low time-bounded Interactive Kolmogorov Complexity (IKt), and those with relatively high Kolmogorov complexity, given the promise that Kt(x · y)< s, ~Kt(y · x)< s and s=log n, and where IKt(π ; x ; y) is defined as the length of the shortest pair of t-bounded TMs (A, B) such that the interaction of (A, B) lead to the transcript π and the respective outputs x, y. We demonstrate that when t is some polynomial, then not only does this hardness assumption imply the existence of KA, but it is also necessary for the existence of secure KA. As such, it yields the first natural hardness assumption characterizing the existence of key-agreement protocols. We additionally show that when the threshold s is bigger (e.g., s=55 log n), then the (worst-case) hardness of this problem instead characterizes the existence of one-way functions (OWFs). As such, our work also clarifies exactly what it would take to base KA on the existence of OWFs, and demonstrates that this question boils down to demonstrating a worst-case reduction between two closely related promise problems.

AB - 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 (π, x, y) with relatively (w.r.t. K(π)) low time-bounded Interactive Kolmogorov Complexity (IKt), and those with relatively high Kolmogorov complexity, given the promise that Kt(x · y)< s, ~Kt(y · x)< s and s=log n, and where IKt(π ; x ; y) is defined as the length of the shortest pair of t-bounded TMs (A, B) such that the interaction of (A, B) lead to the transcript π and the respective outputs x, y. We demonstrate that when t is some polynomial, then not only does this hardness assumption imply the existence of KA, but it is also necessary for the existence of secure KA. As such, it yields the first natural hardness assumption characterizing the existence of key-agreement protocols. We additionally show that when the threshold s is bigger (e.g., s=55 log n), then the (worst-case) hardness of this problem instead characterizes the existence of one-way functions (OWFs). As such, our work also clarifies exactly what it would take to base KA on the existence of OWFs, and demonstrates that this question boils down to demonstrating a worst-case reduction between two closely related promise problems.

UR - http://www.scopus.com/inward/record.url?scp=85182400746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85182400746&partnerID=8YFLogxK

U2 - 10.1109/FOCS57990.2023.00034

DO - 10.1109/FOCS57990.2023.00034

M3 - Conference contribution

AN - SCOPUS:85182400746

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 458

EP - 483

BT - Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023

PB - IEEE Computer Society

Y2 - 6 November 2023 through 9 November 2023

ER -