Quantum Cryptography Links One-Way Puzzles to Hardness of Non-Collapsing Measurements

The quest for secure communication in a world potentially beyond the reach of traditional cryptography drives ongoing research into novel cryptographic primitives, and a team led by Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa from the Yukawa Institute for Theoretical Physics and NTT Social Informatics Laboratories now presents a significant advance in this field. They investigate one-way puzzles, cryptographic tools essential for building secure systems when conventional one-way functions are unavailable, and demonstrate their existence can be based on the presumed difficulty of a new computational problem involving ‘non-collapsing measurements’. This work introduces a complexity class, denoted as, which assesses the challenge of sampling from these unusual measurements, and establishes a link between its hardness and the creation of robust one-way puzzles. By connecting this novel computational problem to existing cryptographic concepts like collision-resistant hashing and commitment schemes, the researchers illuminate a pathway towards building secure systems grounded in fundamentally different principles than those currently employed.

One-way functions (OWFs) have a natural quantum analogue, and represent one of the most fundamental primitives in “Microcrypt”, a field where OWFs do not exist but quantum cryptography is possible. One-way puzzle functions (OWPuzzs) are implied by almost all quantum cryptographic primitives, and they enable several important applications including non-interactive commitments and multi-party computations. A significant goal within quantum cryptography is to base OWPuzzs on plausible assumptions that do not imply the existence of OWFs. This work bases OWPuzzs on the hardness of non-collapsing measurements, and to that end, introduces a new complexity class called SampPDQP. SampPDQP represents a sampling version of the decision class PDQP previously introduced by Aaronson.

Minimal Assumptions for Quantum Cryptography

This collection of research explores the foundations of quantum cryptography, investigating the minimal assumptions needed to build secure cryptographic systems. A central theme is establishing quantum cryptographic primitives based on the weakest possible assumptions, potentially avoiding reliance on traditional one-way functions or other strong classical hardness assumptions. The research examines the connections between quantum cryptography and classical complexity theory, seeking to understand how results from one field can inform the other. Researchers are particularly interested in meta-complexity, characterizing the complexity of building cryptographic systems in terms of minimal assumptions and the relationships between different cryptographic primitives.

The work also explores whether quantum cryptography can leverage quantum phenomena, like entanglement or superposition, to achieve security impossible classically. A key focus, termed MiniQCrypt, is building quantum cryptography with the fewest possible assumptions, while also considering the crucial roles of randomness and unpredictability. The bibliography highlights investigations into quantum commitments, signatures, key exchange, and the design of secure protocols. Specific areas of investigation include quantum bit commitments, quantum pseudorandomness, revocable quantum digital signatures, and unitary synthesis.

The research also focuses on quantum unpredictability and its applications in cryptography. This body of work represents a research landscape focused on building a more robust and foundational understanding of quantum cryptography, potentially moving beyond the limitations of classical assumptions.

One-Way Puzzles From Quantum Measurement Hardness

This work presents a breakthrough in quantum cryptography by establishing a foundation for one-way puzzles (OWPuzzs) based on the difficulty of simulating non-collapsing measurements, a concept rooted in the fundamental laws of quantum physics. Researchers introduced a new complexity class, SampPDQP, to characterize the computational power required for these measurements and demonstrated that if SampPDQP is computationally hard on average, then OWPuzzs exist. This establishes a direct link between a physically plausible assumption, the difficulty of realizing non-collapsing measurements, and the existence of a crucial primitive for quantum cryptography. The team defines SampPDQP as the class of sampling problems solvable by a classical polynomial-time algorithm with access to a single “magical” oracle capable of sampling measurement results on quantum states without collapsing those states.

This oracle represents a highly unphysical operation, and the researchers argue that its realization in quantum polynomial time should be computationally intractable. Further investigation reveals that if SampPDQP is not a subset of SampBQP, then auxiliary-input OWPuzzs also exist, strengthening the theoretical foundation. The researchers also introduce distributional collision-resistant puzzles (dCRPuzzs) as a quantum analogue of classical collision-resistant hashing and demonstrate that dCRPuzzs imply average-case hardness of SampPDQP, and consequently, the existence of OWPuzzs. Moreover, they show that two-message honest-statistically-hiding commitments with classical communication and one-shot message authentication codes, and even commitments alone, also imply dCRPuzzs, further solidifying the connection between these cryptographic primitives and the underlying computational hardness. These results represent a significant step towards building quantum cryptography on assumptions that do not rely on the existence of one-way functions, opening new avenues for secure communication and computation in a post-quantum world.

OWPuzzs from Average-Case Complexity Assumptions

This work establishes a connection between the hardness of a novel complexity class, and the existence of one-way puzzles (OWPuzzs). Researchers demonstrate that if problems within this class are difficult to solve on average for polynomial-time algorithms, then OWPuzzs can be constructed. This is significant because OWPuzzs are fundamental cryptographic primitives, analogous to one-way functions, but applicable in settings where traditional one-way functions are not viable. The team further clarifies this relationship by introducing distributional collision-resistant puzzles (dCRPuzzs), showing that their existence implies the average-case hardness of, and consequently, the existence of OWPuzzs.

They also demonstrate connections between dCRPuzzs and other cryptographic constructs, such as two-message commitments and one-shot signatures, strengthening the foundation for building secure systems based on these principles. The authors acknowledge that their results are improvements upon existing work that relies on the hardness of classes like SZK and CZK, offering a more refined understanding of the conditions required for OWPuzz existence. While the precise relationship between their findings and other recent work exploring connections between OWPuzzs and quantum advantage remains an open question, this research provides a valuable contribution to the field of cryptography by identifying a plausible foundation for constructing these essential primitives.