DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY

Abstract

In this thesis, we study direct product and composition theorems in query complexity, communication complexity and non-local games, and show applications of these results in device-independent cryptography.

The first part of the thesis deals with direct product and composition theorems. Our first result in this part is a composition theorem for randomized query complexity. Next we consider composition theorems where a query function is composed with a communication function, which are often called query-to-communication 'lifting' theorems. We show results lifting various adversary bounds, which are a lower bound technique in query complexity, to randomized and quantum communication complexity.

We study direct product theorems in communication, and closely related parallel repetition theorems in communication, using a technique called anchoring. First, we prove a strong direct product theorem for one-way quantum communication complexity using this technique. Second, we give a simplified proof of a parallel repetition theorem for one-round non-local games whose input distributions are anchored. Third, we prove a parallel repetition theorem for a class of two-round non-local games also via anchoring. The final result of the first part of the thesis is a direct product theorem for interactive quantum communication complexity in terms of the efficiency or quantum partition bound, which is a lower bound on quantum communication.

In the second part of the thesis, our first result is exhibiting a device-independent protocol for a cryptographic task known as encryption with certified deletion, whose security we prove using the parallel repetition theorem for two-round games proved in the first part. Finally, using the interactive direct product result from the first part, we prove that it is possible to do device-independent quantum key distribution even with devices that leak information.