Abstract:We show new constructions for pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators satisfying scalability, which means the security parameter can be much larger than the number of qubits, quantum accessibility, which means the adversary can provide quantum input, and adaptivity, which means the adversary can query it adaptively.
We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions. Compared to prior PRFS works, we use a stronger definition of quantum accessibility in which the adversary can be ancilla-assisted, i.e., the input state may not be pure and could be entangled with other quantum registers. Thus, our result also gives the first (fully) quantum-accessible PRFS.
Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS. This new construction may be helpful in simplifying the microcrypt zoo.
From: YaoNan Zhang [view email]
[v1]
Wed, 30 Jul 2025 10:02:45 UTC (42 KB)
[v2]
Wed, 6 Aug 2025 07:40:55 UTC (38 KB)
[v3]
Sat, 13 Sep 2025 15:35:23 UTC (39 KB)
[v4]
Tue, 17 Feb 2026 09:46:06 UTC (47 KB)
[v5]
Mon, 13 Jul 2026 08:56:58 UTC (48 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。