An attack on a fundamental proof technique reveals a glaring security issue for blockchains and other digital encryption schemes.

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 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.

...read more at quantamagazine.org