4 citations · 8 across the 13 of their papers we have counts for
15 papers
Quantum Pessiland
Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa
Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Imp…
Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
Shuji Horinaga, Takashi Yamakawa
The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as poss…
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…
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…
Proofs of quantum memory
Minki Hhan, Tomoyuki Morimae, Yasuaki Okinaka +1
With the rapid advances in quantum computer architectures and the emerging prospect of large-scale quantum memory, it is becoming essential to classically verify that remote device…
From Worst-Case Hardness of to Quantum Cryptography via Quantum Indistinguishability Obfuscation
Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa
Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications. While classical iO, combined with the infinitely-often worst-case ha…