Non-malleable Coding for Arbitrary Varying Channels

Fuchun Lin; Huaxiong Wang; Reihaneh Safavi-Naini; San Ling

arxiv: 1906.11066 · v2 · pith:UZFGS3HTnew · submitted 2019-06-26 · 💻 cs.IT · math.IT

Non-malleable Coding for Arbitrary Varying Channels

Fuchun Lin , San Ling , Reihaneh Safavi-Naini , Huaxiong Wang This is my paper

Pith reviewed 2026-05-25 15:09 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords non-malleable codesarbitrary varying channelsAVCtamperingadversarial channelsbinary channelsinformation theoretic securitycoding theory

0 comments

The pith

Non-malleable codes achieve rates approaching 1 over binary arbitrary varying channels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that non-malleable coding can be applied to arbitrary varying channels, where an adversary controls transmission by choosing a sequence of channel states. Non-malleability ensures that any tampering outcome depends only on the chosen states and not on the original message. The central result shows this property is achievable at rates that approach 1 for binary discrete memoryless AVCs. The work also sketches a scheme that adds exact message recovery when a designated special state is applied to every bit. A reader would care because the result extends tampering protection from fixed function families to a model of fully adversarial communication channels.

Core claim

Non-malleability for binary discrete memoryless arbitrary varying channels is achievable at a rate asymptotically approaching 1. The codes guarantee that the result after any state sequence is applied depends only on that sequence and not on the message. For the variant with a special state s*, an encoding scheme is outlined that achieves both non-malleability and full message recovery when s* acts on all transmitted bits.

What carries the argument

Non-malleable encoding against the family of tampering functions induced by AVC state sequences, where each state determines the output symbol for each transmitted bit.

If this is right

The non-malleable rate can match the ordinary transmission rate of the AVC without any tampering constraint.
Non-malleability holds against every possible adversarial choice of state sequence.
In the special-state variant, exact recovery is possible whenever the designated state is used on the entire block.
The construction applies the non-malleability goal directly to the standard AVC transmission model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar rate-1 results may hold for non-binary or continuous AVCs if the state set remains finite.
The approach could be combined with existing AVC capacity-achieving codes to add tampering resistance at negligible rate loss.
Constructions might be tested on concrete AVC examples such as binary symmetric channels with an adversarial crossover probability.

Load-bearing premise

That all possible tamperings are captured exactly by selections from the finite set of channel states in a binary discrete memoryless model.

What would settle it

An explicit binary AVC and a proof that every encoding with rate above some fixed number strictly less than 1 fails non-malleability for some state sequence.

read the original abstract

Non-malleable codes protect against an adversary who can tamper with the coded message by using a tampering function in a specified function family, guaranteeing that the tampering result will only depend on the chosen function and not the coded message. The codes have been motivated for providing protection against tampering with hardware that stores the secret cryptographic keys, and have found significant attention in cryptography. Traditional Shannon model of communication systems assumes the communication channel is perfectly known to the transmitter and the receiver. Arbitrary Varying Channels (AVCs) remove this assumption and have been used to model adversarially controlled channels. Transmission over these channels has been originally studied with the goal of recovering the sent message, and more recently with the goal of detecting tampering with the sent messages. In this paper we introduce non-malleability as the protection goal of message transmission over these channels, and study binary (discrete memoryless) AVCs where possible tampering is modelled by the set of channel states. Our main result is that non-malleability for these channels is achievable at a rate asymptotically approaching 1. We also consider the setting of an AVC with a special state s*, and the additional requirement that the message must be recoverable if s* is applied to all the transmitted bits. We give the outline of a message encoding scheme that in addition to non-malleability, can provide recovery for all s* channel.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims non-malleability over binary AVCs at rates approaching 1 by modeling tampering via channel states, which is a new goal, but the abstract gives no construction or proof to check it.

read the letter

The paper's core claim is that non-malleable coding works for binary discrete memoryless AVCs at rates asymptotically close to 1, where channel states represent the tampering. This extends non-malleable codes from fixed tampering functions to the AVC setting that had previously focused on recovery or detection. They also sketch an encoding approach for an extended model with a special state s* that adds recovery when that state hits every transmitted bit. The framing is straightforward and connects two areas without obvious circularity in the stated model. The binary restriction keeps the scope manageable for a first step. The main limitation is that the abstract states the achievability result but supplies no construction, rate calculation, or error analysis, so it is impossible to verify whether the rate-1 result holds without rate loss or gaps in the non-malleability guarantee. The full paper needs to show the explicit scheme and how it handles the state set to make the argument solid. This work is aimed at people in coding theory and information-theoretic security who track new protection goals for adversarial channels. A reader interested in the intersection would see value in the idea itself. It deserves peer review because the direction is specific and the claim is testable once the details are filled in, even if heavy revision on the proofs is likely.

Referee Report

1 major / 0 minor

Summary. The paper introduces non-malleability as a new protection goal for transmission over binary discrete memoryless arbitrary varying channels (AVCs), modeling tampering via channel states. The central claim is an achievability result: non-malleable codes exist at rates asymptotically approaching 1. An extended model with a special state s* is considered, along with an outline of an encoding scheme that additionally guarantees message recovery when s* is applied to all transmitted bits.

Significance. If the achievability result holds with a rigorous construction and analysis, the work would usefully connect non-malleable codes from cryptography with the AVC model from information theory, establishing a high-rate protection goal against adversarial channel control. The near-unit rate is notable and would strengthen the case for non-malleability as a practical objective in adversarially controlled settings.

major comments (1)

[Abstract / main result statement] The manuscript states the main achievability result (non-malleability at rates approaching 1) but supplies neither an explicit construction, proof outline, nor error analysis. This gap is load-bearing for the central claim, as the abstract and introduction alone do not allow verification that the math supports the stated rate.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and the recommendation for major revision. We address the single major comment below.

read point-by-point responses

Referee: [Abstract / main result statement] The manuscript states the main achievability result (non-malleability at rates approaching 1) but supplies neither an explicit construction, proof outline, nor error analysis. This gap is load-bearing for the central claim, as the abstract and introduction alone do not allow verification that the math supports the stated rate.

Authors: We agree that the abstract and introduction would benefit from a high-level proof sketch and error analysis to make the achievability result verifiable at a glance. The full manuscript contains the complete technical argument, but we will revise the introduction to include an outline of the random coding construction, the key properties of the AVC state selection, and the error-probability analysis establishing that the rate can approach 1 while preserving non-malleability. The extended model with state s* already contains an outline, which we will cross-reference for consistency. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper states an existence/achievability result for non-malleable coding over binary discrete memoryless AVCs (tampering modeled by channel states) at rates approaching 1, plus an outline for an extended s* recovery setting. No equations, parameter fits, or self-citations are visible in the provided abstract or description that reduce the central claim to a definition, a fitted input renamed as prediction, or a load-bearing self-citation chain. The derivation is presented as a construction whose details would be external to the inputs, making the result self-contained against the stated model.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based on abstract only; no free parameters, new entities, or ad-hoc axioms are visible. Relies on standard definitions of non-malleable codes and AVCs from prior literature.

axioms (1)

domain assumption Binary discrete memoryless AVC model with tampering given by channel states
Main result stated specifically for binary (discrete memoryless) AVCs.

pith-pipeline@v0.9.0 · 5783 in / 1144 out tokens · 27704 ms · 2026-05-25T15:09:38.482662+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · 2 internal anchors

[1]

Maji, Omkant P andey, and Manoj Prabhakaran

Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant P andey, and Manoj Prabhakaran. A rate-optimizing compiler for non-mal leable codes against bit-wise tampering and permutations. In Theory of Cryptography TCC 2015 , pages 375–397, 2015

work page 2015
[2]

David Blackwell, Leo Breiman, and A. J. Thomasian. The ca pacities of certain channel classes under random coding. Ann. Math. Statist. , 31(3):558–567, 1960

work page 1960
[3]

Non-malleable codes and extractors for small-depth circuits, and afﬁne functions

Eshan Chattopadhyay and Xin Li. Non-malleable codes and extractors for small-depth circuits, and afﬁne functions. In ACM SIGACT Sympo- sium on Theory of Computing, STOC , pages 1171–1184, 2017

work page 2017
[4]

Capacity of non- malleable codes

Mahdi Cheraghchi and V enkatesan Guruswami. Capacity of non- malleable codes. IEEE Trans. Information Theory , 62(3):1097–1118, 2016

work page 2016
[5]

Non-mallea ble coding against bit-wise and split-state tampering

Mahdi Cheraghchi and V enkatesan Guruswami. Non-mallea ble coding against bit-wise and split-state tampering. J. Cryptology, 30(1):191–241, 2017

work page 2017
[6]

Nonmalleable cryptog- raphy

Danny Dolev, Cynthia Dwork, and Moni Naor. Nonmalleable cryptog- raphy. In SIAM J. Comput. , volume 30, pages 391–437, 2000

work page 2000
[7]

Non- malleable codes

Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wic hs. Non- malleable codes. In Andrew Chi-Chih Yao, editor , ICS 2010, pages 434- 452, Tsinghua University, Beijing, China, January 5-7, 201 0. Tsinghua University Press

work page 2010
[8]

Codes which detect deception

Edgar N Gilbert, F Jessie MacWilliams, and Neil J A Sloane . Codes which detect deception. Bell System Technical Journal , 53(3):405–424, 1974

work page 1974
[9]

Authentication capacity of adversarial channels

Oliver Kosut and Jörg Kliewer. Authentication capacity of adversarial channels. In IEEE Information Theory W orkshop, ITW, pages 1–5, 2018

work page 2018
[10]

Leakage-Resilient Non-Malleable Secret Sharing in Non-compartmentalized Models

Fuchun Lin, Mahdi Cheraghchi, V enkatesan Guruswami, R eihaneh Safavi-Naini, and Huaxiong Wang. Leakage-resilient non- malleable secret sharing in non-compartmentalized models . https://arxiv.org/abs/1902.06195, 2018

work page internal anchor Pith review Pith/arXiv arXiv 1902
[11]

Non-Malleable Codes with Leakage and Applications to Secure Communication

Fuchun Lin, Reihaneh Safavi-Naini, Mahdi Cheraghchi, and Huaxiong Wang. Non-malleable codes with leakage and applications to secure communication. In https://arxiv.org/abs/1708.05462

work page internal anchor Pith review Pith/arXiv arXiv
[12]

Claude E. Shannon. A mathematical theory of communicat ion. Mobile Computing and Communications Review , 5(1):3–55, 2001

work page 2001

[1] [1]

Maji, Omkant P andey, and Manoj Prabhakaran

Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant P andey, and Manoj Prabhakaran. A rate-optimizing compiler for non-mal leable codes against bit-wise tampering and permutations. In Theory of Cryptography TCC 2015 , pages 375–397, 2015

work page 2015

[2] [2]

David Blackwell, Leo Breiman, and A. J. Thomasian. The ca pacities of certain channel classes under random coding. Ann. Math. Statist. , 31(3):558–567, 1960

work page 1960

[3] [3]

Non-malleable codes and extractors for small-depth circuits, and afﬁne functions

Eshan Chattopadhyay and Xin Li. Non-malleable codes and extractors for small-depth circuits, and afﬁne functions. In ACM SIGACT Sympo- sium on Theory of Computing, STOC , pages 1171–1184, 2017

work page 2017

[4] [4]

Capacity of non- malleable codes

Mahdi Cheraghchi and V enkatesan Guruswami. Capacity of non- malleable codes. IEEE Trans. Information Theory , 62(3):1097–1118, 2016

work page 2016

[5] [5]

Non-mallea ble coding against bit-wise and split-state tampering

Mahdi Cheraghchi and V enkatesan Guruswami. Non-mallea ble coding against bit-wise and split-state tampering. J. Cryptology, 30(1):191–241, 2017

work page 2017

[6] [6]

Nonmalleable cryptog- raphy

Danny Dolev, Cynthia Dwork, and Moni Naor. Nonmalleable cryptog- raphy. In SIAM J. Comput. , volume 30, pages 391–437, 2000

work page 2000

[7] [7]

Non- malleable codes

Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wic hs. Non- malleable codes. In Andrew Chi-Chih Yao, editor , ICS 2010, pages 434- 452, Tsinghua University, Beijing, China, January 5-7, 201 0. Tsinghua University Press

work page 2010

[8] [8]

Codes which detect deception

Edgar N Gilbert, F Jessie MacWilliams, and Neil J A Sloane . Codes which detect deception. Bell System Technical Journal , 53(3):405–424, 1974

work page 1974

[9] [9]

Authentication capacity of adversarial channels

Oliver Kosut and Jörg Kliewer. Authentication capacity of adversarial channels. In IEEE Information Theory W orkshop, ITW, pages 1–5, 2018

work page 2018

[10] [10]

Leakage-Resilient Non-Malleable Secret Sharing in Non-compartmentalized Models

Fuchun Lin, Mahdi Cheraghchi, V enkatesan Guruswami, R eihaneh Safavi-Naini, and Huaxiong Wang. Leakage-resilient non- malleable secret sharing in non-compartmentalized models . https://arxiv.org/abs/1902.06195, 2018

work page internal anchor Pith review Pith/arXiv arXiv 1902

[11] [11]

Non-Malleable Codes with Leakage and Applications to Secure Communication

Fuchun Lin, Reihaneh Safavi-Naini, Mahdi Cheraghchi, and Huaxiong Wang. Non-malleable codes with leakage and applications to secure communication. In https://arxiv.org/abs/1708.05462

work page internal anchor Pith review Pith/arXiv arXiv

[12] [12]

Claude E. Shannon. A mathematical theory of communicat ion. Mobile Computing and Communications Review , 5(1):3–55, 2001

work page 2001