Communications of the ACM
Answer to Thorny Question Could Unlock Internet Security
The question essentially is, can randomness exponentially speed up computations? said Rafael Pass, professor of computer science at Cornell Tech and at the Cornell Ann S. Bowers College of Computing and Information Science.
Credit: Henry Yuen
Cornell University's Rafael Pass and Yanyi Liu explored the EXP versus BPP problem, which concerns whether randomness exponentially accelerates computations.
If true, then all encryption schemes can be cracked and Internet security undone, and the researchers probed whether assuming that EXP is unequal to BPP will ensure unbreakable encryption schemes.
Their work reconsidered their previously discovered link between encryption schemes and the time-bounded Kolmogorov Complexity of a string, or the length of the shortest program that can output x in a set duration.
The researchers determined that unbreakable encryptions are possible only if an algorithm that can compute the Levin-Kolmogorov Complexity for most strings, without committing excessive errors, is nonexistent.
The Levin-Kolmogorov Complexity problem is core to understanding the EXP versus BPP conundrum, and Pass said proving that EXP is unequal to BPP would solve the N versus NP riddle fundamental to computer science and cryptography.
From Cornell Chronicle
View Full Article
Abstracts Copyright © 2021 SmithBucklin, Washington, DC, USA
No entries found