Non-Malleable Codes Against Complexity-Bounded Tampering

14 concepts9 papers1 proposal

When we store sensitive data on physical hardware, adversaries can manipulate the underlying bits using fault injection, side-channel attacks, or localized radiation. Traditional error-correcting codes are designed to fix random or orthogonal noise, but they fail against malicious, targeted modifications. If an adversary knows a piece of data represents a financial transaction amount, they might alter the bits to predictably double that amount.

To prevent this, cryptographers use Non-Malleable Codes (NMCs). An NMC guarantees that if an adversary tampers with a codeword, the decoded result will either be the exact original message, or a completely unrelated message that reveals nothing about the original.

Historically, constructing NMCs required strict physical assumptions about where the adversary could tamper, such as the "split-state model," which assumes the codeword is divided into isolated compartments that the adversary cannot jointly analyze. A rapidly growing body of research has shifted this paradigm: instead of restricting the adversary's physical access boundaries, we can restrict their computational complexity. By assuming the tampering mechanism is globally applied but bounded in its circuit depth, time, or algebraic degree, we can build robust, setup-free protection for real-world hardware.


The Core Intuition: Hardness as a Shield

How do you prove that a code is non-malleable against a global tampering function? The core mechanism relies on a fundamental bridge between cryptography and circuit complexity: average-case hardness.

If a tampering function attempts to systematically alter a codeword to produce a related message, it must implicitly understand and manipulate the global structure of that codeword. If we design the code such that decoding requires evaluating a highly complex mathematical property, a simple or bounded tampering function will be unable to maintain the necessary correlations. Its structural changes will look like chaotic noise to the decoder, causing the system to either output an error ($\bot$) or decode to a completely random, unrelated message.

[Original Message] ---> [Encoder] ---> [Codeword]
                                           |
                                   (Global Tampering) 
                                   (e.g., Bounded Depth)
                                           v
[Random / Error]   <--- [Decoder] <--- [Mauled Codeword]

As shown by Dachman-Soled et al. in Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering, this framework allows us to build explicit NMCs against sophisticated, global threat models—such as constant-depth ($AC^0$) circuits, decision trees, and streaming space-bounded adversaries—by directly leveraging known hardness results from complexity theory.


Eliminating the Trusted Setup: The Plain Model

Early computational NMCs suffered from a major practical bottleneck: they required a trusted setup, such as a pre-shared secret key or a Common Reference String (CRS) generated by an un-tamperable third party. This requirement limits their applicability in decentralized or highly isolated hardware environments.

The ultimate goal is to achieve security in the plain model—meaning the code requires zero trusted infrastructure or prior coordination. Ostrovsky et al. emphasized this necessity in Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions, demonstrating that relaxing these setup requirements is vital for making non-malleable primitives practical.

To eliminate the trusted setup against global adversaries, researchers turned to derandomization assumptions. In Non-Malleable Codes Against Bounded Polynomial Time Tampering, Dachman-Soled et al. proved that plain-model security is achievable even when the adversary can run for arbitrary bounded polynomial time. Remarkably, the authors achieved a breakthrough where the codeword length remains constant even as the adversary's allowed computation time scales up.

The authors later extended this paradigm to parallelized attacks in Non-Malleable Codes for Bounded Polynomial Depth Tampering, proving that protection against broad, parallel circuit tampering can be achieved unconditionally or via standard complexity assumptions without any pre-shared secrets.


Scaling the Tampering Hierarchy

As this research direction matured, cryptographers systematically expanded the classes of mathematical functions they could defend against, moving from simple circuits to complex algebraic and non-deterministic models.

Bounded-Depth and Bounded Fan-In Circuits

For hardware attacks that operate via highly parallel but shallow logic gates, Ball et al. constructed efficient, unconditionally secure NMCs in Non-malleable Codes for Bounded Depth, Bounded Fan-In Circuits. For constant-depth circuits ($NC^c$), the authors achieved a constant rate, meaning the storage overhead of the code does not grow exponentially with the message length.

Beyond Linearity: Higher-Degree Polynomials

Traditional algebraic non-malleable codes were restricted to affine (degree-1) tampering functions. Moving beyond linear transformations is notoriously difficult because non-linear functions destroy the linear independence properties that standard security proofs rely on.

To bypass this limitation, Ball et al. developed novel seedless non-malleable extractors in Non-Malleability against Polynomial Tampering. These extractors can ingest a tampered distribution and smooth out any non-linear correlations introduced by arbitrary-degree polynomial functions, proving that linearity is not a fundamental barrier to security.

General Polynomial-Size Circuits

The pinnacle of this hierarchy is defending against any arbitrary polynomial-size circuit ($P/poly$). In (Nondeterministic) Hardness vs. Non-malleability, Ball et al. established the first explicit constructions resilient to full polynomial-size circuit tampering. They achieved this by introducing a novel hardness assumption concerning non-deterministic circuits. This assumption is entirely orthogonal to standard cryptographic primitives, meaning these codes can remain secure even in a world where traditional one-way functions do not exist.


Efficiency and Mathematical Certainty

A key question when designing these codes is whether the protective properties require a disproportionate increase in resource usage as the adversary becomes more powerful.

Fortunately, complexity-bounded NMCs scale remarkably well. In Non-Malleable Codes for Small-Depth Circuits, Dachman-Soled et al. demonstrated that NMCs can maintain efficient scaling between message length and codeword size while providing unconditional security guarantees. This means the protection against small-depth circuit tampering remains mathematically certain, completely independent of future algorithmic breakthroughs or whether $P = NP$.

However, this unconditional security depends heavily on how the adversary interacts with the blocks of data. If the adversary can dynamically alter data in a block-by-block manner where later modifications depend on previous blocks, information-theoretic security becomes impossible. As Chandran et al. demonstrated in Block-Wise Non-Malleable Codes, defending against such block-wise dependencies requires shifting back to computational assumptions, such as sub-exponentially hard one-way permutations.

By framing the adversary's capabilities in terms of computational and circuit complexity rather than physical isolation, this line of research has made non-malleable codes both highly practical and resilient to the global, complex tampering strategies encountered in real-world hardware security.

Key Foundational Work

Non-Malleable Codes for Bounded Depth, Bounded Fan-in Circuits (2016) — contributed 4 concept elements to this direction.
Block-Wise Non-Malleable Codes (2016) — contributed 1 concept elements to this direction.
Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_plain_model_non_malleable_codes_de589d33,
  title = {plain-model non-malleable codes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/plain-model-non-malleable-codes/rdr_de589d33642042c88fb5e870ece70508},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_plain_model_non_malleable_codes_de589d33_v1,
  title = {plain-model non-malleable codes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/plain-model-non-malleable-codes/rdr_de589d33642042c88fb5e870ece70508/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake