• Randomness and Its Power: Randomness is a source of power, used in various applications like coin tosses and securing online interactions. It enables fair and unpredictable choices.
• Generating Randomness in Computing: Many computing applications find it hard to generate suitable randomness. Programmers often rely on hash functions instead. Hash functions swirl data and extract a small random-looking portion. For decades, the random oracle model assumed that the outputs of good hash functions are indistinguishable from genuine randomness.
• New Paper and Its Impact: A new paper has shaken the random oracle model assumption. It demonstrates a method to trick a commercially available proof system into certifying false statements, even though the system is secure under the random oracle model. This is relevant for blockchains that record cryptocurrency transactions.
• The Fiat-Shamir Transformation: This fundamental technique is used in various computing applications to convince strangers that a computation is correct. It involves using hash functions to generate random challenges and address concerns about bribing or trapdoors. The Fiat-Shamir transformation turns interactive proofs into noninteractive ones.
• Proving Lies with Fiat-Shamir: In 1996, Fiat-Shamir was proved secure in the random oracle model. But real hash functions are not truly random, and researchers worried about attacks. In 2000s, interactive proof protocols were designed to fail under Fiat-Shamir. Later, a new attack was discovered on a Fiat-Shamir proof system based on the GKR protocol. A malicious program can compute random challenges and pass inspection, allowing false proofs.
• Mitigating the Attack: Polyhedra offered a version of the proof system that was attacked and quickly patched. Yogev and Gal Arnon came up with another way to modify Fiat-Shamir to defend against the attack. But not all applications may be suitable for such modifications, and there may be other attacks.
• Concerns and Future: Thaler is more worried about implementation bugs than the new attack. Other researchers are more concerned, as complex code may be vulnerable to undetected malicious code. The attack has shaken cryptographers' confidence in the Fiat-Shamir protocol and the random oracle model. It may be time to rethink and revise many other things that were thought to be proven.