Attacks on the Fiat-Shamir paradigm and program obfuscation

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 proofs 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 some of these popular heuristics. In particular, we focus on two types of heuristics: (1) the Fiat-Shamir heuristic for constructing digital signature schemes, and (2) heuristics for obfuscation. We show that, in some sense, both of these types of heuristics are insecure. Thus, this thesis consists of two parts: (1) The insecuirty of the Fiat-Shamir paradigm: The Fiat-Shamir heuristic provides a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The idea of the transformation is to replace the random (second-round) 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.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Tauman Kalai, Yael

Advisor dc:contributor.advisor

• Shafi Goldwasser.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/34026

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/34026