PaperlayerView exact revision on arXiv

Source-linked AI summary

Authentication over Arbitrarily Varying Channels with Causal Adversaries

Mayank Bakshi, Vinod M. Prabhakaran, Bikash Kumar Dey, Oliver Kosut

arXiv:2608.28939v1cs.IT

TL;DR

The paper studies authentication over AVCs with causal output-feedback adversaries and develops converse and achievability arguments for stochastic and deterministic codes. It characterizes positivity using distribution-overwritability and I-overwritability, and shows that positive stochastic authentication capacity reaches the no-adversary Shannon capacity.

  • Problem

    The paper asks when authentication remains possible over an AVC whose adversary selects states causally from past channel outputs, distinguishing stochastic from deterministic encoding.

  • Method

    The paper combines a posterior-based wait-and-overwrite attack for converses with overlap-controlled codes and martingale concentration for adaptive adversaries.

  • Results

    Stochastic authentication capacity is positive exactly when the channel is not distribution-overwritable, deterministic capacity is positive exactly when it is not I-overwritable, and positive stochastic capacity equals Cs0.

  • Takeaways & Limitations

    The causal stochastic-code and deterministic-code settings have distinct positivity characterizations, with stochastic encoding necessary for positive rates on some channels.

Abstract

from arXiv · show

We study authentication over a discrete memoryless arbitrarily varying channel (AVC) in which the adversary selects the channel state causally based on past channel outputs. We prove that the authentication capacity is positive exactly when the channel is not distribution-overwritable under stochastic encoding, and not I-overwritable under deterministic encoding. In the stochastic case, whenever the authentication capacity is positive, it coincides with the no-adversary Shannon capacity. Both converses follow from a novel wait-and-overwrite attack: the adversary tracks the no-adversary posterior over the message via the posterior guessing probability, and once it concentrates past a threshold, it samples a guess and a decoy from the posterior and overwrites the channel to mimic a no-adversary transmission of the decoy. The positivity results are obtained by constructing positive-rate codes with controlled overlap between codewords, together with a martingale concentration argument that handles adaptive adversarial strategies. For stochastic encoding, the full-capacity achievability further combines a capacity-achieving channel code with an authentication tag. These characterizations separate the causal stochastic-code and causal deterministic-code settings from each other and from the oblivious-adversary setting studied by Kosut and Kliewer.

I. INTRODUCTION

This paper studies authentication over an AVC where an output-feedback adversary causally selects channel states. It characterizes when stochastic and deterministic authentication capacities are positive and introduces a wait-and-overwrite converse.

  • Problem: The adversary observes past channel outputs and causally selects each channel state.This model is the output-feedback causal counterpart of the omniscient adversary and refines the oblivious-adversary model.
  • Main results: Stochastic authentication capacity is positive exactly when the AVC is not distribution-overwritable.The result is stated as Theorem 5.
  • Main results: Deterministic authentication capacity is positive exactly when the AVC is not I-overwritable.The result is stated as Theorem 7.
  • Main results: Whenever stochastic authentication capacity is positive, it equals the no-adversary Shannon capacity Cs0.This is the full-capacity characterization for stochastic codes.
  • Implications and scope: The two positivity conditions form a strict hierarchy, so some channels require stochastic codes for positive authentication rates.I-overwritability is strictly contained within distribution-overwritability; the positive deterministic capacity value remains open.
  • Techniques: The wait-and-overwrite attack tracks the posterior guessing probability, then uses a sampled guess and decoy to overwrite the channel.The achievability argument adapts overlapping-set constructions to feedback adversaries through martingale concentration.

B. Channel and adversary

The paper studies authentication over a discrete memoryless AVC with causal state selection based on past outputs, distinguishing stochastic and deterministic codes. It characterizes positivity through distribution-overwritability for stochastic codes and I-overwritability for deterministic codes, while identifying a capacity result for stochastic codes and an open rate question for deterministic codes.

  • Channel and adversary: The channel is a finite-alphabet discrete memoryless AVC with a fixed no-adversary state, and the adversary chooses each state before the channel produces its output.The receiver may output REJECT to flag the adversary’s presence.
  • Positivity conditions: Authentication capacity is positive for stochastic codes exactly when the channel is not distribution-overwritable.This condition is weaker than oblivious overwritability and is linked to a strict hierarchy of overwritability notions.
  • Capacity characterization: Whenever stochastic authentication capacity is positive, it equals the no-adversary Shannon capacity Cs0 for both feedback and no-feedback settings.The stated characterization concerns stochastic codes; the corresponding deterministic capacity equality remains unresolved.
  • Positivity conditions: Authentication capacity is positive for deterministic codes exactly when the channel is not I-overwritable.For deterministic codes, the paper establishes positivity but does not identify the achievable rate with Cs0.
  • Capacity characterization: The deterministic achievable rate remains unknown because, after waiting, the adversary may guess the intended codeword and act effectively omniscient, while the corresponding omniscient capacity is open.This leaves the deterministic authentication capacity as an open problem.

IV. THE WAIT-AND-OVERWRITE ATTACK

The paper develops a common wait-and-overwrite attack for stochastic and deterministic codes, using posterior concentration to switch from waiting to channel overwriting. Under the respective overwritability conditions, the attack creates authentication errors with constant probability.

  • Attack construction: The adversary waits under a fixed state until the no-adversary posterior guessing probability exceeds a threshold, then samples a guess and decoy from that posterior.The overwrite phase chooses causal state distributions so the output law matches a no-adversary transmission of the decoy under the guessed message’s encoder behavior.
  • Stopping-time control: Reliability forces the threshold stopping time to occur with high probability, while the posterior remains below 1/2 on the stopping event with probability at least 3/4.These stopping-time controls provide the non-degeneracy needed for the guess and decoy to differ from the true message with constant probability.
  • Attack success: The attack succeeds when the sampled guess equals the true message and the sampled decoy differs, an event having conditional probability G(1−G) and at least γ(1−γ) under the stopping event.Conditioned on success, the output is a no-adversary transcript of the decoy, so decoding it produces an authentication error with probability at least 1−ϵn.
  • Converse conditions: The converse applies to stochastic codes when the channel is distribution-overwritable and to deterministic codes when it is I-overwritable.The overwritability condition changes which channels admit the attack, not the attack’s success-probability mechanism.
  • Feedback: The same wait-and-overwrite attack applies with or without encoder feedback, so feedback does not change the positivity conclusions.The converse uses the encoder’s input distribution under feedback but does not require feedback to be present.

V. POSITIVITY PROOFS FOR THEOREMS 5 AND 7

The positivity proof constructs overlapping-set authentication codes and uses martingale concentration to control adaptive adversaries whose states depend on past outputs. Non-overwritability supplies a uniform per-symbol separation that yields positive-rate reliability and authentication.

  • Martingale concentration: A flip-set martingale makes the output deviations concentrate uniformly over adaptive strategies, with probability 1−e^−Ω(n).Azuma–Hoeffding applies because the centered output indicators have zero conditional mean, and the exponent depends only on the separation and alphabet parameters.
  • Achievability guarantee: For all sufficiently large blocklengths, the construction achieves positive authentication rate, no-adversary error at most λ1, and missed-detection error at most λ2 uniformly over feedback adversaries.The number of authentication messages satisfies N ≥ 2^R(auth)n for a positive rate R(auth).
  • Code construction: The construction uses exponentially many overlapping subsets of time positions, with controlled sizes, intersections, and an overlap property for decoding.The code transmits a distinguished symbol on each message’s subset and fresh i.i.d. inputs elsewhere.
  • Adaptive-adversary obstacle: Adaptive state selection prevents a direct independent per-letter analysis because outputs on the flip set are neither independent nor identically distributed.The adversarial strategy also ranges over an uncountable path-dependent class.

A. Achievability for deterministic codes (Theorem 7)

For deterministic codes, the stochastic construction specializes to a Dirac input distribution, converting distribution-overwritability gaps into I-overwritability gaps. The stochastic scheme reaches no-adversary capacity by appending a short authentication tag, but the deterministic proof leaves a capacity gap open.

  • Deterministic specialization: The deterministic encoder sends x′0 on each message subset and x0 elsewhere, while retaining the same overlapping-set codebook and flip-set concentration argument.The witness gap reduces from distribution-overwritability to I-overwritability, and Azuma–Hoeffding yields the same concentration.
  • Capacity boundary: The deterministic construction achieves a positive rate strictly below the no-adversary capacity under inputs restricted to {x0, x′0}.The gap to C* and, consequently, to Cs0 remains an open problem.
  • Authentication tags: The stochastic full-capacity construction composes an authentication code with an Ahlswede–Dueck identification code to obtain doubly-exponentially many tag candidates.The resulting tag provides deterministic candidate verifiers with low false-alarm and missed-detection error.
  • Full-capacity achievability: The achievability scheme concatenates a capacity-achieving no-adversary channel code with the authentication tag, using the tag over n2 = O(log n) symbols.The channel code carries the message while the tag carries a verification statistic.

B. Concatenation with a channel code

The full stochastic authentication capacity is achieved by concatenating a capacity-achieving channel code with an authentication tag. The resulting composite code preserves reliability and authentication while approaching the no-adversary Shannon capacity.

  • Construction: The achievability scheme concatenates a capacity-achieving channel code with an authentication tag at any rate R<Cs0.The tag length is logarithmic in the channel-code message-space size.
  • Construction: The decoder first obtains a candidate message from the channel code and then verifies that candidate using the tag.Rejection by the tag yields a rejected composite decoding outcome.
  • Error analysis: Under a no-adversary transmission, the channel stage recovers the message with probability at least 1−ϵn, while the tag has the correct verification behavior with probability at least 1−ϵn.The no-adversary error is bounded by 2ϵn.
  • Error analysis: Under an adversary, accepting an incorrect candidate is exactly a missed-detection event of the authentication tag.The tag construction controls this event uniformly over causal adversary strategies.
  • Capacity conclusion: The composite code achieves authentication error at most 3ϵn=o(1) at asymptotic rate R.Because R<Cs0 is arbitrary, the stochastic authentication capacity is at least Cs0 and therefore equals it.
  • Robustness: The adversary may decode the message during the wait phase and become effectively message-omniscient during the tag phase, yet the tag’s missed-detection bound remains valid.The bound relies on fresh i.i.d. encoder randomness on the flip set.

APPENDIX A

The appendix proves the converse through a wait-and-overwrite attack that waits for posterior concentration, samples messages from the posterior, and then matches the resulting transmission to a no-adversary transcript. The same argument specializes from stochastic distribution-overwriting to deterministic I-overwriting and also covers feedback encoders.

  • Wait-and-overwrite attack: The adversary stops at the first time the posterior guessing probability exceeds a threshold, then samples a guess and decoy from the posterior.This stopping rule drives the wait-and-overwrite attack.
  • Distribution matching: A per-step matching identity lets the overwrite phase reproduce the no-adversary output law associated with the decoy message.A telescoping argument shows that the resulting likelihood agrees with a no-adversary likelihood.
  • Authentication failure: The attack forces a non-rejection, incorrect-decoding event with conditional probability at least γ(1−γ)(1−ϵn) on the high-posterior event.The high-posterior event itself occurs with probability at least 3/4−ϵn/(1−√γ).
  • Deterministic specialization: In the deterministic case, the encoder marginal is a point mass, so distribution-overwriting reduces to the per-symbol I-overwriting condition.The remainder of the converse proof is unchanged and yields the same bound.
  • Feedback: The proof also covers feedback encoders because the causal adversary can compute the encoder’s conditional input distribution from the observed history.Thus encoder feedback does not change the converse.
  • Proof constants: Some numerical constants in the converse are proof artifacts, and tighter stopping-time arguments can improve them without changing the qualitative conclusion.The stated looseness comes from Markov’s inequality and a coarse lower bound.

DETAILED PROOFS FOR STOCHASTIC ACHIEVABILITY

The stochastic achievability proof constructs authentication tags from overlapping message-specific subsets and analyzes adaptive adversaries with a bounded-difference martingale. Non-distribution-overwritability supplies a uniform statistical gap that makes false alarms and missed detections vanish at positive rate.

  • Tag definition: An authentication tag uses a stochastic encoder together with deterministic candidate-indexed verifiers that accept or reject received outputs.Its rate is measured through doubly logarithmic message-space growth.
  • Code construction: The code construction assigns each message an overlapping subset Bm, with a flip-set overlap property controlling comparisons between candidate and transmitted messages.The flip set B_hatm\Bm prevents cancellation in the verification statistic.
  • Witness condition: Non-distribution-overwritability provides an input distribution PX and target symbol x′ whose induced output distributions remain separated under every adversarial state mixture.PX is used off the verification set, while x′ defines the verifier’s target distribution.
  • Error analysis: Hoeffding concentration and a union bound likewise make the false-alarm probability vanish when the rate satisfies the stated construction constraint.The resulting error events are o(1) uniformly over feedback adversaries.
  • Adaptive adversaries: On the flip set, fresh i.i.d. encoder inputs create a uniform per-history distributional gap against every causal adversary strategy.The gap holds at each history rather than only after averaging over strategies.
  • Error analysis: An Azuma–Hoeffding bound converts the per-history gap into exponentially small missed-detection probability, which remains negligible after union bounding over candidates.For a single incorrect candidate, the bound is at most 2e^(−c2n).

B. Proof of Lemma 15: lift via identification codes

The proof lifts a positive-rate authentication code to the doubly-exponential message size required for the authentication tag by composing it with an Ahlswede–Dueck identification code. The composite verifier inherits both false-alarm and missed-detection guarantees.

  • Composition: The lift composes the authentication code with an Ahlswede–Dueck identification code for a noiseless binary channel.The identification layer supplies the larger message space while the authentication layer protects its transmission.
  • Rate selection: The construction selects an authentication rate R below the positive auth-code rate and an intermediate rate_hatR between them.The identification rate is set to R/hatR.
  • Identification layer: The inner identification code uses a stochastic encoder and candidate-specific acceptance or rejection verifiers over binary codewords.Its codeword set has size at most the identification message-space size.
  • Composite decoder: The outer authentication code decodes either an identification codeword or REJECT before the candidate-specific identification verifier is run.This sequential decoder defines the composite tag.
  • Rate guarantee: The composite tag achieves the required doubly-exponential rate, satisfying (1/n)log log Nn≥R.The message-space embedding is feasible because the authentication code supports the needed rate.
  • Error guarantees: The composite false-alarm probability is at most λ1 by union bounding the authentication and identification false-alarm events.Each component contributes at most λ1/2.
  • Error guarantees: The composite missed-detection probability is controlled similarly by combining the authentication and identification missed-detection bounds.The authentication layer’s guarantee is uniform over feedback adversaries.

C. Concatenation with a channel code

The section concatenates a capacity-achieving channel code with a logarithmic-length authentication tag, while analyzing the tag against adversaries that inherit the wait-phase history. The resulting stochastic authentication rate approaches the no-adversary channel capacity.

  • Construction: The composite construction uses a length-n1 channel code at rate R<Cs0 and an (Nn,n2)-tag with n2=O(log n).The encoder and decoder combine the channel-code and tag phases.
  • Error analysis: The channel-code stage recovers the correct message with probability at least 1−ϵn, after which the tag accepts conditionally with probability at least 1−ϵn.A union bound controls the resulting no-adversary error.
  • Adversary analysis: The tag-phase adversary is induced by fixing the wait-phase realization, including its outputs and states, as a parameter.Its conditional actions use only tag-phase history while retaining the wait-phase outputs as a prefix.
  • Error analysis: For every incorrect candidate, the induced tag-phase analysis bounds acceptance by ϵn, and marginalization preserves this missed-detection bound.The total authentication error is bounded by the no-adversary error plus worst-case missed detection.
  • Rate: The composite rate is n1R/(n1+O(log n))→R, yielding C_auth,stoch≥R for every R<Cs0.This completes the achievability halves of Theorems 5 and 6.

APPENDIX E

Appendix E adapts the achievability proof to deterministic encoding and verifies examples separating I-overwritability from distribution-overwritability. It also shows that causal stochastic authentication can attain the no-adversary capacity in the AZBSC example.

  • Deterministic achievability: The deterministic achievability proof replaces the input distribution with a point mass and carries over the martingale and overlap arguments.The resulting encoder is a deterministic function of the message.
  • Deterministic achievability: The I-overwritability witness makes the distribution-overwritability gap reduce exactly to the defining I-overwritability condition.The proof uses the witness (x0,x′0,δ).
  • Deterministic achievability: The overlap-property bound depends only on codebook geometry, so it is identical in the stochastic and deterministic cases.The combining argument gives Pr_adv( M̂∉{m,REJECT})≤⌈2^nR⌉·2|Y|e^−c2μn=o(1) when R ln 2<c2μ.
  • Separating overwritability notions: For the binary noiseless-channel example, the no-adversary capacity is Cs0=1 bit/use, yet every input pair is I-overwritable.Randomized input distributions with p∈(0,1) cannot be distribution-overwritten.
  • Separating overwritability notions: In the AZBSC(δ,α), stochastic causal authentication achieves the BSC(δ) no-adversary capacity despite the channel not being obliviously overwritable.The example is distribution-overwritable but fails oblivious overwritability.
Loading 2608.28939v1…