Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/204942
Title: DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY
Authors: SRIJITA KUNDU
ORCID iD:   orcid.org/0000-0002-8630-0113
Keywords: Query complexity, communication complexity, device-independent cryptography, direct product, composition
Issue Date: 21-Jul-2021
Citation: SRIJITA KUNDU (2021-07-21). DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY. ScholarBank@NUS Repository.
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.
URI: https://scholarbank.nus.edu.sg/handle/10635/204942
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
KunduS.pdf1.08 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

118
checked on May 12, 2022

Download(s)

22
checked on May 12, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.