Authentication over Arbitrarily Varying Channels with Causal Adversaries

I. INTRODUCTION

• The adversary chooses each channel state as a function of past states and past channel outputs, making this the output-feedback causal-adversary model.Source: §I · pp. 1–2
• Stochastic authentication capacity is positive iff the channel is not distribution-overwritable, while deterministic authentication capacity is positive iff it is not I-overwritable.These characterizations concern authentication against a causal adversary with output feedback.Source: §I · p. 2
• Whenever stochastic authentication capacity is positive, it equals the no-adversary Shannon capacity Cs0.Source: §I · p. 2
• I-overwritable channels form a strict subset of distribution-overwritable channels, so stochastic codes are necessary for positive rates on some channels; positive deterministic capacity remains open.Source: §I · p. 2
• The wait-and-overwrite converse tracks posterior guessing probability and enables converses for both stochastic and deterministic codes.Source: §I · pp. 2–3
• Achievability adapts ideas from to feedback adversaries using a martingale concentration argument.Source: §I · p. 3

A. Notation

• The notation defines [N] as {1, …, N}, uses script letters for finite alphabets, capitals for random variables and lowercase for realizations, and V for variational distance.Source: A. Notation · p. 3

B. Channel and adversary

• The model uses a finite-alphabet discrete memoryless channel with a fixed no-adversary state, where each output is drawn according to the input and adversary-selected state.The fixed-state channel is the legitimate channel, with Shannon capacity Cs0.Source: B. Channel and adversary · p. 3

C. Codes

• Codes are deterministic when each conditional law is a Dirac mass and stochastic otherwise; feedback permits the encoder to use past outputs.Without feedback, the encoder cannot condition Xt on Y t−1.Source: C. Codes · p. 3

D. Adversarial strategies and error metric

• The error quantity ϵn upper-bounds no-adversary error, so bounds stated for the latter also hold for ϵn.Q0 denotes the trivial adversarial strategy St ≡ s0.Source: D. Adversarial strategies and error… · p. 3

A. Overwritability conditions

• Distribution-overwritability and I-overwritability require matching the attacked channel to the no-adversary channel at different levels of granularity.Oblivious overwritability implies distribution-overwritability, which implies I-overwritability, and both implications are strict: the bit-flip channel is I-overwritable but not distribution-overwritable, while AZBSC(δ, α) is distribution-overwritable but not obliviously overwritable,.Source: A. Overwritability conditions · p. 4

B. Authentication capacity and positivity conditions

• Theorem 5 characterizes positivity for stochastic codes by equivalent conditions, including that the channel is not distribution-overwritable.Source: B. Authentication capacity and… · p. 4
• Deterministic authentication has positive capacity exactly when the channel is not I-overwritable, but its achievable rate is not known to equal the no-adversary capacity.The paper leaves deterministic authentication capacity open; after the wait phase, the adversary may guess the intended codeword and act effectively omniscient.Source: B. Authentication capacity and… · pp. 4–5

IV. THE WAIT-AND-OVERWRITE ATTACK

• The converse analysis for both theorems builds on a wait-and-overwrite attack that uses posterior guessing probability to switch between waiting and overwriting.The attack’s central quantity is the posterior guessing probability.Source: §IV · p. 5

A. The attack

• The adversary waits using state s0 until the no-adversary posterior exceeds γ, then samples a guess and decoy from that posterior and chooses states to mimic transmission of the decoy.The overwrite phase matches the marginal output law of a no-adversary decoy transmission.Source: A. The attack · p. 5

B. Stopping-time lemma

• Reliability forces the posterior threshold time Tγ to occur by blocklength n with high probability, while at Tγ the posterior stays below 1/2 with probability at least 3/4.This non-degeneracy gives the sampled guess and decoy a constant probability of differing from the true message.Source: B. Stopping-time lemma · p. 6

C. Proof of converses

• The per-step overwrite construction differs by code type: stochastic codes use conditional input distributions, while deterministic codes use message- and feedback-determined codeword symbols.In both cases, the adversary chooses a state distribution to match the decoy’s no-adversary conditional output law.Source: C. Proof of converses · p. 6
• On the stopping event, the attack succeeds with conditional probability at least γ(1−γ); its decoy-like transcript makes the decoder output a wrong message with probability at least 1−ϵn.The success event is {ˆm=M, ˜m≠M}; the proposition’s bound also uses Pr(E)≥3/4−ϵn/(1−√γ).Source: C. Proof of converses · p. 6
• Proposition 11 establishes the converse halves of Theorems 5 and 7 for stochastic codes on distribution-overwritable channels and deterministic codes on I-overwritable channels.The proposition applies to blocklength-n feedback codes; in the deterministic case, the stated authentication-error bound is zero.Source: C. Proof of converses · pp. 6–7
• The same attack applies with or without encoder feedback, so the converse covers both Cfb and Cno-fb.Its construction uses the encoder’s input distribution under feedback and does not require the absence of encoder feedback.Source: C. Proof of converses · p. 7

• Positive-rate codes achieve no-adversary error at most λ1 and missed-detection error at most λ2 uniformly over feedback adversaries for all sufficiently large n.The construction targets a code rate R(auth) > 0.Source: §V · p. 7

Step 1: Codebook

• Step 1 builds overlapping subsets with controlled sizes and pairwise intersections, adapting the scheme of to the output-feedback setting.The family’s overlap property is used in the decoding-error analysis.Source: §V · p. 7

Step 2: Encoder/Decoder

• Step 2 encodes with a non-overwritability witness and accepts only a unique message whose output-type test passes.The encoder sends x′ on the message’s subset and draws fresh i.i.d. inputs from PX elsewhere.Source: §V · p. 7

Step 3: Decoding-error bound

• Step 3 reduces wrong-message decoding error to a flip-set total-variation bound: on every history, π_t is at least δ from W(· | x′, s0), with failure probability 1−e−Ω(n) uniformly over Q.The exponent depends only on (δ, α, β, |Y|).Source: §V · p. 7

A. Achievability for deterministic codes (Theorem 7)

• For deterministic achievability, the encoder sends x′0 on Bm and x0 outside Bm, specializing the stochastic construction to PX = δx0.The witness gap becomes the I-overwritability gap, while the codebook and overlap property remain unchanged because they depend on set geometry.Source: A. Achievability for deterministic… · p. 8
• On the flip set, deterministic transmission of x0 gives a conditional Bernoulli mean uniform over Q, and Azuma–Hoeffding yields the same flip-set concentration.The proof uses the same bounded-difference martingale argument as in the stochastic case.Source: A. Achievability for deterministic… · p. 8
• The deterministic construction achieves a positive rate strictly below C*, but closing the gap to C*—and thus to Cs0—remains open.Cs0 is the no-adversary Shannon capacity under inputs restricted to {x0, x′0}.Source: A. Achievability for deterministic… · p. 8

VI. CAPACITY FOR STOCHASTIC CODES (THEOREM 6)

• The stochastic construction reaches the no-adversary capacity by combining a tag with a capacity-achieving code for the sub-channel W(y|x, s0).The channel code carries the message in n1 symbols, while the tag carries a verification statistic in n2 = O(log n) symbols.Source: §VI · p. 8

A. Authentication tags

• An authentication tag uses a stochastic encoder and deterministic candidate-message verifiers designed for low false-alarm and missed-detection error.Each verifier first runs the authentication-code decoder and then the identification verifier on the decoded codeword.Source: A. Authentication tags · p. 8
• If the channel is not distribution-overwritable, authentication tags exist with positive rate and arbitrarily small fixed false-alarm and missed-detection errors for sufficiently large n.The tag construction composes an authentication code with an Ahlswede–Dueck identification code for the noiseless binary channel, yielding doubly exponentially many candidates.Source: A. Authentication tags · p. 8

B. Concatenation with a channel code

• The scheme combines a capacity-achieving channel code with the Lemma 15 tag, using tag blocklength n2=Ω(log log⌈2nR⌉)=O(log n).The decoder first decodes a candidate message from the channel-code portion, then verifies it using the tag.Source: B. Concatenation with a channel code · p. 9
• With no adversary, the composite decoder’s error probability is at most 2ϵn.The channel-code stage recovers the message with probability at least 1−ϵn, and the verifier accepts the correct tag with probability at least 1−ϵn.Source: B. Concatenation with a channel code · p. 9
• The concatenated code achieves authentication error at most 3ϵn=o(1) at rate nR/(n+O(log n))→R for any R<Cs0.Thus stochastic authentication capacity reaches Cs0, matching the trivial reverse inequality.Source: B. Concatenation with a channel code · p. 9
• Even if the adversary decodes the message during the wait phase, the tag’s missed-detection bound holds uniformly over its adaptive strategies.Fresh i.i.d. encoder inputs on the flip set hide each Xt, while the non-distribution-overwritability gap controls πt uniformly over QSt|Ft−1.Source: B. Concatenation with a channel code · p. 9

VII. CONCLUSION

• Stochastic authentication capacity is positive exactly when the channel is not distribution-overwritable, and then equals Cs0; deterministic-code positivity holds exactly when the channel is not I-overwritable.Characterizing deterministic-code capacity remains open.Source: §VII · p. 10
• The converses use a wait-and-overwrite attack based on posterior guessing probability, while achievability uses overlapping-set codes and martingale analysis of adversarial adaptivity.Reaching Cs0 further composes the authentication tag with a channel code.Source: §VII · p. 10
• Future work includes continuous alphabets, feedback adversaries with delayed or noisy observations, and multi-user settings.Source: §VII · p. 10

APPENDIX A SUB-MULTIPLICATIVE GROWTH OF THE GUESSING PROBABILITY

• Appendix A states a lemma establishing sub-multiplicative growth of the guessing probability under the no-adversary law.The proof squares and sums over messages.Source: Appendix A · p. 12

APPENDIX B

• Appendix B defines Tγ as the first time the posterior guessing probability exceeds γ and proves that, given Tγ ≤ n, the probability it exceeds 1/2 at Tγ is less than 1/4.The appendix also uses the conditional MAP error and guessing-probability bounds to prove (4).Source: Appendix B · p. 13

APPENDIX C DETAILED PROOF OF THE CONVERSE

• For distribution-overwritable channels, the proof establishes a per-step matching identity by selecting a state distribution that matches the attacked encoder marginal to a no-adversary transmission.The state distribution is obtained by averaging the per-symbol witnesses.Source: Appendix C · p. 14
• A telescoping identity converts the post-stopping attack likelihood into a no-adversary likelihood, enabling separate bounds on rejection and correct decoding.The proof then combines those bounds with the high-probability stopping estimates.Source: Appendix C · pp. 14–15
• After Tγ, the attack samples the guessed message and a decoy independently from the posterior, while the wait phase fixes the state to s0.The explicit attack distribution weights these samples by the posterior given the stopped output and state history.Source: Appendix C · p. 14
• On event E, the authentication error is at least γ(1 − γ)(1 − ϵn), and the attack reaches E with probability at least 3/4 − ϵn/(1 − √γ).The argument uses posterior sampling and matching to make the channel output a no-adversary transcript of the decoy.Source: Appendix C · p. 16
• For deterministic encoders, the matching reduces to per-symbol I-overwritability and the same bound holds; feedback leaves the encoder distribution computable to the adversary.The adversary can compute that distribution from its past outputs and states, so the matching proof still applies.Source: Appendix C · p. 16

APPENDIX D DETAILED PROOFS FOR STOCHASTIC ACHIEVABILITY

• An (N, n)-authentication tag consists of a stochastic encoder and deterministic verifiers indexed by the receiver’s available candidate message.The encoder maps messages to distributions over input sequences; each verifier maps output sequences to ACCEPT or REJECT.Source: Appendix D · p. 16
• The tag’s error pair is defined with respect to feedback adversary strategies.The supplied passages do not include the error-pair inequalities.Source: Appendix D · p. 16
• The tag capacity is the supremum of rates achievable by sequences of tags for every error pair in (0, 1)^2, with lim inf (1/n) log log N_n at least the rate.The sequence has blocklength n and tag size N_n.Source: Appendix D · p. 16

A. Auth-code construction: detailed proof of the achievability of Theorem 5

• A single template handles stochastic and deterministic encoding: the deterministic case specializes the witness distribution to PX = δx0.The witness distribution comes from non-distribution-overwritability, and x′ is the target symbol used by the verifier.Source: A. Auth-code construction: detailed… · pp. 16–17
• The codebook’s overlap property controls match-versus-flip cancellation, letting the proof lower-bound full-set total variation using the flip set, up to a tunable correction.The construction uses message-specific subsets Bm, with an overlap condition for every output sequence and pair of messages.Source: A. Auth-code construction: detailed… · p. 17
• On flip positions, the encoder draws inputs independently from PX, while a history-dependent adversary chooses states; a uniform per-history gap enables one Azuma bound for all strategies.The flip-set TV deviation yields an exponentially small missed-detection probability for each incorrect candidate.Source: A. Auth-code construction: detailed… · p. 18
• Both error probabilities are o(1) uniformly over feedback adversaries when R satisfies the proof’s rate bound.The proof obtains exponentially small error for each candidate and uses a union bound over messages.Source: A. Auth-code construction: detailed… · pp. 17–18

B. Proof of Lemma 15: lift via identification codes

• Following, the construction composes the authentication code with an Ahlswede–Dueck identification code for the noiseless binary channel.The receiver first decodes an identification codeword or rejects using the authentication verifier, then runs the candidate-specific identification verifier on the decoded word.Source: B. Proof of Lemma 15: lift via… · p. 19
• The composition matches Lemma 15’s rate claim for any R<R(auth), choosing the blocklength so the authentication-code message space can represent the identification codewords.The proof chooses an intermediate rate between R and R(auth), then uses n large enough to accommodate the identification codeword space.Source: B. Proof of Lemma 15: lift via… · p. 19
• The composite code has false-alarm error at most λ1 and missed-detection error at most λ2, by union-bounding the authentication and identification error events.The authentication code’s no-adversary and missed-detection errors are each bounded by min{λ1/2, λ2/2} uniformly over feedback; the missed-detection bound applies uniformly over feedback adversaries.Source: B. Proof of Lemma 15: lift via… · pp. 19–20

C. Concatenation with a channel code

• The construction concatenates a length-n1 channel code of rate R<Cs0 and no-adversary error ϵn=o(1) with an (Nn,n2)-tag, where n2=O(log n), using a product encoder and composite decoder.Source: C. Concatenation with a channel code · p. 20
• Freezing each wait-phase realization induces a valid feedback adversary for the tag phase, so the tag’s false-acceptance probability remains at most ϵn even when the adversary observed wait-phase outputs.Source: C. Concatenation with a channel code · p. 20
• The composite authentication error is bounded by the no-adversary error plus worst-case missed detection, and its rate nR/(n1+n2) approaches R, yielding authentication capacity at least R for every R<Cs0.The tag length is O(log n), so its overhead vanishes asymptotically.Source: C. Concatenation with a channel code · p. 20

APPENDIX E — PROOF OF DETERMINISTIC ACHIEVABILITY (THEOREM 7)

• Replacing PX with δx0 makes the deterministic achievability encoder output x′0 on Bm and x0 otherwise.Source: PROOF OF DETERMINISTIC ACHIEVABILITY… · p. 21
• The martingale concentration step and codebook-overlap bound carry over unchanged; Azuma–Hoeffding applies with |Z|≤1, independent of the input distribution.Source: PROOF OF DETERMINISTIC ACHIEVABILITY… · p. 21
• For R ln 2<c2µ, the combining argument gives Pradv(Mhat ∉ {m, REJECT})=o(1), proving Theorem 7’s achievability.Source: PROOF OF DETERMINISTIC ACHIEVABILITY… · p. 21

APPENDIX F BIT-FLIP CHANNEL: I-OVERWRITABLE BUT NOT DISTRIBUTION-OVERWRITABLE

• The bit-flip AVC is I-overwritable for every input pair, yet no oblivious state mixture matches its no-adversary marginal for genuinely randomized inputs.Source: Appendix F · p. 21

APPENDIX G AZBSC(δ, α): DISTRIBUTION-OVERWRITABLE BUT NOT OBLIVIOUSLY OVERWRITABLE

• For every admissible (δ, α), matching both AZBSC inputs forces q0+q1 =(1−2δ)/(1−2δ−α) outside [0, 1], ruling out oblivious overwritability.Source: Appendix G · p. 22
• C•auth,stoch = Cs0, the no-adversary BSC(δ) capacity, although the AZBSC channel is not obliviously overwritable, a conclusion the dichotomy of would not yield.Source: Appendix G · p. 22