Scalable pseudorandom unitaries with an independent security parameter

Unsolved ID op_f271040c57d9a513 Last edited 16 September 2026

Edit

Field: Quantum Cryptography
Topics: Computational complexity and computability
Quantum circuit complexity

Problem

Can pseudorandom-unitary security scale independently of Hilbert-space dimension while construction uses only polynomially many oracle queries?

For \(d=2^n\) and an independent security parameter \(\kappa\), seek a uniformly generated family \(\{U_{n,\kappa,f}\}_f\) indexed by Boolean functions \(f:\{0,1\}^r\to\{0,1\}\), with \(r,q\leq\operatorname{poly}(n,\kappa)\), and an algorithm \(\mathcal A^f\) using at most \(q\) oracle queries such that

\begin{equation} \left\|\mathcal A^f-U_{n,\kappa,f}(\,\cdot\,)U_{n,\kappa,f}^\dagger\right\|_\diamond \leq2^{-\kappa} \tag{1} \end{equation}

for every \(f\). For uniformly random \(f\), require

\begin{equation} \sup_{\mathcal D:\,\#\mathrm{queries}\leq2^\kappa} \left|\Pr_f[\mathcal D^{U_{n,\kappa,f}}=1] -\Pr_{V\sim\operatorname{Haar}(d)}[\mathcal D^V=1]\right| \leq2^{-\kappa}. \tag{2} \end{equation}

Does a family satisfying Eqs. (1) and (2) exist with no imposed relation between \(n\) and \(\kappa\)? The distinguisher accesses the ideal unitary, not the function \(f\).

Source

The question is explicitly posed or retained as open in the cited primary literature [Brakerski26]. The statement is rewritten here to make its hypotheses and success criterion self-contained.

Progress

Status: explicitly unresolved in the 2026 source. Brakerski and Yuen analyze this scalable formulation, establish barriers for existing candidates, and connect a positive answer to unitary synthesis. Their baseline construction has polynomial dependence on \(d\), rather than the required \(\log d\). Thus it does not resolve the displayed problem. [Brakerski26]
Their distinguishing attack on the PFC construction is not a universal impossibility theorem for scalable PRUs, and the paper leaves the general construction problem unresolved. [Brakerski26]

Comment

This is deliberately an oracle-query problem. A query-efficient construction is not automatically a gate-efficient, standard-model cryptosystem. That distinction should remain explicit in any proposed solution.

The independence of parameters is substantive. A distinguishing bound involving \(t^2/2^n\) may become small by increasing \(n\); it does not offer an independent security knob at fixed dimension. The requested construction must work when the allowed query count is large relative to dimension as well.

The object is a quantum operation, and the security criterion is operational distinguishability from Haar rather than a relationship between classical complexity classes.

References

[Brakerski26]: Zvika Brakerski and Henry Yuen, On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem. submitted 11 May 2026; CRYPTO 2026. See Definitions 4.1 and 4.4, §4.1, Lemma 4.7, and §6.link

Scalable pseudorandom unitaries with an independent security parameter

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems