Definition
Non-malleable code is a type of error‑correcting or error‑detecting code designed so that any tampering of the encoded data results either in the original message or in a completely unrelated (and typically invalid) output, preventing an adversary from meaningfully modifying the underlying plaintext while preserving the structure of the codeword.
Overview
Introduced within cryptographic research, non-malleable codes address scenarios where an attacker can observe or manipulate encoded data stored on insecure media (e.g., hardware devices, memory). Traditional error‑correcting codes can correct random errors but may still allow an adversary to induce predictable transformations of the decoded message. Non-malleable codes aim to guarantee non‑malleability: after any allowed tampering function, the decoded result is either the original message or a value that is independent of the original, according to a defined security notion. Formalizations typically involve a family of tampering functions (e.g., bit‑wise independent functions, split‑state functions) and a security game where the adversary must not be able to cause a related output with non‑negligible probability.
Applications include secure storage, tamper‑resistant hardware, software obfuscation, and leakage‑resilient cryptographic protocols. The concept builds upon earlier work on non‑malleable cryptographic primitives such as non‑malleable commitments and encryption.
Etymology/Origin
The term combines “non‑malleable,” a notion first defined in cryptography by Dolev, Dwork, and Naor (1991) to describe encryption schemes resistant to related‑message attacks, with “code,” referring to coding theory. The specific phrase “non‑malleable code” appeared in academic literature around 2008–2010, notably in works by Dziembowski, Pietrzak, and Wichs, who provided the first formal definitions and constructions for certain tampering families.
Characteristics
| Feature | Description |
|---|---|
| Tampering Model | Defined by a class of functions (e.g., bit‑wise independent, split‑state, affine) that an adversary may apply to a codeword. |
| Correctness | If no tampering occurs, decoding returns the original message with probability 1 (or with negligible error). |
| Non‑Malleability | For any tampering function f in the allowed class, the distribution of the decoded output after applying f is either the original message or a value that is statistically independent of it, except with negligible probability. |
| Efficiency | Constructions aim for polynomial‑time encoding and decoding, with reasonable overhead (often linear or polylogarithmic in message length). |
| Security Parameter | Non‑malleability is typically quantified with respect to a security parameter λ, where advantage of any polynomial‑time adversary is bounded by negl(λ). |
| Robustness | Some constructions provide additional guarantees such as detection of tampering (outputting a special ⊥ symbol) or resilience against multiple sequential tamperings. |
Related Topics
- Error‑Correcting Codes – Traditional codes that recover original data from random noise but without non‑malleability guarantees.
- Non‑Malleable Cryptography – Broader class of primitives (e.g., non‑malleable encryption, commitments) that resist related‑message attacks.
- Tamper‑Resistant Hardware – Physical devices employing non‑malleable codes to protect secret keys and firmware.
- Leakage‑Resilient Cryptography – Designs that remain secure even when some information about internal state leaks; non‑malleable codes can be used as building blocks.
- Split‑State Model – A specific tampering model where a codeword is divided into two halves, each tampered independently; many early constructions focus on this model.
References
- Dziembowski, S., Pietrzak, K., & Wichs, D. (2010). “Non‑Malleable Codes.” In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS).
- Dolev, D., Dwork, C., & Naor, M. (1991). “Non‑Malleable Cryptography.” SIAM Journal on Computing.
Note: The above summary reflects the consensus of peer‑reviewed literature up to the knowledge cutoff of September 2021. Subsequent developments may have extended definitions, constructions, or applications.