PROBLEMS IN QUANTUM TAMPER RESILIENT CRYPTOGRAPHY AND QUANTUM COMMUNICATION COMPLEXITY

Abstract

In the first part of this thesis, we study combinatorial objects such as extractors, nonmalleable extractors, and non-malleable codes. They have been found useful in numerous applications including privacy-amplification (PA), pseudo-randomness, derandomization, expanders, combinatorics, and cryptography. Extractors are functions that are useful in extracting almost truly random bits from imperfect sources of randomness. While non-malleable extractors provide a stronger notion of randomness extraction, non-malleable codes provide relaxation of the notion of error-detection codes. We study the security of these combinatorial objects against quantum side information on the imperfect sources of randomness.

In the second part of this thesis, we study a problem related to quantum communication complexity. In particular, we disprove the quantum log-approximate-rank conjecture of Lee and Shraibman [LS08], which states that for a total function f, the log-approximate-rank of the communication matrix corresponding to f and quantum communication complexity of the function f are polynomially related.