Quantum one-way function (QOWF) was proposed for quantum cryptography, which was computable but almost irreversible in quantum polynomial time. Full quantum one-way function (F-QOWF) is one of the most important models of QOWF, which deals with quantum states. Although the universal construction of full quantum one-way function has been proposed, there is still little further discussion on the entangled input, specific function instantiation and application scenarios of F-QOWF. In this paper, we introduce quantum hypergraph states into the universal construction of F-QOWF. Quantum hypergraph states are highly entangled multi-party states constructed from the hypergraph. By applying quantum hypergraph states to the new F-QOWF, we generalize the universal construction of F-QOWF to entangled states. The application to quantum aggregate signature shows that quantum hypergraph states help the new F-QOWF be well applied to quantum multi-party cryptographic protocols.
Quantum one-way function (QOWF) was proposed for quantum cryptography, which was computable but almost irreversible in quantum polynomial time. Full quantum one-way function (F-QOWF) is one of the most important models of QOWF, which deals with quantum states. Although the universal construction of full quantum one-way function has been proposed, there is still little further discussion on the entangled input, specific function instantiation and application scenarios of F-QOWF. In this paper, we introduce quantum hypergraph states into the universal construction of F-QOWF. Quantum hypergraph states are highly entangled multi-party states constructed from the hypergraph. By applying quantum hypergraph states to the new F-QOWF, we generalize the universal construction of F-QOWF to entangled states. The application to quantum aggregate signature shows that quantum hypergraph states help the new F-QOWF be well applied to quantum multi-party cryptographic protocols.
One-way functions are fundamental tools for cryptography. Until now, quantum one-way functions have several input-output categories such as “classical-to-classical,” “classical-to-quantum,” and “quantum-to-classical,” which are used for postquantum cryptography or quantum cryptography. However, there are still no intrinsic “quantum-to-quantum” quantum one-way functions. In this article, we propose the full quantum one-way function to design full quantum cryptographic schemes. By concatenating the “quantum-classical” one-way function and the rotation operation of single qubit, the full quantum one-way function has the input and output of quantum states. We prove its one-way property from “easy computation” and “computationally difficult to invert.” Then we apply the full quantum one-way function to quantum identity authentication. Security analysis shows that the proposed quantum identity authentication scheme based on the full quantum one-way function is secure even under active attacks.
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.
Hypergraph states, a generalization of graph states, constitute a large class of quantum states with intriguing nonlocal properties, and they have promising applications in quantum information science and technology. In this paper, we study some features of an independently proposed generalization of hypergraph states to qudit hypergraph states, i.e., each vertex in the generalized hypergraph (multi-hypergraph) represents a d-level system instead of a two-level one. It is shown that multi-hypergraphs and d-level hypergraph states have a one-to-one correspondence, and the structure of a multi-hypergraph exhibits the entanglement property of the corresponding quantum state. We discuss their relationship with some well-known state classes, e.g., real equally weighted states and stabilizer states. The Bell nonlocality, an important resource in fulfilling many quantum information tasks, is also investigated.
In the rapidly developing field of quantum cryptography, graph theory provides a useful mathematical foundation for complex relationships and structures.Applications for it are becoming more and more common.Vertices, edges, connectivity, and graph states, all components of graph theory help illustrate multi-party entanglement, network connection, and protocol designs in quantum cryptography systems.The connection between graph theory and quantum cryptography is examined in this article.It shows that, graph theory and quantum cryptography design can be used to create scalable, reliable quantum secure networks.The basics of graph theory, including network modeling and graph-state entanglement, are covered.It then gives a summary of modern graph-based quantum cryptography methods, including those used for secure computing, secret sharing, and key distribution.The study highlights current issues while contrasting their approaches and resource requirements.Graph states are used in current methods for secret sharing and multi-party key agreement.Additionally, they use graph structures for protocol creation and graph networks for routing in quantum key distribution (QKD).However, significant obstacles remain, such as the experimental construction of large graph-state networks, securing against different types of assaults, and using sophisticated graphtheoretic methods.Novel graph structures such as hypergraphs and quotient graphs should be the focus of future research.It should also develop graph-based solutions for post-quantum and multi-party cryptographic primitives and include classical-quantum network analysis.
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 cryptographic primitives can exist even if one-way functions do not exist. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results. (1) We define a weaker version of OWSGs, weak OWSGs, and show that they are equivalent to OWSGs. (2) Quantum digital signatures are equivalent to OWSGs. (3) Private-key quantum money schemes (with pure money states) imply OWSGs. (4) Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. (5) We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs, and show that they are equivalent to EFI pairs.