arXiv:2609.30253
How Not to Build Microcrypt
Aditya Gulati, Dakshita Khurana, Kabir Tomer
Abstract
A key challenge in quantum cryptography is to build quantum one-wayness and pseudorandomness without the use of (quantum computable) one-way functions. So far, this has turned out to be a difficult task, with only a few proposed candidates that are not directly built from one-way functions. Even within these few proposed candidates, we have lacked the techniques to analyze when proposed constructions may inadvertently yield one-way functions. In this work, we introduce efficient NP-aided shadow tomography of quantum states. We prove that collections of {\em computable} pure states can be learned via efficient NP-aided shadow tomography, where we say that a state is computable if the amplitude and phase on any computational basis term can be classically efficiently computed given the description of an efficient preparation circuit for the state. We also give new algorithms for NP-aided learning of unitaries given polynomially many queries to the unitary. By building on this, we show that many existing architectures for PRS and PRU, including some that were explicitly introduced for the purposes of avoiding one-way functions (e.g., Hamiltonian Phase States, Bostanci et. al., TQC 2025), actually do imply the existence of one-way functions or imply \(\NP\) hardness. We hope that these no-go results will inform future investigations into building PRS and PRUs from assumptions that are plausibly outside the complexity class NP.
AI Summary
The paper asks which quantum cryptographic constructions can avoid classical one-way functions, focusing on attacks using classical queries to an $\mathrm{NP}$ oracle. It studies pure-state families whose computational-basis amplitudes are classically computable to arbitrary precision given the key. For any such family with $L$-bit keys, an efficient quantum algorithm with classical $\mathrm{NP}$ access recovers a key specifying a state of fidelity at least $1-\varepsilon$, with probability at least $1-\delta$, using $O((L+\log(1/\delta))/\varepsilon)$ copies. The algorithm first fits the basis-measurement distribution by maximum-likelihood search, then prepares a magnitude-matched, positive-amplitude reference. Controlled-SWAP interference measurements expose relative phases, enabling a second likelihood search. When basis outcomes and keys are also classically samplable, replacing these searches with posterior sampling and distributional inversion yields quantum-secure classical one-way functions from pure-state OWSGs. Applications include finite-key Hamiltonian phase states and the specified IQP group-action candidates. A separate attack distinguishes Clifford–monomial–Clifford unitaries from Haar using $2m$ nonadaptive forward queries and one classical $\mathrm{NP}$ query. Bell measurements yield permutation-consistency constraints with short witnesses. Acceptance is certain for the construction and at most $2^L(3/4)^m$ for Haar when $m\leq2^n-2$. The state results require efficient amplitude computation; the one-way-function implication additionally requires classical sampling. Direct OWSG inversion assumes canonical verification or pointwise correctness. The techniques do not cover several multi-layer or overlapping architectures, long Kac walks, or secret general-unitary endpoints; absence of an attack is not a security claim.
Generative AI tools were used during the preparation of this manuscript to assist with writing, editing, and polishing the exposition, as well as to help formalize some ideas and check mathematical arguments and proofs.
Error found: The paper incorrectly asserts that searching its CMC displacement-consistency predicate recovers a close unitary: I and Z_1 produce identical transcripts for its probe despite having orthogonal normalized Choi states, so the advertised CMC unitary-learning result is unsupported.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.