Randomness is a source of power. From the coin toss that decides which team gets the ball to the random keys that secure online interactions, randomness lets us make choices that are fair and impossible to predict.
But in many computing applications, suitable randomness can be hard to generate. So instead, programmers often rely on things called hash functions, which swirl data around and extract some small portion in a way that looks random. For decades, many computer scientists have presumed that for practical purposes, the outputs of good hash functions are generally indistinguishable from genuine randomness — an assumption they call the random oracle model.
“It’s hard to find today a cryptographic application… whose security analysis does not use this methodology,” said Ran Canetti (opens a new tab) of Boston University.
Now, a new paper (opens a new tab) has shaken that bedrock assumption. It demonstrates a method for tricking a commercially available proof system into certifying false statements, even though the system is demonstrably secure if you accept the random oracle model. Proof systems related to this one are essential for the blockchains that record cryptocurrency transactions, where they are used to certify computations performed by outside servers.
There’s “a lot of money relying on this stuff,” said Eylon Yogev (opens a new tab) of Bar-Ilan University in Israel. For blockchain proof protocols, “there’s a huge motivation for attackers to break the security of the system.”
In the new paper — by Dmitry Khovratovich (opens a new tab) of the Ethereum Foundation, Ron Rothblum (opens a new tab) of the zero-knowledge proof technology company Succinct and the Technion in Haifa, Israel, and Lev Soukhanov of the blockchain-focused start-up [[alloc] init] — the researchers are able to prove lies no matter which hash function is used to generate the “randomness” the proof system relies upon.
When Yogev heard about the team’s result, he said, “I had the feeling that someone is pulling the carpet from under my feet.” He and others have been working to patch up these vulnerabilities. But “it’s far from being a solved issue,” he said.
More broadly, the new result is forcing a reckoning about the random oracle model. “This is a time to rethink,” Canetti said.
To read more, click here.