A class of optimal authentication codes with secrecy

Source: arXiv:2605.14823 · Published 2026-05-14 · By Haibo Liu, Chengzhi Wei, Qunying Liao

TL;DR

This paper addresses the construction of authentication codes with secrecy that are both simple to implement and algebraically elegant. Authentication codes (A-codes) with secrecy differ from those without secrecy by hiding the source state in the encoded message using the shared secret key, protecting both authentication and confidentiality. The authors present a new class of linear authentication codes over finite fields, where the encoding rule maps a source state and key to a message constructed from field elements and trace functions. Using properties of special Weil sums and exponential sums over finite fields, the paper analytically derives closed-form expressions for the maximum success probabilities of impersonation (PI) and substitution (PS) attacks against these codes. It then rigorously proves that these probabilities asymptotically meet previously known information-theoretic and combinatorial lower bounds, thereby establishing the asymptotic optimality of the constructed codes.

Key findings

• The authentication code construction is defined over finite fields F_p^n with message space M = F_p^n × F_p and encoding rule Ek(s) = (s + k^p^r, Tr_r(s k)), where Tr_r is a trace function.
• The maximum success probability of impersonation attack PI is explicitly computed in Theorem 1 with exact closed form formulas dependent on p, n, r, and gcd(n,r). For example, for odd n, PI = 1/p + 1/p^{(n+1)/2}.
• The substitution attack maximum success probability PS is upper bounded in Theorem 2 with expressions involving powers of p and parameters n, v = gcd(n,r), and t = n/2; exact PS calculation is complex due to Weil sums.
• The codes asymptotically achieve the combinatorial lower bounds on PI and PS given by Lemma 2, i.e., lim_{n→∞} R/PI = 1 and lim_{n→∞} P/PS = 1 where R = |S|/|M| and P = (|S|-1)/(|M|-1).
• They also asymptotically satisfy the information-theoretic lower bound on PI from Lemma 1, linking the entropy terms to PI (Theorem 4).
• The algebraic approach leverages detailed exponential sum evaluations and properties of permutation polynomials over finite fields to derive attack probabilities.
• The codes have simple linear encoding rules without splitting, facilitating easy implementation compared to prior combinatorial constructions.
• The theoretical proofs rely heavily on special Weil sum properties, orthogonality of additive characters, and Gauss sums over finite fields.

Threat model

The adversary is capable of intercepting, inserting, or substituting messages on a public communication channel but lacks knowledge of the secret key or the exact encoding rule. Two attack types are considered: impersonation attacks where the adversary attempts to insert forged messages without prior observations, and substitution attacks where the adversary observes a legitimate message and replaces it with a forged one aiming to deceive the receiver. The adversary cannot break the finite field hardness or invert the secret key-based encoding without knowledge of the key.

Methodology — deep read

The paper starts by grounding its work in classical authentication code models with secrecy, where a shared secret key k is used to encode a source state s into a message m via a one-to-one encoding rule Ek(s). The authors specifically consider linear codes over finite fields F_p^n with p an odd prime, and utilize trace functions Tr_r to compose messages that both encrypt the source state and enable authentication.

1. Threat model and assumptions: The adversary can observe or insert messages on the public channel but does not know the secret key or encoding rule. Specifically, impersonation attacks allow arbitrary message insertion without seeing genuine messages; substitution attacks allow the adversary to observe a genuine message and attempt to replace it with another message, hoping for acceptance.

2. Data and spaces: Source states S, keys K, and messages M are finite field elements or tuples thereof. Here, S = K = F_p^n, M = F_p^n × F_p. Uniform probability distributions over these spaces are assumed. The encoding function E_k(s) = (s + k^{p^r}, Tr_r(s k)) maps each source state to a unique message.

3. Architecture/algorithmic components: Encoding is linear over F_p^n with an additive part s + k^{p^r} and a trace function output providing redundancy for authentication. The novel component is leveraging the special Weil sum S_{h,u}(a,b) and exponential sums to analyze authentication probabilities.

4. Training/analysis regime: Instead of training ML models, the work conducts rigorous algebraic analysis. Lemmas from number theory and finite field theory, particularly concerning additive and multiplicative characters, Gauss sums, and permutation polynomials, are applied. The authors derive closed-form expressions for the counts of solutions to certain equations over finite fields, which correspond to attack success probabilities.

5. Evaluation protocol: The main metrics are the maximum success probabilities PI for impersonation and PS for substitution attacks. These are compared against known information-theoretic and combinatorial lower bounds (Lemmas 1 and 2). Asymptotic optimality is established by taking n→∞ and showing ratios of these metrics converge to 1. Various cases depending on parity of n and gcd(n,r) are analyzed.

6. Reproducibility: The results are purely theoretical and algebraic. No code or experimental dataset is presented. All proofs rely on established lemmas regarding Weil sums and finite field properties from cited literature.

Concrete example: For odd n, by representing messages as (m1,m2) with m1 = s + k^{p^r} and m2 = Tr_r(s k), the authors count the number of keys k satisfying the verification equation Tr_r(m1 k - k^{p^r +1})=m2, using character orthogonality to transform counts into sums over additive characters. Applying known values of Weil sums allows explicit bounds of PI and PS to be computed. These counts directly relate to attack probabilities, which they analyze rigorously case-by-case.

Overall, the methodology involves sophisticated algebraic coding constructions combined with deep number theory and finite field analytic tools to derive exact and asymptotic authentication security guarantees.

Technical innovations

• New algebraic construction of linear authentication codes with secrecy based on finite field structures and trace functions.
• Explicit closed-form formulas for impersonation attack success probability PI using special Weil sums and Gauss sums.
• Derivation of upper bounds on substitution attack success probability PS via additive character orthogonality and exponential sum analysis.
• Proof that constructed codes asymptotically achieve both information-theoretic and combinatorial lower bounds on authentication probabilities, establishing asymptotic optimality.

Baselines vs proposed

• Information-theoretic lower bound (Lemma 1): PI ≥ 2^{H(E|M) - H(E)} and PS ≥ 2^{H(E|M^2) - H(E|M)}; proposed codes achieve these asymptotically as n→∞.
• Combinatorial lower bound (Lemma 2): PI ≥ |S| / |M| and PS ≥ (|S| -1) / (|M|-1); codes asymptotically meet these bounds.
• Exact PI formulas (Theorem 1) vs lower bounds: e.g., PI = 1/p + 1/p^{(n+1)/2} closely approaches 1/p = |S|/|M| as n increases.

Limitations

• Exact values of substitution attack probability PS are not fully determined; only upper bounds are provided due to complexity of Weil sums involved.
• Proofs of asymptotic optimality rely on n tending to infinity; finite-size performance or security is not empirically analyzed.
• The results assume uniform distributions over source and key spaces; real-world distributions may vary.
• Codes consider no splitting (one-to-one encoding), limiting applicability to constructions requiring splitting.
• Complexity of evaluating certain character sums prevents closed-form PS calculation in all cases.
• No explicit discussion of computational or implementation cost beyond stating simplicity of encoding.

Open questions / follow-ons

• Can the exact substitution attack success probability PS be tightly characterized rather than upper bounded?
• How do the codes perform against adaptive adversaries with partial key leakage or side information?
• Is it possible to extend construction to support splitting authentication codes and quantify their security?
• What are the practical computational costs and implementation trade-offs for these codes in real communication systems?

Why it matters for bot defense

For bot-defense practitioners, this paper provides a rigorous algebraic approach to designing authentication codes that provide both secrecy and authentication with provable security guarantees against impersonation and substitution attacks. Although not directly about CAPTCHAs or bot detection, the work highlights constructions of lightweight, mathematically grounded authentication schemes resistant to message forgery and replay threats—properties relevant to preventing automated spoofing or session hijacking common in bot attacks. The asymptotic optimality results suggest these codes can provide near-best security guarantees at minimal message overhead, which is useful where minimal user friction and strong verification are desired.

One technical insight useful for CAPTCHA or bot defense engineers is the exploitation of algebraic structures over finite fields and Weil sums to tightly bound adversarial success probabilities. Understanding these rigorous bounds may guide the design of challenge-response protocols or authentication tokens that are intrinsically resistant to brute force or substitution attacks without heavy computational costs. However, applying these principles in the bot-defense context would require integrating with probabilistic or interactive challenge mechanisms beyond static code constructions.

Cite

@article{arxiv2605_14823,
  title={ A class of optimal authentication codes with secrecy },
  author={ Haibo Liu and Chengzhi Wei and Qunying Liao },
  journal={arXiv preprint arXiv:2605.14823},
  year={ 2026 },
  url={https://arxiv.org/abs/2605.14823}
}

Read the full paper

• arXiv:2605.14823 (abstract)
• arXiv:2605.14823 (PDF)