Expressiveness of Definitions and Efficiency of Constructions in Computational Cryptography

Abstract

The computational treatment of cryptography, and indeed any scientific treatment of a problem, is marked by its definitional side and by it constructive side. Results in this thesis better our understanding of both: on one side, they characterize the extent to which computational definitions capture the security of the basic task of symmetric encryption; on the other, they provide explicit bounds on the efficiency of commitment and secure two-party computation constructions. Specifically:

- We relate the <em>formal</em> and <em>computational</em> treatments of symmetric encryption, obtaining a <em>precise</em> characterization of computational schemes whose computational semantics imply their formal semantics. We prove that this characterization is strictly weaker than previously-identified notions, and show how it may be realized in a simpler, more efficient manner.

- We provide lower-bounds on the number of times a one-way permutation needs to be invoked (as a "black-box") in order to construct statistically-binding commitments. Our bounds are tight for the case of <em>perfectly</em>-binding schemes.

- We show that the secure computation of <em>any</em> two-party functionality can be performed in an optimal <em>two</em> rounds of communication even in a setting that accounts for concurrent execution with other protocols (i.e., the Universal Composability framework). Here, we rely on the assumption that parties have access to a common reference string; some sort of setup is known to be necessary.