Attacks on the Fiat-Shamir Paradigm and Program Obfuscation

The goal of cryptology 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 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 for obfuscation. We show that, in some sense, both of these types of heuristics are insecure.