BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Tomoyuki Morimae

Tomoyuki Morimae contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
quant-phComputational ComplexityCryptography and Security

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Certified Everlasting Functional Encryption

Computational security in cryptography has a risk that computational assumptions underlying the security are broken in the future. One solution is to construct information-theoretically-secure protocols, but many cryptographic primitives are known to be impossible (or unlikely) to have information-theoretical security even in the quantum world. A nice compromise (intrinsic to quantum) is certified everlasting security, which roughly means the following. A receiver with possession of quantum encrypted data can issue a certificate that shows that the receiver has deleted the encrypted data. If the certificate is valid, the security is guaranteed even if the receiver becomes computationally unbounded. Although several cryptographic primitives, such as commitments and zero-knowledge, have been made certified everlasting secure, there are many other important primitives that are not known to be certified everlasting secure. In this paper, we introduce certified everlasting FE. In this primitive, the receiver with the ciphertext of a message m and the functional decryption key of a function f can obtain f(m) and nothing else. The security holds even if the adversary becomes computationally unbounded after issuing a valid certificate. We, first, construct certified everlasting FE for P/poly circuits where only a single key query is allowed for the adversary. We, then, extend it to q-bounded one for NC1 circuits where q-bounded means that q key queries are allowed for the adversary with an a priori bounded polynomial q. For the construction of certified everlasting FE, we introduce and construct certified everlasting versions of secret-key encryption, public-key encryption, receiver non-committing encryption, and a garbling scheme, which are of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Divide-and-conquer verification method for noisy intermediate-scale quantum computation

Several noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip, where two-qubit gates can be directly applied on only some pairs of qubits. In this paper, we propose a method to efficiently verify such noisy intermediate-scale quantum computation. To this end, we first characterize small-scale quantum operations with respect to the diamond norm. Then by using these characterized quantum operations, we estimate the fidelity $\langleψ_t|\hatρ_{\rm out}|ψ_t\rangle$ between an actual $n$-qubit output state $\hatρ_{\rm out}$ obtained from the noisy intermediate-scale quantum computation and the ideal output state (i.e., the target state) $|ψ_t\rangle$. Although the direct fidelity estimation method requires $O(2^n)$ copies of $\hatρ_{\rm out}$ on average, our method requires only $O(D^32^{12D})$ copies even in the worst case, where $D$ is the denseness of $|ψ_t\rangle$. For logarithmic-depth quantum circuits on a sparse chip, $D$ is at most $O(\log{n})$, and thus $O(D^32^{12D})$ is a polynomial in $n$. By using the IBM Manila 5-qubit chip, we also perform a proof-of-principle experiment to observe the practical performance of our method.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sumcheck-based delegation of quantum computing to rational server

Delegated quantum computing enables a client with weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server can be efficiently verified by the client. Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after the client interacts with the server, the client pays a reward to the server. The rational server sends messages that maximize the expected value of the reward. It is known that the classical client can delegate universal quantum computing to the rational quantum server in one round. In this paper, we propose novel one-round rational delegated quantum computing protocols by generalizing the classical rational sumcheck protocol. The construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set. Furthermore, as with the previous protocols, our reward function satisfies natural requirements. We also discuss the reward gap. Simply speaking, the reward gap is a minimum loss on the expected value of the server's reward incurred by the server's behavior that makes the client accept an incorrect answer. Although our sumcheck-based protocols have only exponentially small reward gaps as in the previous protocols, we show that a constant reward gap can be achieved if two noncommunicating but entangled rational servers are allowed. We also discuss whether a single rational server is sufficient under the (widely believed) assumption that the learning-with-errors problem is hard for polynomial-time quantum computing. Apart from these results, we show, under a certain condition, the equivalence between $rational$ and $ordinary$ delegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication

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 ciphertext can generate a classical certificate that the encrypted message is deleted. Although their construction is information-theoretically secure, it is limited to the setting of one-time symmetric key encryption (SKE), where a sender and receiver have to share a common key in advance and the key can be used only once. Moreover, the sender has to generate a quantum state and send it to the receiver over a quantum channel in their construction. Although deletion certificates are privately verifiable, which means a verification key for a certificate has to be kept secret, in the definition by Broadbent and Islam, we can also consider public verifiability. In this work, we present various constructions of encryption with certified deletion. - Quantum communication case: We achieve (reusable-key) public key encryption (PKE) and attribute-based encryption (ABE) with certified deletion. Our PKE scheme with certified deletion is constructed assuming the existence of IND-CPA secure PKE, and our ABE scheme with certified deletion is constructed assuming the existence of indistinguishability obfuscation and one-way function. These two schemes are privately verifiable. - Classical communication case: We also achieve PKE with certified deletion that uses only classical communication. We give two schemes, a privately verifiable one and a publicly verifiable one. The former is constructed assuming the LWE assumption in the quantum random oracle model. The latter is constructed assuming the existence of one-shot signatures and extractable witness encryption.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center

The posthoc verification protocol [J. F. Fitzsimons, M. Hajdu{\v s}ek, and T. Morimae, Physical Review Letters {\bf120}, 040501 (2018)] enables an information-theoretically-sound non-interactive verification of quantum computing, but the message from the prover to the verifier is quantum and the verifier has to do single-qubit measurements. The Mahadev protocol removes these quantum parts, but the soundness becomes the computational one. In this paper, we construct an information-theoretically-sound non-interactive classical verification protocol for quantum computing with a trusted center. The trusted center sends random BB84 states to the prover, and the classical descriptions of these BB84 states to the verifier. The messages from the center to the prover and the verifier are independent of the instance. By slightly modifying our protocol, we also construct a non-interactive statistical zero-knowledge proof system for QMA with the trusted center.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rational proofs for quantum computing

It is an open problem whether a classical client can delegate quantum computing to an efficient remote quantum server in such a way that the correctness of quantum computing is somehow guaranteed. Several protocols for verifiable delegated quantum computing have been proposed, but the client is not completely free from any quantum technology: the client has to generate or measure single-qubit states. In this paper, we show that the client can be completely classical if the server is rational (i.e., economically motivated), following the "rational proofs" framework of Azar and Micali. More precisely, we consider the following protocol. The server first sends the client a message allegedly equal to the solution of the problem that the client wants to solve. The client then gives the server a monetary reward whose amount is calculated in classical probabilistic polynomial-time by using the server's message as an input. The reward function is constructed in such a way that the expectation value of the reward (the expectation over the client's probabilistic computing) is maximum when the server's message is the correct solution to the problem. The rational server who wants to maximize his/her profit therefore has to send the correct solution to the client.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Trusted center verification model and classical channel remote state preparation

The classical channel remote state preparation (ccRSP) is an important two-party primitive in quantum cryptography. Alice (classical polynomial-time) and Bob (quantum polynomial-time) exchange polynomial rounds of classical messages, and Bob finally gets random single-qubit states while Alice finally gets classical descriptions of the states. In [T. Morimae, arXiv:2003.10712], an information-theoretically-sound non-interactive protocol for the verification of quantum computing was proposed. The verifier of the protocol is classical, but the trusted center is assumed that sends random single-qubit states to the prover and their classical descriptions to the verifier. If the trusted center can be replaced with a ccRSP protocol while keeping the information-theoretical soundness, an information-theoretically-sound classical verification of quantum computing is possible, which solves the long-standing open problem. In this paper, we show that it is not the case unless BQP is contained in MA. We also consider a general verification protocol where the verifier or the trusted center first sends quantum states to the prover, and then the prover and the verifier exchange a constant round of classical messages. We show that the first quantum message transmission cannot be replaced with an (even approximate) ccRSP protocol while keeping the information-theoretical soundness unless BQP is contained in AM. We finally study the verification with the computational soundness. We show that if a ccRSP protocol satisfies a certain condition even against any quantum polynomial-time malicious prover, the replacement of the trusted center with the ccRSP protocol realizes a computationally-sound classical verification of quantum computing. The condition is weaker than the verifiability of the ccRSP.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Low-temperature coherence properties of Z_2 quantum memory

We investigate low-temperature coherence properties of the Z_2 quantum memory which is capable of storing the information of a single logical qubit. We show that the memory has superposition of macroscopically distinct states for some values of a control parameter and at sufficiently low temperature, and that the code states of this memory have no instability except for the inevitable one. However, we also see that the coherence power of this memory is limited by space and time. We also briefly discuss the RVB memory, which is an improvement of the Z_2 quantum memory, and the relations of our results to the obscured symmetry breaking in statistical physics.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Superposition of macroscopically distinct states means large multipartite entanglement

We show relations between superposition of macroscopically distinct states and entanglement. These relations lead to the important conclusion that if a state contains superposition of macroscopically distinct states, the state also contains large multipartite entanglement in terms of several measures. Such multipartite entanglement property also suggests that if a state contains superposition of macroscopically distinct states, a measurement on a single particle drastically changes the state of macroscopically many other particles, as in the case of the N-qubit GHZ state.

0 citations0 reviewsNo code linkedOpen access