Browse Theses

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 random message of the verifier in the identification scheme, with the value of some deterministic hash function evaluated on the first-round message (sent by the prover) and on the message to be signed, The Fiat-Shamir methodology for producing digital signature schemes quickly gained popularity both in theory and in practice, as it yields efficient and easy to implement digital signature schemes. The most important question however remained open: are the digital signature schemes produced by the Fiat-Shamir methodology secure__ __

In this thesis, we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir transformation yields insecure digital signature, schemes for any hash function used by the transformation. This is in contrast to the work of Pointcheval and Stern, who proved that the Fiat-Shamir methodology always produces digital signature schemes that are secure against chosen message attacks in the "Random Oracle Model"---when the hash function is modeled by a random oracle. Thus, our result can be viewed as a continuation to the line of critical studies of the Random Oracle Model, which was initiated by Canetti, Goldreich and Halevi.

2. The impossibility of obfuscation. The goal of code obfuscation is to make a program completely "unintelligible" while preserving its functionality. Obfuscation has been used for many years in attempts to prevent reverse engineering, e.g., for copy protection, licensing schemes, and games. As a result, many heuristics for obfuscation have emerged, and the important question that remained is: are these heuristics for obfuscation secure__ __

Barak et al. (2001) demonstrated the existence of a class of functions for which obfuscation is not at all possible. In this thesis we go beyond an existential impossibility result, showing that there are many " natural " classes of functions that cannot be obfuscated. This impossibility result holds in an augmentation of the formal obfuscation model of Barak et al. that includes auxiliary input.

In both of these parts, among other things, we take advantage of non black-box access to a program, a technique pioneered by Barak, this time in the context of digital signature schemes and in the context of obfuscation.