Constant Lower Bounds on the Cryptographic Security of Quantum Two-Party Computations

In this thesis, we generate a lower bound on the security of quantum protocols for secure function evaluation. Central to our proof is the concept of gentle measurements of quantum states, which do not greatly disturb a quantum state if a certain outcome is obtained with high probability. We show how a cheating party can leverage gentle measurements to learn more information than should be allowable. To quantify our lower bound, we reduce a specific cryptographic task known as die-rolling to secure function evaluation and use the concept of gentle measurements to relate their security notions. Our lower bound is then obtained using a known security bound for die-rolling known as Kitaev's bound.

Due to the generality of secure function evaluation, we are able to apply this lower bound to obtain lower bounds on the security of quantum protocols for many quantum tasks. In particular, we provide lower bounds for oblivious transfer, XOR oblivious transfer, the equality function, the inner product function, Yao's millionaires' problem, and the secret phrase problem. Note that many of these lower bounds are the first of their kind, which is a testament to the utility of our lower bound. As a consequence, these bounds prove that unconditional security for quantum protocols is impossible for these applications, and since these are constant lower bounds, this rules out any form of boosting toward perfect security. Our work lends itself to future research on designing optimal protocols for the above listed tasks, and potentially others, by providing constant lower bounds to approximate or improve.