One-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in ''Microcrypt'' where OWFs do not exist but quantum cryptography is possible. OWPuzzs are implied by almost all quantum cryptographic primitives, and imply several important applications such as non-interactive commitments and multi-party computations. A significant goal in the field of quantum cryptography is to base OWPuzzs on plausible assumptions that will not imply OWFs. In this paper, we base OWPuzzs on hardness of non-collapsing measurements. To that end, we introduce a new complexity class,
SampPDQP, which is a sampling version of the decision class
PDQP introduced in [Aaronson, Bouland, Fitzsimons, and Lee, ITCS 2016]. We show that if
SampPDQP is hard on average for quantum polynomial time, then OWPuzzs exist.
SampPDQP is the class of sampling problems that can be solved by a classical polynomial-time algorithm that can make a single query to a non-collapsing measurement oracle, which is a ''magical'' oracle that can sample measurement results on quantum states without collapsing the states. Such non-collapsing measurements are highly unphysical operations that should be hard to realize in quantum polynomial-time. We also study upperbounds of the hardness of
SampPDQP. We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs), which are a natural quantum analogue of distributional collision-resistant hashing [Dubrov and Ishai, STOC 2006]. We show that dCRPuzzs imply average-case hardness of
SampPDQP (and therefore OWPuzzs as well). We also show that two-message honest-statistically-hiding commitments with classical communication and one-shot signatures [Amos, Georgiou, Kiayias, Zhandry, STOC 2020] imply dCRPuzzs.
Abstract Quantum Key Distribution (QKD) is widely marketed as an unconditionally secure framework, shielded by the quantum mechanical postulate that any measurement of an unknown state inevitably disturbs the system and alerts legitimate parties to eavesdropping. In this paper, we demonstrate that this assumption represents a critical overgeneralization. By deploying Quantum Non-Demolition (QND) measurement techniques alongside state synchronization, an adversary can extract state information without triggering the wave-function collapse or state disturbance predicted by classical interpretations of von Neumann measurements. We establish that the security of current quantum cryptographic protocols relies on a restrictive dogma rather than a universal physical boundary, exposing a fundamental architectural flaw in quantum communication security. Key Takeaways & Core Concepts Refutation of the "Disturbance Axiom": Challenges the foundational assumption of QKD protocols (such as BB84) that information extraction inherently requires physical perturbation of the transmitted quantum state. QND Eavesdropping Mechanism: Outlines a theoretical State Synchronization Attack where an adversary uses Quantum Non-Demolition probes to weakly couple with carrier signals, reading state data without introducing a detectable Quantum Bit Error Rate (QBER). Logical Invalidation: Uses formal Aristotelian deductive logic to demonstrate that the existence of non-disturbing (QND) measurement classes serves as a single counterexample that falsifies claims of "unconditional physical security." Systemic Cryptographic Impact: Re-evaluates quantum physical-layer security, arguing that 0% error rate reporting does not guarantee an uncompromised channel and pushing for rewritten security bounds that