## TCC 2006March 4-7 2006, Columbia UniversityNew York, NY USA |

Home Call for papers Accepted papers Program Rump session Venue Entertainment Restaurant list Travel Info Accommodation Registration Contact |
## Tutorials## I. On Black-Box Separations in Cryptography## Omer Reingold, The Weizmann InstituteWe 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 UniversityIn 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). |