On the Cryptographic Futility of Non-Collapsing Measurements

We investigate quantum analogues of collision resistance and obtain separations between quantum "one-way" and "collision-resistant" primitives. 1. Our first result studies one-wayness versus collision-resistance defined over quantum circuits that output classical strings. We show that there is a classical oracle mathcal{O} relative to which (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a non-collapsing measurement oracle, mathcal{Q}^{mathcal{O}}. Very roughly, mathcal{Q}^{mathcal{O}} outputs the result of multiple non-collapsing measurements on the output of any quantum mathcal{O}-aided circuit. This rules out fully black-box {\em quantum} constructions of Y from X for any X in \{indistinguishability obfuscation and one-way permutations, public-key encryption, deniable encryption, oblivious transfer, non-interactive ZK, trapdoor permutations, quantum money\}, Y in \{collision-resistant hash functions, hard problems in SZK, homomorphic encryption, distributional collision-resistant puzzles\}. 2. Our second result studies one-wayness versus collision-resistance defined over quantum states. Here, we show that relative to the same classical oracle mathcal{O}, (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a {\em cloning unitary} mathsf{QCol}^mathcal{O}. Very roughly, this latter oracle implements a well-defined, linear operation to clone a subset of the qubits output by any quantum mathcal{O}-aided circuit. This rules out fully black-box constructions of quantum lightning from public-key quantum money.