2018/10/31 by Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computer science #Computer security #Cryptographic protocol #Cryptography #Cryptography and Data Security #Oblivious transfer #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum cryptography #Quantum information #Quantum mechanics #Security token #Simple (philosophy) #Stateless protocol #Theoretical computer science #Universal composability #quant-ph
paper · pdf · doi:10.22331/q-2021-04-08-429
published as Quantum 5, 429 (2021) · 36 pages. Followup to withdrawn paper arXiv:1511.01363v1; this new paper has different security claims and proof techniques. v2: Various updates, including further fleshing out of Gutoski/Watrous SDP framework for security, and evidence potentially supporting conjecture for polynomial security. v3: Published version (to appear in Quantum), updates to improve SDP exposition and to conjectures
arxiv created 2021/04/01 · openalex publication_date 2021/04/08 · arxiv updated 2021/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>i</mml:mi><mml:mo>.</mml:mo><mml:mi>e</mml:mi><mml:mo>.</mml:mo></mml:math>, reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> adaptive queries to the token (for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.