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

dc.contributor.authorOsborn, Sarah Anneen
dc.contributor.committeechairSikora, Jamieen
dc.contributor.committeememberYao, Danfengen
dc.contributor.committeememberMorrison, Travis Williamen
dc.contributor.departmentComputer Scienceen
dc.description.abstractIn 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.en
dc.description.abstractgeneralQuantifying the cryptographic security of quantum applications is the focus of much research in the quantum cryptography discipline. Quantum protocols might have better security than their classical counterparts, and this advantage might make the adoption of quantum cryptographic protocols a viable option. In this thesis, we introduce a method for generating constant lower bounds on the security of a variety of quantum applications. This is accomplished through finding a lower bound on the security of a protocol that is general, and by virtue of its generality, can be scoped to quantum applications such that the lower bound can be applied, and constant lower bounds generated for these applications. The significance of the work in this thesis is that many of the constant lower bounds presented are the first of their kind for these quantum applications, thus proving the impossibility of them having unconditional security. This also proves that one cannot asymptotically boost towards perfect security in these quantum tasks by any means. These constant lower bounds also provide a foundation for future work in the study of these quantum applications, specifically in the search for upper and lower bounds on their cryptographic security, as well as in the search for protocols that approximate these bounds.en
dc.description.degreeMaster of Scienceen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.subjectQuantum Computationen
dc.subjectQuantum Cryptographyen
dc.subjectLower Boundsen
dc.subjectSecure Function Evaluationen
dc.titleConstant Lower Bounds on the Cryptographic Security of Quantum Two-Party Computationsen
dc.typeThesisen Science and Applicationsen Polytechnic Institute and State Universityen of Scienceen
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
303.89 KB
Adobe Portable Document Format