Non-malleable code
A non-malleable code with respect to a family of tampering functions is a keyless randomized encoding such that decoding a codeword modified by any yields either the encoded message or a value distributed independently of it — DPW10.
Syntax
A coding scheme is a pair of algorithms , which need not be efficient, with respect to message space for some and codeword space :
- , a randomized algorithm taking a message and outputting a codeword ,
- , a deterministic algorithm taking a codeword and outputting a message or .
Every coding scheme on this page is perfectly correct, as defined under Correctness. Without correctness, a code whose always outputs is non-malleable with respect to every family, and with every code is.
A tampering family is a set of functions . The rate of is .
Properties
Correctness
A coding scheme is perfectly correct if for all , over the coins of . Every code on this page is perfectly correct, as the definition of a coding scheme requires — DPW10, Definition 3.1.
Non-malleability
For and a distribution on , the game compares the decoding of a tampered codeword of with a sample of in which is replaced by . The distribution depends on but not on ; the symbol accounts for tampering functions, such as the identity, that leave the message unchanged — DPW10.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{nm}}_{\Pi,f,D,\calA}(m)$}
\begin{algorithmic}
\State $b \getsr \bits$
\State $c \gets \Enc(m)$; $\tilde m_0 \gets \Dec(f(c))$
\State $\tilde m_1 \gets D$
\If{$\tilde m_1 = \mathsf{same}^*$}
\State $\tilde m_1 \gets m$
\EndIf
\State $b' \gets \calA(\tilde m_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
A coding scheme is -non-malleable with respect to if for every there is a distribution on such that for all and all ,
— DPW10. The adversary is unbounded, so the largest advantage over all is the statistical distance between the distributions of and .
As an object, a non-malleable code denotes this notion with the family and the error as parameters; results relating it to other objects are stated for a named family, such as split-state tampering. Without a named family the notion is trivial: for every code is -non-malleable, with the point mass on .
No coding scheme is non-malleable with respect to the family of all functions , and no coding scheme with efficient and is non-malleable with respect to the family of all efficiently computable functions: each family contains a function that decodes, replaces the message by a different one, and re-encodes — DPW10.
Variations
Split-state tampering
The codeword is a pair , and the split-state family contains every function for arbitrary functions and , which need not be efficient. A split-state non-malleable code is a sequence of codes, having codeword length and message length , such that is -non-malleable with respect to the split-state family on for a negligible function . As in the base syntax, and need not be efficient.
DKO13 construct an efficient one for one-bit messages from two-source extractors — DKO13; ADL14 construct an efficient one for multi-bit messages — ADL14; AO20 achieve constant rate — AO20. When the two halves have equal length, the best achievable rate, by codes that need not be efficient, is — CG14.
Bit-wise tampering
The bit-wise family contains every function that acts on each bit of the codeword independently, keeping it, flipping it, or setting it to or to . DPW10 construct an efficient code that is non-malleable with respect to this family — DPW10.
Other results
- For every family with , for a constant , the probabilistic method gives a code that is non-malleable with respect to and has rate close to ; the code need not be efficient — DPW10, as summarized by CG14.
- For every family with , where , a randomized construction gives, with high probability, codes non-malleable with respect to of rate arbitrarily close to ; for the family of functions that tamper only with the first bits of the codeword, is the best achievable rate — CG14.
- In the random-oracle model there are efficient codes non-malleable with respect to families in which every bit of the tampered codeword depends arbitrarily on any of the bits of the original codeword — DPW10.
- Storing the secret state of a device encoded with a code non-malleable with respect to protects any functionality against tampering of its memory by functions in — DPW10.