Constructions, Lower Bounds, and New Directions in Cryptography and Computational Complexity

In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators á la Goldreich-Levin; an issue related to streaming models for cryptography. In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives. We observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP; BPP an so on. By parametrizing on the number of passes over the random tape we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize BPNC (a class believed to be much lower than P ⊆ BPP). We also obtain a number of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [Nis92] for the derandomization of BPNC 1, and the relation of parametrized access to NP-witnesses with width- parametrizations of SAT. A substantial contribution regards a streaming approach to lower bounds for problems in the NC-hierarchy (and above). We apply Communication Complexity to show a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage. In particular, we obtain a nΩ(1) lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P − NC assuming EXP ≠ PSPACE. Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC0 [AIK06a] yields a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model. Also, we show that relying on this work is in some sense necessary.

Department dc:contributor.department

Computer Science

Year dc:date.issued

2010

Author dc:creator

• Papakonstantinou, Periklis

Advisor dc:contributor.advisor

• Rackoff, Charles

• computational complexity
• cryptography

Language dc:language.iso

en_ca

Handle dc:identifier.uri

http://hdl.handle.net/1807/24843

OAI identifier oai:identifier

oai:utoronto.scholaris.ca:1807/24843