Martti Karvonen

We show that if an adaptive Z2-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin’s All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.

Verification is a crucial property of many cryptographic functionalities, enabling a verifier to check whether a prover conducted an operation as agreed or deviated from the agreement. Probably the most intuitive technique for verification is the cut-and-choose technique, in which the verifier randomly intertwines test rounds with the output round to verify the honesty of the prover. Although this technique was successfully deployed for some use cases, such as quantum key distribution, its suitability for many other functionalities remains unknown. We consider two central verification tasks — quantum state verification and verifiable delegated quantum computing — and prove inherent trade-offs when verification is implemented solely via cut-and-choose: no protocol can simultaneously achieve high correctness, security, and efficiency; improving any one of these quantities beyond certain bounds necessarily degrades at least one of the others.

Quantum state verification plays a vital role in many quantum cryptographic protocols, as it allows using quantum states from an untrusted source. While some progress has been made in this direction, the question of whether the most prevalent type of quantum state verification, namely cut-and-choose verification, can be efficient and secure, is still not answered in full generality. In this work, we show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. We provide a no-go result showing that the cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient and secure. We show this trade-off for stand-alone and composable security, where the scaling of the lower bound for the security parameters renders cut-and-choose quantum state verification effectively useless.

In arXiv:2105.05949, we initiate a categorical study of composable security definitions in cryptography. We formalize the simulation paradigm of cryptography in terms of category theory and show that protocols secure against abstract attacks form a symmetric monoidal category, thus giving an abstract model of composable security definitions in cryptography. Our model is able to incorporate computational security, set-up assumptions and various attack models such as colluding or independently acting subsets of adversaries in a modular, flexible fashion. Amongst other benefits, the categorical language allows using string diagrams to prove results cryptographically: in particular, we can promote "figures illustrating the proof" found in the cryptographic literature into honest proofs.