Paper 2026/146

Feistel Tools: Reprogramming and Query-Recording for QRPs

Abstract

We present a new generic approach to extend proof techniques in the quantum random oracle model (QROM) — such as query-recording and reprogramming — to the quantum random permutation model (QRPM). Our framework involves simulating bidirectional-query random permutation oracles using Feistel constructions to port the QROM features for the underlying random round functions to the overall Feistel-simulated QRP. We then demonstrate the power of our framework by: • Obtaining a tighter than state-of-the-art lower bound for the query extrapolation problem — a variant of which was studied by Boneh and Zhandry (Eurocrypt 2013) in the QROM — in the bidirectional QRPM, as well as recovering a meaningful lower bound for the double-sided zero search problem (Unruh, Asiacrypt 2023). • Proving the adaptive zero-knowledge property of NIZKs derived from a recent variant of the Fiat-Shamir transform — called duplex-sponge Fiat-Shamir (Chiesa and Orrù, TCC 2025) which is deployed in the wild — in a post-quantum setting against non-uniform adversaries with preprocessing capabilities. All in all, our work illustrates how the “Feistel toolkit” effectively bridges the QROM-QRPM gap by not only achieving the standard QROM techniques of query-recording and reprogramming techniques for QRPs, but also unlocking new state-of-the-art features such as proving non-uniform security in the QRPM.