Welcome to the resource topic for 2024/425
Title:
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement
Authors: Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass
Abstract: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 relatively (w.r.t. K(\pi)) low time-bounded Interactive Kolmogorov Complexity (IK^t), and those with relatively high Kolmogorov complexity, given the promise that K^t(x|y)< s, K^t(y|x)< s and s = log n, and where IK^t(\pi;x;y) is defined as the length of the shortest pair of t-bounded TMs (A,B) such that the interaction of (Ac,Bc) lead to the transcript \pi 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 = 55log 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.
ePrint: https://eprint.iacr.org/2024/425
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .