Paper 2024/1934

Quantum One-Time Programs, Revisited

Aparna Gupte, Massachusetts Institute of Technology
Jiahui Liu, Massachusetts Institute of Technology
Justin Raizes, Carnegie Mellon University
Bhaskar Roberts, University of California, Berkeley
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Abstract

One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security. There is a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security. In this work, we present new, meaningful, yet achievable definitions of one-time program security for *probabilistic* classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be highly random given a single query, but whose one-time program form leaks the entire function even in the oracle model.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
quantum cryptographyone time programunclonable cryptographysignature tokens
Contact author(s)
agupte @ mit edu
jiahuiliu crypto @ gmail com
jraizes @ andrew cmu edu
bhaskarr @ berkeley edu
vinodv @ mit edu
History
2024-11-29: approved
2024-11-28: received
See all versions
Short URL
https://ia.cr/2024/1934
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1934,
      author = {Aparna Gupte and Jiahui Liu and Justin Raizes and Bhaskar Roberts and Vinod Vaikuntanathan},
      title = {Quantum One-Time Programs, Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1934},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1934}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.