74 citations · 192 across the 22 of their papers we have counts for
26 papers
MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations
Mohammed Barhoush, Ryo Nishimaki, Takashi Yamakawa
We investigate two natural relaxations of quantum cryptographic primitives. The first involves quantum input sampling, where inputs are generated by a quantum algorithm rather than…
Untelegraphable Encryption and its Applications
Jeffrey Champion, Fuyuki Kitagawa, Ryo Nishimaki +1
We initiate the study of untelegraphable encryption (UTE), founded on the no-telegraphing principle, which allows an encryptor to encrypt a message such that a binary string repres…
Robust Combiners and Universal Constructions for Quantum Cryptography
Taiga Hiroka, Fuyuki Kitagawa, Ryo Nishimaki +1
A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of t…
Unconditionally Secure Commitments with Quantum Auxiliary Inputs
Tomoyuki Morimae, Barak Nehoran, Takashi Yamakawa
We show the following unconditional results on quantum commitments in two related yet different models: 1. We revisit the notion of quantum auxiliary-input commitments introduced b…
Quantum Complexity for Discrete Logarithms and Related Problems
Minki Hhan, Takashi Yamakawa, Aaram Yun
This paper studies the quantum computational complexity of the discrete logarithm (DL) and related group-theoretic problems in the context of generic algorithms -- that is, algorit…
Publicly Verifiable Deletion from Minimal Assumptions
Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
We present a general compiler to add the publicly verifiable deletion property for various cryptographic primitives including public key encryption, attribute-based encryption, and…
Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions
Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki +1
We construct quantum public-key encryption from one-way functions. In our construction, public keys are quantum, but ciphertexts are classical. Quantum public-key encryption from o…
Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
Xingjian Li, Qipeng Liu, Angelos Pelecanos +1
It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly BQP/poly or QMA QCMA. In this paper, we construct classically-accessib…
Public Key Encryption with Secure Key Leasing
Shweta Agrawal, Fuyuki Kitagawa, Ryo Nishimaki +2
We introduce the notion of public key encryption with secure key leasing (PKE-SKL). Our notion supports the leasing of decryption keys so that a leased key achieves the decryption…
Obfuscation of Pseudo-Deterministic Quantum Circuits
James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki +1
We show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, assuming the quantum hardness of learning with errors. Given the classical description…
Certified Everlasting Secure Collusion-Resistant Functional Encryption, and More
Taiga Hiroka, Fuyuki Kitagawa, Tomoyuki Morimae +3
We study certified everlasting secure functional encryption (FE) and many other cryptographic primitives in this work. Certified everlasting security roughly means the following. A…
Quantum Advantage from One-Way Functions
Tomoyuki Morimae, Takashi Yamakawa
We demonstrate quantum advantage with several basic assumptions, specifically based on only the existence of OWFs. We introduce inefficient-verifier proofs of quantumness (IV-PoQ),…
From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments
Minki Hhan, Tomoyuki Morimae, Takashi Yamakawa
Recently, Aaronson et al. (arXiv:2009.07450) showed that detecting interference between two orthogonal states is as hard as swapping these states. While their original motivation w…
One-Wayness in Quantum Cryptography
Tomoyuki Morimae, Takashi Yamakawa
The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryp…
Proofs of Quantumness from Trapdoor Permutations
Tomoyuki Morimae, Takashi Yamakawa
Assume that Alice can do only classical probabilistic polynomial-time computing while Bob can do quantum polynomial-time computing. Alice and Bob communicate over only classical ch…
Certified Everlasting Functional Encryption
Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki +1
Computational security in cryptography has a risk that computational assumptions underlying the security are broken in the future. One solution is to construct information-theoreti…
Verifiable Quantum Advantage without Structure
Takashi Yamakawa, Mark Zhandry
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: - There are NP search problems solvable by quantum polynomial-time machines but no…
Quantum commitments and signatures without one-way functions
Tomoyuki Morimae, Takashi Yamakawa
In the classical world, the existence of commitments is equivalent to the existence of one-way functions. In the quantum setting, on the other hand, commitments are not known to im…
Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round
Nai-Hui Chia, Kai-Min Chung, Xiao Liang +1
From the minimal assumption of post-quantum semi-honest oblivious transfers, we build the first -simulatable two-party computation (2PC) against quantum polynomial-time (QPT) ad…
Certified Everlasting Zero-Knowledge Proof for QMA
Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki +1
In known constructions of classical zero-knowledge protocols for NP, either of zero-knowledge or soundness holds only against computationally bounded adversaries. Indeed, achieving…
Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication
Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki +1
Broadbent and Islam (TCC '20) proposed a quantum cryptographic primitive called quantum encryption with certified deletion. In this primitive, a receiver in possession of a quantum…
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu +1
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for . As a main result, we show that there is no constant-round post-qua…
Classically Verifiable NIZK for QMA with Preprocessing
Tomoyuki Morimae, Takashi Yamakawa
We propose three constructions of classically verifiable non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models. - We construct a CV-…
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, th…