acm-header
Sign In

Communications of the ACM

ACM News

Researchers Identify 'Master Problem' Underlying All Cryptography


In the absence of proofs, cryptographers simply hope that the functions that have survived attacks really are secure.

Credit: Samantha Mash/Quanta Magazine

In 1868, the mathematician Charles Dodgson (better known as Lewis Carroll) proclaimed that an encryption scheme called the Vigenère cipher was "unbreakable." He had no proof, but he had compelling reasons for his belief, since mathematicians had been trying unsuccessfully to break the cipher for more than three centuries.

There was just one small problem: A German infantry officer named Friedrich Kasiski had, in fact, broken it five years earlier, in a book that garnered little notice at the time.

Cryptographers have been playing this game of cat and mouse, creating and breaking ciphers, for as long as people have been sending secret information. "For thousands of years, people [have been] trying to figure out, 'Can we break the cycle?'" said Rafael Pass, a cryptographer at Cornell Tech and Cornell University.

Five decades ago, cryptographers took a huge step in this direction. They showed that it's possible to create provably secure ciphers if you have access to a single ingredient: a "one-way function," something that's easy to carry out but hard to reverse. Since then, researchers have devised a wide array of candidate one-way functions, from simple operations based on multiplication to more complicated geometric or logarithmic procedures.

From Quanta Magazine
View Full Article

 


 

No entries found