2024/04/25 by Atul Singh Arora, Jamie Sikora, Arora, Atul Singh +3
Computer Science · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #IoT and Edge/Fog Computing #Parallel Computing and Optimization Techniques #Quantum Physics (quant-ph) #Software System Performance and Reliability
paper · pdf · doi:10.48550/arxiv.2404.17079
openalex publication_date 2024/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Weak coin flipping is the cryptographic task where Alice and Bob remotely flip a coin but want opposite outcomes. This work studies this task in the device-independent regime where Alice and Bob neither trust each other, nor their quantum devices. The best protocol was devised over a decade ago by Silman, Chailloux, Aharon, Kerenidis, Pironio, and Massar with bias ε ≈ 0.33664, where the bias is a commonly adopted security measure for coin flipping protocols. This work presents two techniques to lower the bias of such protocols, namely self-testing and abort-phobic compositions. We apply these techniques to the SCAKPM '11 protocol above and, assuming a continuity conjecture, lower the bias to ε ≈ 0.29104. We believe that these techniques could be useful in the design of device-independent protocols for a variety of other tasks. Independently of weak coin flipping, en route to our results, we show how one can test n-1 out of n devices, and estimate the performance of the remaining device, for later use in the protocol. The proof uses linear programming and, due to its generality, may find applications elsewhere.