Paper 2024/425
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement
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
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Contact author(s)
-
marshall @ cs nyu edu
yl2866 @ cornell edu
noammaz @ gmail com
rafaelp @ tau ac il - History
- 2024-03-15: approved
- 2024-03-12: received
- See all versions
- Short URL
- https://ia.cr/2024/425
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/425, author = {Marshall Ball and Yanyi Liu and Noam Mazor and Rafael Pass}, title = {Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/425}, year = {2024}, url = {https://eprint.iacr.org/2024/425} }