1 citations · 2 across the 3 of their papers we have counts for
8 papers
A classical oracle separation between QMA and QMA(2)
Sabee Grewal, Saachi Mutreja, Kabir Tomer
We exhibit a classical oracle relative to which QMA \neq QMA(2). The separation is based on a separable Hamiltonian problem defined by signed edge constraints on a graph. The YES i…
How to Build Pseudorandom Unitaries in Microcrypt
Aditya Gulati, Dakshita Khurana, Kabir Tomer
We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we fi…
How Not to Build Microcrypt
Aditya Gulati, Dakshita Khurana, Kabir Tomer
A key challenge in quantum cryptography is to build quantum one-wayness and pseudorandomness without the use of (quantum computable) one-way functions. So far, this has turned out…
Non-Trivial Zero-Knowledge Implies One-Way Functions
Suvradip Chakraborty, James Hulett, Dakshita Khurana +1
A recent breakthrough [Hirahara and Nanashima, STOC'2024] established that if , the existence of zero-knowledge with negligible errors…
On the Cryptographic Foundations of Interactive Quantum Advantage
Kabir Tomer, Mark Zhandry
In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A ``trivial'' PoQ is to simp…
On the Cryptographic Futility of Non-Collapsing Measurements
Alper Cakan, Dakshita Khurana, Tomoyuki Morimae +3
We investigate quantum analogues of collision resistance and obtain separations between quantum ``one-way'' and ``collision-resistant'' primitives. 1. Our first result studies one-…
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from -Hardness
Dakshita Khurana, Kabir Tomer
Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that p…
Commitments from Quantum One-Wayness
Dakshita Khurana, Kabir Tomer
One-way functions are central to classical cryptography. They are both necessary for the existence of non-trivial classical cryptosystems, and sufficient to realize meaningful prim…