11 papers
The Entire Quantum Computer on a Classical Leash
Yael Tauman Kalai, Dakshita Khurana, Justin Raizes
We show that a classical client with no quantum hardware can use a single untrusted and potentially malicious quantum server as if it were its own trusted quantum computer. Through…
Query-Limited RAM Programs and their Applications
Jiahui Liu, Justin Raizes, Bhaskar Roberts +1
Quantum one-time programs (Broadbent, Gutoski and Stebila, CRYPTO 2013) or OTPs for short, enable a functionality to be encoded into a quantum token that can be evaluated on a sing…
Semi-Quantum Cryptography with Certified Deletion
Yael Tauman Kalai, Justin Raizes
Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server compl…
On Best-Possible One-Time Programs
Aparna Gupte, Jiahui Liu, Luowen Qian +3
One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware. Quantum measurement suggests a physic…
How to Classically Verify a Quantum Cat without Killing It
Yael Tauman Kalai, Dakshita Khurana, Justin Raizes
A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probabi…
A New Approach to Arguments of Quantum Knowledge
James Bartusek, Ruta Jawale, Justin Raizes +1
We construct a publicly-verifiable non-interactive zero-knowledge argument system for QMA with the following properties. 1. Transparent setup. Our protocol only requires a uniforml…
Proofs of No Intrusion
Vipul Goyal, Justin Raizes
A central challenge in data security is not just preventing theft, but detecting whether it has occurred. Classically, this is impossible because a perfect copy leaves no evidence.…
How to Delete Without a Trace: Certified Deniability in a Quantum World
Alper Çakan, Vipul Goyal, Justin Raizes
Is it possible to comprehensively destroy a piece of quantum information, so that nothing is left behind except the memory of whether one had it at one point? For example, various…
Quantum One-Time Programs, Revisited
Aparna Gupte, Jiahui Liu, Justin Raizes +2
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 a…
Hard Quantum Extrapolations in Quantum Cryptography
Luowen Qian, Justin Raizes, Mark Zhandry
Although one-way functions are well-established as the minimal primitive for classical cryptography, a minimal primitive for quantum cryptography is still unclear. Universal extrap…
Secret Sharing with Certified Deletion
James Bartusek, Justin Raizes
Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret shari…