2022/03/15 by Sarah Osborn, Jamie Sikora, Osborn, Sarah +1 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2203.08268
openalex publication_date 2022/03/15 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
Secure function evaluation is a two-party cryptographic primitive where Bob\ncomputes a function of Alice's and his respective inputs, and both hope to keep\ntheir inputs private from the other party. It has been proven that perfect (or\nnear perfect) security is impossible, even for quantum protocols. We generalize\nthis no-go result by exhibiting a constant lower bound on the cheating\nprobabilities for any quantum protocol for secure function evaluation, and\npresent many applications from oblivious transfer to the millionaire's problem.\nConstant lower bounds are of practical interest since they imply the\nimpossibility to arbitrarily amplify the security of quantum protocols by any\nmeans.\n