MRS‑AUTH – A Post‑Quantum Authentication Framework with Active Verifier Resistance and Deniability

Abstract

MRS‑AUTH is a novel authentication framework that achieves deniability even against an active verifier who may adaptively query candidate credentials both before and after receiving a challenge. Unlike ring signatures or zero‑knowledge proofs – where the prover holds a single secret witness that can be extracted under coercion – MRS‑AUTH exploits the multiplicative structure of linear Diophantine equations. Through recursive decomposition, it generates a Diophantine forest of exponentially many syntactically valid credential chains. The authentic chain is sampled uniformly from this forest and committed together with k‑1 indistinguishable aliases using a fixed‑shape Merkle tree with dummy leaves, eliminating structure‑ and length‑based side‑channel leakage. The Forest Symmetry Theorem proves that all chains are structurally information‑theoretically indistinguishable. However, the full index‑anonymity against an active verifier is computational and bounded in Theorem 6.6 by k · ε_SHA3 + ε_coll + negl(λ). For cryptographic scales N ∼ 10⁴², the Ehrhart‑based continuous‑volume approximation yields an effective entropy exceeding 371 bits, with a statistical distance to the perfect uniform distribution of Δ ≤ 2⁻¹³⁵ – well below the 128‑bit security threshold. Empirical validation via exact enumeration and a chi‑squared test (χ²/dof ≈ 0.985) confirms the uniformity. A constant‑time Rust implementation, leveraging the subtle and zeroize crates, exhibits an execution time of approximately 0.12 ms across four orders of magnitude of N, demonstrating practical deployability. The work also formalises the Active Verifier Game model, a new adversarial definition that quantitatively captures coercion resistance in a post‑quantum setting.