11 papers
Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
Bruno Cavalar, Eli Goldin, Matthew Gray +3
One of the most fundamental problems in distribution testing is the identity testing problem: given samples , the goal is to determine whether the samples are drawn…
Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions
Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki +1
Mahadev [SIAM J. Comput. 2022] introduced the first protocol for classical verification of quantum computation based on the Learning-with-Errors (LWE) assumption, achieving a 4-mes…
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-…
Black-Box Separation Between Pseudorandom Unitaries, Pseudorandom Isometries, and Pseudorandom Function-Like States
Aditya Gulati, Yao-Ting Lin, Tomoyuki Morimae +1
Pseudorandom functions (PRFs) are one of the most fundamental primitives in classical cryptography. On the other hand, in quantum cryptography, it is possible that PRFs do not exis…
Quantum Cryptography and Hardness of Non-Collapsing Measurements
Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa
One-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in ''Mi…
CountCrypt: Quantum Cryptography between QCMA and PP
Eli Goldin, Tomoyuki Morimae, Saachi Mutreja +1
We construct a unitary oracle relative to which but quantum-computation-classical-communication (QCCC) commitments and QCCC multiparty non-interactive…