⚛️ quantum physics

Parallel Kac's Walk Generates PRU

This paper proves that a linear number of sequential repetitions of the parallel Kac's Walk constitutes an adaptive-secure pseudorandom unitary family with strong resistance to inverse queries, thereby confirming a prior conjecture and demonstrating the efficacy of the path recording technique.

Original authors: Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao

Published 2026-09-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern cryptography, the goal is often to create things that look completely random to anyone trying to peek inside, yet are generated by a specific, hidden rule. In the classical world, we rely on tools like pseudorandom functions and permutations to secure our digital lives, ensuring that encrypted messages remain unreadable to hackers. As we move into the quantum era, where computers can process information in fundamentally different ways, scientists need new tools that are just as secure against quantum attackers. One such tool is the "pseudorandom unitary," a complex mathematical object that acts like a random shuffling of quantum states. It is efficient to build, but so thoroughly scrambled that no one can tell the difference between it and a truly random shuffle, even if they have the power to ask questions and see the answers in both forward and reverse directions. For a long time, the only known way to build these secure quantum shufflers relied on a specific, somewhat rigid recipe involving a sequence of three distinct steps.

A team of researchers has now discovered a different path to the same destination, proving that a method based on a concept called "parallel Kac's walk" can generate these secure quantum shufflers just as effectively. This approach draws inspiration from a mathematical model originally proposed in 1956 to describe how particles mix in a gas. In the quantum version, imagine a system of many possible states. Instead of shuffling them all at once, the process picks pairs of these states and applies a random, tiny rotation to each pair simultaneously. By repeating this simple pairing and rotating process a number of times that grows linearly with the size of the system, the entire collection of states becomes thoroughly mixed. The researchers demonstrated that if you take this mixing process and replace the truly random choices with secure, computer-generated pseudorandom choices, the result is a robust quantum shuffler. This new construction is not only secure against standard attacks but also holds up against adversaries who can query the system in reverse, a feature that makes it exceptionally strong.

The significance of this work lies in its departure from the established norms. Until now, every proven method for creating these secure quantum shufflers followed a specific pattern known as the PFC construction, which layers a random permutation, a phase shift, and another permutation in a fixed sequence. The new method breaks this mold entirely. Instead of layering different types of operations, it relies on the repeated application of a single, uniform module: the parallel Kac's walk step. This is akin to building a secure lock not by combining three different types of gears, but by repeating a single, well-designed gear mechanism many times. The researchers showed that after a linear number of these repetitions, the system achieves a level of randomness that is computationally indistinguishable from true randomness. This means that for any practical purpose, an observer cannot tell whether they are interacting with the constructed system or a perfectly random one, even if they are allowed to make a polynomial number of queries.

The proof of this security relies on a sophisticated technique called "path recording," which allows the researchers to track how an adversary interacts with the system without actually knowing the secret key. They showed that after a certain number of steps, the system effectively forces the adversary's view into a specific, restricted state where the randomness is guaranteed. By carefully analyzing how the system behaves when the adversary tries to probe it from different angles, including by reversing the operations, the team confirmed that the construction remains secure. This finding is particularly important because it provides a second, independent candidate for a fundamental cryptographic primitive. In security, having multiple different ways to build the same secure object is vital; if a weakness is ever found in one design, the other can serve as a backup. Furthermore, this new construction is conceptually simpler, relying on the repetition of a basic unit rather than a complex assembly of different components, which could make it easier to implement in future quantum hardware.

The researchers also explored the potential for further simplification, suggesting that the random rotations used in each step might eventually be replaced by a single, identical rotation repeated throughout the process, or that the complex permutations could be swapped for simpler local swaps. If these simplifications hold true, the result would be a system of local random circuits that is both efficient and secure, solving a long-standing question in the field. While these specific simplifications remain open questions for future study, the core result stands firm: a linear number of parallel Kac's walk steps is sufficient to generate a secure pseudorandom unitary. This work not only confirms a previous conjecture but also expands the toolkit available to quantum cryptographers, offering a fresh perspective on how to build the unbreakable locks of the quantum future.

Technical Summary: Parallel Kac's Walk Generates PRU

Problem Statement

The construction of Pseudorandom Unitaries (PRUs)—ensembles of unitaries that are efficiently implementable yet computationally indistinguishable from Haar-random unitaries by any quantum polynomial-time distinguisher—has been a significant challenge in quantum cryptography. While Pseudorandom States (PRSs) were established earlier, PRUs remained elusive.

Recent breakthroughs by Metger, Poremba, Sinha, and Yuen [MPSY24] introduced the PFC construction (a sequence of random Clifford, random phase, and random permutation gates), which was subsequently proven by Ma and Huang [MH25] to be adaptive-secure against adversaries. However, all known provably secure PRU constructions to date follow this PFC paradigm. The open question addressed in this work is whether alternative constructions, specifically those based on random walks on unitary groups, can also achieve PRU security.

Methodology

The authors analyze the Parallel Kac's Walk, a variant of the classical Kac's walk (a random walk on unitary groups) adapted for quantum computing. In a single step of the parallel Kac's walk:

A random permutation $\sigma$ is applied to the computational basis, pairing basis states $|i\rangle$ and $|j\rangle$ such that they share the same suffix of length $n-1$ .
For each pair, an independent $2 \times 2$ Haar-random unitary is applied.

The proposed construction, denoted as $HP_{n, T}$ , consists of $T$ sequential repetitions of this parallel Kac's walk step, where the random functions and permutations are replaced by quantum-secure pseudorandom counterparts (QPRF and QPRP). The authors set $T = O(n)$ (specifically $30n$ ) to ensure the construction is efficient (linear in the number of qubits).

The proof strategy relies on the path-recording technique introduced by Ma and Huang [MH25], adapted to the specific structure of the Kac's walk. The methodology proceeds in three main phases:

Projection to Distinct Block Subspace: The authors first demonstrate that $O(n)$ steps of the parallel Kac's walk act as a "random state scrambler" (RSS). When followed by a random permutation, the adversary's state is projected with high probability into the distinct block subspace. In this subspace, the query tuples $(x_1, \dots, x_t)$ belong to distinct blocks (where a block is defined by the suffix of the bit string). This projection is crucial because the security analysis relies on the adversary's queries being restricted to these distinct blocks.
Purified Oracle and Path Recording: The authors introduce a Purified Function-Permutation Oracle (HPO) to model the adversary's interaction with the random unitary $H_f \cdot P_\sigma$ . They define a new Path-Recording Oracle (PR) tailored to the distinct block subspace. Unlike the standard path-recording oracle which tracks distinct elements, this variant ensures that sampled outputs belong to distinct blocks.
Indistinguishability via Isometry: A key technical contribution is the construction of an isometry, Compress, which maps the environment state of the purified HPO oracle to the state space of the path-recording oracle. The authors prove that if the adversary's state resides in the distinct block subspace (guaranteed by the initial $O(n)$ steps), the behavior of the parallel Kac's walk step is indistinguishable from the path-recording oracle. Since the path-recording oracle is indistinguishable from a Haar-random unitary under these constraints, the entire construction is proven secure.

Key Contributions and Results

1. Adaptive-Secure PRU Construction

The paper proves that a linear number of sequential repetitions of the parallel Kac's walk forms an adaptive-secure PRU.

Theorem 1 (Informal): The distribution of a unitary corresponding to an $O(n)$ -step random parallel Kac's walk is computationally indistinguishable from the Haar distribution against adaptive adversaries.
Theorem 16: Formally establishes that $HP_{n, T+1}$ (with $T=30n$ ) is computationally indistinguishable from the Haar distribution.

2. Strong Security Against Inverse Queries

The construction is shown to satisfy strong security, meaning it remains indistinguishable from Haar random even when the adversary has access to both forward ( $O$ ) and inverse ( $O^\dagger$ ) queries.

Theorem 33: By using $2T+1$ steps (specifically $HP_{n, 2T+1}$ ), the construction achieves statistical strong security. This implies the existence of computationally strong PRUs under the assumption of post-quantum one-way functions.

3. Alternative to the PFC Paradigm

This work provides the first secure PRU construction that deviates significantly from the PFC (Clifford-Phase-Permutation) paradigm.

The construction is modular, consisting of repetitions of a basic "scrambling" module (the parallel Kac's walk step).
It offers a new perspective on PRU design, suggesting that a "filter" (like a 2-design or RSS) followed by a single step of a "randomness compiler" (like the parallel Kac's walk) can yield a full PRU.

4. Generalization of Security Conditions

The authors distill a general condition (Theorem 32 and Theorem 34) for PRU and strong-PRU construction. They show that any unitary distribution $K$ that approximates Haar randomness under specific twirling operations (e.g., being an approximate 2-design or an RSS), when composed with a single step of parallel Kac's walk, yields a PRU. This provides a template for generating new PRU candidates.

Significance and Claims

The paper claims to confirm a conjecture from [LQS+26] that the parallel Kac's walk can generate a PRU. Its significance lies in:

Diversification of PRU Candidates: By providing a construction outside the PFC family, it mitigates the risk associated with potential vulnerabilities in a single paradigm.
Demonstration of Path-Recording Versatility: The work extends the path-recording technique to handle the "distinct block" structure inherent in Kac's walks, showcasing the technique's adaptability for analyzing different quantum random processes.
Connection to Classical Cryptography: The iterative nature of the construction (repeating a basic module) draws a parallel to classical block ciphers like AES and Feistel networks, offering a quantum analogue to these well-understood structures.

The authors remain modest regarding efficiency, noting that their construction does not currently offer asymptotic efficiency advantages over the PFC construction. They identify open questions, such as whether the number of rounds can be reduced to a constant or if the construction can be simplified to local random circuits, which would resolve a long-standing open problem in quantum complexity theory.