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
In this paper, we introduce a new concept, proofs of quantum memory (PoQM). A PoQM is an interactive protocol between a classical verifier and a quantum prover over a classical cha…
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…
Quantum Lifting for Invertible Permutations and Ideal Ciphers
Alexandru Cojocaru, Minki Hhan, Qipeng Liu +2
In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probabilit…
Cryptographic Characterization of Quantum Advantage
Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa
Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advant…
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…
A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
Amit Behera, Giulio Malavolta, Tomoyuki Morimae +2
While in classical cryptography, one-way functions (OWFs) are widely regarded as the "minimal assumption," the situation in quantum cryptography is less clear. Recent works have pu…
A Simple Framework for Secure Key Leasing
Fuyuki Kitagawa, Tomoyuki Morimae, Takashi Yamakawa
Secure key leasing (a.k.a. key-revocable cryptography) enables us to lease a cryptographic key as a quantum state in such a way that the key can be later revoked in a verifiable ma…
Quantum Unpredictability
Tomoyuki Morimae, Shogo Yamada, Takashi Yamakawa
Unpredictable functions (UPFs) play essential roles in classical cryptography, including message authentication codes (MACs) and digital signatures. In this paper, we introduce a q…
Exponential Quantum One-Wayness and EFI Pairs
Giulio Malavolta, Tomoyuki Morimae, Michael Walter +1
In classical cryptography, one-way functions are widely considered to be the minimal computational assumption. However, when taking quantum information into account, the situation…
Revocable Quantum Digital Signatures
Tomoyuki Morimae, Alexander Poremba, Takashi Yamakawa
We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption…
A Note on Output Length of One-Way State Generators and EFIs
Minki Hhan, Tomoyuki Morimae, Takashi Yamakawa
We study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs. - Standard OWSGs. Recently, Cavalar et al. (arXiv:2312.08363) give OWSGs with -q…