Attacks on the Fiat-Shamir paradigm and program obfuscation
Yael Tauman Kalai · 2006
The goal of cryptography is to construct secure and efficient protocols for various tasks. Unfortunately, it is often the case that protocols that are provably secure are not efficient enough for practical use. As a result, most protocols used in practice are heuristics that lack a proof of security. These heuristics are typically very efficient and are believed to be secure, though no proof of security has been provided. In this thesis we study the security of two types of such popular heuristics: (1) the Fiat-Shamir paradigm for constructing digital signature schemes, and (2) heuristics for obfuscation. We show that, in some sense, both of these types of heuristics are insecure. This thesis consists of two parts: 1. The insecurity of the Fiat-Shamir paradigm. The Fiat-Shamir paradigm provides a general method for transforming any 3-round identification scheme, in which the verifier’s message is random (and consists of his random coin tosses), into a digital signature scheme. The idea of the transformation is to replace the