TCC 2006

March 4-7 2006, Columbia University
New York, NY USA

Tutorials

I. On Black-Box Separations in Cryptography

Omer Reingold, The Weizmann Institute

We review the notion of black-box reduction and black-box separations. We discuss several past separations and give intuition to their proof. Our focus is on the techniques for proving such separations and the subtalties that arise.

II. On Non-Black-Box Proofs of Security

Boaz Barak, Princeton University

In cryptography we typically prove the security of a scheme by reducing the task of breaking the scheme to some hard computational problem. This reduction usually done in a black-box fashion. By this we mean that there is an algorithm that can solve the hard problem given any black-box for breaking the scheme.

This talk is about exceptions to this rule: that is, schemes that are proven secure using a non-black-box reduction, that actually uses the code of a scheme-breaking attacker to construct a problem-solving algorithm. It turns out that such reductions can be used to obtain schemes with better properties that were known before. In fact, in some cases these non-black-box reductions can be obtain goals that were proven to be impossible to achieve when restricting to black-box reductions. In particular, I will present constructions of zero-knowledge protocols that are proven secure under various compositions (B. '01, Pass '04, B.-Sahai '05).