How Not to Build Microcrypt

What it claims

Beyond the HPS result the summary names, the paper establishes two distinct results and a concrete taxonomy of which quantum pseudorandom constructions survive NP-aided attack. It separates two properties: computable states (amplitude and phase on any basis term efficiently computable from the key) are invertible in BQP^NP, giving only worst-case NP-hardness; sampleable + computable OWSGs additionally imply actual one-way functions. HPS falls in the second class, as does Morimae–Xagawa's IQP-based quantum group action proposal — both shown to imply OWFs, contradicting their intended purpose.

How it works

The tomography algorithm reduces the classical post-processing needed for shadow tomography from PP (the previously known bound, believed far stronger than NP) down to NP, by exploiting amplitude computability. Two measurements are combined:

• Computational-basis measurement yields samples; an NP oracle does maximum-likelihood search over exponentially many keys for one whose predicted probabilities p_h(x)=|a_h(x)|² best explain the transcript. This recovers magnitudes but discards phase.
• Phase extraction (building on KT25) uses a two-to-one function to collapse onto pairs x, x⊕Δ, then measures in {|x⟩±|y⟩} and {|x⟩±i|y⟩} bases. The signal weakens when amplitudes are imbalanced; rather than scrambling with a 2-design (which would destroy computability), they interfere the challenge against a reference state via controlled-SWAP to balance weights.

Evidence (PRU results)

The attacks extend to unitaries. Theorem 1.3: any family U_k = C₁,k P_k F_k C₂,k (Cliffords, a computational-basis permutation, a diagonal phase unitary) is learnable and distinguishable from Haar by BQP^NP. This covers the PFC architecture, the first proven-secure PRUs (MH25, MPSY24b), and recent constructions (FLM+26, CSBH25, FPVY25, REF26). Conclusion: these cannot be instantiated from assumptions weaker than NP-hardness.

Limits

• Results give no-go bounds, not constructions. Table 4 (not reproduced in the fetched text) lists architectures the techniques do NOT break — the actual pointer for someone seeking a viable Microcrypt route.
• Concurrent independent work: Carrasco et al. [CEG+26] also prove HPS→OWF via a state-certification framework; the authors call the broader results incomparable (they handle non-flat/nonuniform amplitude states; CEG+26 covers the flat setting).
• Section 8.5 explicitly flags limitations of the current techniques (not in fetched text).
• The OWSG-inversion theorem needs a stronger-than-usual correctness guarantee, which the authors note all proposed constructions happen to satisfy.