This report describes properties of basic cryptographic primitives (quantum public-key cryptosystmes and quantum one-way functions) in the quantum world where quantum computers are available. Some quantum public-key cryptosystems have already proposed. However, the security requirements for quantum public-key cryptosystems are not studied well. We propose several security notions for quantum public-key cryptosystems and discuss relation among them. In the classical setting, the notion of one-way permutations plays an essential role in cryptology. Even in the quantum setting, quantum one-way permutations are expected to play again an essential role in quantum cryptography. However, we do not have any candidates so far. So, we give a characterization of quantum one-way permutations.
This report describes properties of basic cryptographic primitives (quantum public-key cryptosystmes and quantum one-way functions) in the quantum world where quantum computers are available. Some quantum public-key cryptosystems have already proposed. However, the security requirements for quantum public-key cryptosystems are not studied well. We propose several security notions for quantum public-key cryptosystems and discuss relation among them. In the classical setting, the notion of one-way permutations plays an essential role in cryptology. Even in the quantum setting, quantum one-way permutations are expected to play again an essential role in quantum cryptography. However, we do not have any candidates so far. So, we give a characterization of quantum one-way permutations.
It is well known that Shor's quantum algorithm for integer factorization can break down the RSA public-key cryptosystem, which is widely used in many cryptographic applications. Thus, public-key cryptosystems in the quantum computational setting are longed for cryptology. In order to define the security notions of public-key cryptosystems, we have to model the power of the sender, receiver, adversary and channel. While we may consider a setting where quantum computers are available only to adversaries, we generally discuss what are the right security notions for (quantum) public-key cryptosystems in the quantum computational setting. Moreover, we consider the security of quantum public-key cryptosystems known so far.
Cryptography is the science and practice of designing computing and communication systems that are secure in the presence of adversaries.Among the central topics in cryptographic research, public-key encryption enables secure communication between two parties, while digital signatures provide guarantees on the authenticity of information.To prove the security of cryptographic schemes, we use reductions.Reduction is a fundamental concept in computer science.When problem A is reduced to problem B, it implies that B is at least as hard as A. To show such a relationship, we usually build a reduction algorithm that solves A efficiently using an algorithm that solves B as a subroutine.Such reductions not only establish the security of the cryptographic primitives, but also give a computational complexity perspective.For example, one can identify the minimal assumption on which cryptographic systems can be based.The existence of one-way functions is considered a minimal assumption in cryptography.In other words, the existence of one-way functions is essential for the existence of any cryptographic primitive.A function f is said to be one-way if, given f (x), it is computationally infeasible to efficiently recover a corresponding preimage.While one-wayness is a minimal assumption, it is also known to suffice for deriving important cryptographic primitives such as symmetric-key encryption and digital signatures.Cryptographic primitives can thus be divided into those that can be derived from one-way functions and those that cannot.Cryptographic primitives that can be derived from one-way functions are referred to as Minicrypt.In this way, one-way functions play a central role in providing a hierarchical understanding of modern cryptographic theory.When quantum communication and computation are incorporated into cryptographic protocols, it becomes possible to derive a broader class of cryptographic primitives from one-way functions.For example, while there is evidence that public-key encryption cannot be constructed from one-way functions alone in the classical setting, recent works have shown that quantum public-key encryption can be constructed from one-way functions when quantum communication channels are available.Thus, even without altering the classical boundaries, incorporating quantum communication and computation leaves ample room for phenomena that differ from those observed in the classical setting.The class of cryptographic primitives that can be constructed from one-way functions, assuming quantum computation and communication, is referred to as MiniQCrypt.As quantum technologies continue to advance and the realization of quantum communication and quantum computers becomes increasingly plausible, the study of one-way functions must be revisited and discussed within these quantum frameworks.We identify two main challenges in this area.The first challenge is to generalize the quantum reduction from one-wayness to unpredictability.The classical reduction from onewayness to unpredictability, known as the Goldreich-Levin theorem, is not only fundamental in cryptography but also plays an important role in computational complexity theory.A quantum analogue of this theorem was established by Adcock and Cleve.However, whether the quantum Goldreich-Levin theorem holds not only in the binary setting but also over more general domains such as Z q remains a nontrivial open problem.The second challenge i
Quantum cryptographic primitives beyond key distribution remain a less well understood area of research. In classical cryptography, one-way functions underpin nearly all standard cryptographic protocols, motivating the search for meaningful quantum analogues and for a clear understanding of the physical and computational mechanisms that could enforce one-wayness. In this article, we review quantum one-way functions and a range of closely related quantum-state primitives, including one-way state generators, pseudorandom quantum states, and efficiently indistinguishable pairs of states. We discuss both computational and information-theoretic notions of quantum one-wayness, emphasizing the different adversarial models and security assumptions that underlie these constructions. We compare and contrast the various proposed primitives, and clarify their conceptual relationships. Particular emphasis is placed on questions of physical realizability, experimental feasibility, and robustness to noise. Finally, we outline open problems and future directions toward the development of practical quantum cryptographic primitives beyond key distribution, and the emergence of a broader quantum-cryptographic ecosystem.
Abstract. This paper presents a new paradigm of cryptography, quantum public-key cryptosystems. In quantum public-key cryptosystems, all parties including senders, receivers and adversaries are modeled as quantum (probabilistic) poly-time Turing (QPT) machines and only classical channels (i.e., no quantum channels) are employed. A quantum trapdoor one-way function, f, plays an essential role in our system, in which a QPT machine can compute f with high probability, any QPT machine can invert f with negligible probability, and a QPT machine with trapdoor data can invert f. This paper proposes a concrete scheme for quantum public-key cryptosystems: a quantum public-key encryption scheme or quantum trapdoor one-way function. The security of our schemes is based on the computational assumption (over QPT machines) that a class of subset-sum problems is intractable against any QPT machine. Our scheme is very efficient and practical if Shor’s discrete logarithm algorithm is efficiently realized on a quantum machine.
In classical cryptography, one-way functions are necessary for most of cryptography. In the quantum world, however, Kretschmer at {TQC'21} and subsequent works have demonstrated that quantum versions of various primitives in minicrypt, such as signatures and private-key encryption, do not require quantum-computable one-way functions (\textsf{qOWF}s). However, the question of the necessity of \textsf{qOWF}s for primitives in Cryptomania like public-key encryption with classical public keys and ciphertexts (\textsf{qPKE}) has remained open.
We provide a comprehensive picture of the relationship between \textsf{qPKE} and \textsf{qOWF}. First, our main result is a black-box separation between \textsf{qOWF}s and \textsf{qPKE}. In particular, we show that relative to a unitary, real, and self-inverse oracle, there exists a \textsf{qPKE} scheme (with classical keys and ciphertexts), but \textsf{qOWF}s do not exist. Further, our oracles admit a point-function obfuscation construction, thus ruling out black-box construction of \textsf{qOWF} from point function obfuscations.
On the positive side, we construct \textsf{qPKE} from quantum indistinguishability obfuscation for quantum circuits with classical obfuscated descriptions and efficiently verifiable one-way puzzles, which is known to be a potentially weaker assumption than \textsf{qOWF}s, due to an existing black-box separation. Our construction is the quantum analog of the classical construction of \textsf{PKE} from one-way functions and indistinguishability obfuscation in the quantum computation with classical communication (QCCC) setting.