cronokirby

(2026-05) Beyond Quadratic; Unlocking Pseudorandomness with Quartic Character

2026-05-15

Abstract

We study pseudorandomness arising from quartic Dirichlet characters and obtain results that connect analytic and cryptographic perspectives. From an analytic perspective, and following the framework of Mauduit and Sárközy, we define a Boolean function ψπ\psi_\pi from the quartic character χπ\chi_\pi modulo a Gaussian prime π\pi and analyze sequence Ep−1=(ψπ(1),…,ψπ(p−1))E_{p-1}=(\psi_\pi(1),\ldots,\psi_\pi(p-1)) for p=ππˉ≡1mod4p=\pi\bar\pi \equiv 1 \bmod{4}. Using classical character-sum bounds (Pólya-Vinogradov and refinements of Mauduit-Sárközy and Oon), we show that Ep−1E_{p-1} satisfies W(Ep−1)=O(p\logp)W(E_{p-1}) =O(\sqrt{p}\log p) and Cμ(Ep−1)≤2μ2+1μp\logp,C_{\mu}(E_{p-1}) \leq 2^{\frac{\mu}{2}+1} \mu \sqrt{p}\log p, which imply strong pseudorandomness for small μ\mu. From the cryptographic side, we resolve an open question posed by Damgård by proving that quartic characters yield the secure pseudorandom generators and weak pseudorandom functions (wPRFs). Adapting similar techniques of Corrigan-Gibbs and Wu, we have shown that distinguishing quartic wPRF implies solving quadratic residuosity, via a chain of polynomial-time reductions. Our results show that under the Quadratic Residuosity Assumption, the quartic character also yields cryptographically secure wPRFs whose one-wayness was assumed in the construction of Quartapus\mathsf{Quartapus} signature scheme by Brier et al. and the post-quantum secure signature scheme PorcRoast4\mathsf{PorcRoast}_{4} by Beullens et al. that are more efficient and secure than legacy schemes based on the Legendre character.