Stabilizer-Public-Key Authentication: Partial Prediction Bounds and Limits of Key Reuse

Abstract:We propose an information-theoretic authentication protocol based on a finite supply of quadratic-stabilizer public-key states over an odd-prime field. A computationally unbounded adversary observes one valid classical signature and may jointly process $N$ public-key copies, while verification uses one additional independent copy. We show that, conditioned on the exposed signature, the security problem reduces to a partial-prediction game for a uniform stabilizer ensemble on $r=n-\ell$ residual qudits, with a partial query along $d=rank(Y-Y')$ directions, where $n$ is the number of qudits, $\ell$ is the message-space dimension, and $Y$ and $Y'$ denote the honestly signed and target-forged messages, respectively. Surprisingly, although the target requires only partial information, there is no first-order reduction in the required copy rate when $d/r\to\beta\in(0,1]$. The optimal average fixed-target forgery probability tends to zero for $N/r\to\alpha<1$ and to one for $\alpha>1$, revealing a sharp threshold at $\alpha=1$. Thus, our results guarantee security against fixed-target forgery under a single-signature-exposure model.

arXiv:2609.20877 [quant-ph]

(or arXiv:2609.20877v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.20877 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.