Master’s Thesis Presentation • Quantum Information and Computation — Concentration Bounds from Parallel Repetition Theorems: Symmetric Key

Taylor Hornby, Master’s candidate
David R. Cheriton School of Computer Science

This thesis contributes to two areas. The first is the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. 

We make the following contributions:

• A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances).
• Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies.
• A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires quadratically more repetitions than are necessary in the classical case.

The second area is quantum cryptography, where we contribute:

• The definition of a new cryptographic primitive called an offline key expander (OKE), which aims to perform the classically-impossible task of increasing the effective brute-force resistance of a symmetric key, by trading off a one-time chance for the adversary to break the scheme without having to carry out a brute-force attack at all. We ask whether or not useful OKEs exist, but unfortunately we aren’t able to answer the question, so we leave it open.
• A candidate OKE scheme we call Pseudorandom Conjugate Coding (PCC), which attempts to protect a long key with a short one by encoding it with a pseudorandomly-generated conjugate coding. We prove that PCC is totally insecure when the key being hidden is more than a factor of 7.59 longer than the short one, and we leave PCC’s security for smaller factors an open question.