ECCC-Report TR14-128https://eccc.weizmann.ac.il/report/2014/128Comments and Revisions published for TR14-128en-usFri, 18 Sep 2015 07:42:47 +0300
Revision 3
| Non-malleable Reductions and Applications |
Divesh Aggarwal,
Yevgeniy Dodis,
Tomasz Kazana ,
Maciej Obremski
https://eccc.weizmann.ac.il/report/2014/128#revision3Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely ``unrelated value''. Although such codes do not exist if the family of ``tampering functions'' $\cF$ allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families $\cF$.
The family which received the most attention~\cite{DPW10,LL12,DKO13,ADL14,CG14a,CG14b} is the family of tampering functions in the so called {\em split-state} model: here the message $x$ is encoded into two shares $L$ and $R$,
%of length $N$ each,
and the attacker is allowed to {\em arbitrarily} tamper with each $L$ and $R$ {\em individually}.
%
Despite this attention, the following problem remained open:
\begin{center}
{\em Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate}: $|L|=|R|=O(|x|)$.
\end{center}
In this work, we resolve this open problem. Our technique for getting our main result is of independent interest. We
\begin{itemize}
\item[(a)] develop a generalization of non-malleable codes, called {\em non-malleable reductions};
\item[(b)] show simple composition theorem for non-malleable reductions;
\item[(c)] build a variety of such reductions connecting various (independently interesting) tampering families $\cF$ to each other; and
\item[(d)] construct our final, constant-rate, non-malleable code in the split-state model by applying the composition theorem to a series of easy to understand reductions.
\end{itemize}
Fri, 18 Sep 2015 07:42:47 +0300https://eccc.weizmann.ac.il/report/2014/128#revision3
Revision 2
| Non-malleable Reductions and Applications |
Divesh Aggarwal,
Yevgeniy Dodis,
Tomasz Kazana ,
Maciej Obremski
https://eccc.weizmann.ac.il/report/2014/128#revision2Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs [DPW10], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely "unrelated value". Although such codes do not exist if the family of ``tampering functions'' F allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families F. The family which received the most attention [DPW10,LL12,DKO13,ADL14,CG14a,CG14b] is the family of tampering functions in the so called (2-part) *split-state* model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R *individually*. Despite this attention, the following problem remained open:
*** Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate: |L|=|R|=O(|x|). ***
In this work, we resolve this open problem. Our technique for getting our main result is of independent interest. We (a) develop a generalization of non-malleable codes, called *non-malleable reductions*; (b) show simple composition theorem for non-malleable reductions; (c) build a variety of such reductions connecting various (independently interesting) tampering families F to each other; (d) construct several new non-malleable codes in the split-state model by applying the composition theorem to a series of easy to understand reductions.
Most importantly, we show several "independence amplification" reductions, showing how to reduce split-state tampering of very few parts to an easier question of split-state tampering with a much larger number of parts. In particular, our final, constant-rate, non-malleable code composes one of these reductions with the very recent, "9-split-state" code of Chattopadhyay and Zuckerman [CZ14].Fri, 17 Oct 2014 13:43:47 +0300https://eccc.weizmann.ac.il/report/2014/128#revision2
Revision 1
| Non-malleable Reductions and Applications |
Divesh Aggarwal,
Yevgeniy Dodis,
Tomasz Kazana ,
Maciej Obremski
https://eccc.weizmann.ac.il/report/2014/128#revision1Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely ``unrelated value''. Although such codes do not exist if the family of ``tampering functions'' $\cF$ allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families $\cF$.
The family which received the most attention~\cite{DPW10,LL12,DKO13,ADL14,CG14a,CG14b} is the family of tampering functions in the so called {\em split-state} model: here the message $x$ is encoded into two shares $L$ and $R$,
%of length $N$ each,
and the attacker is allowed to {\em arbitrarily} tamper with each $L$ and $R$ {\em individually}.
%
Despite this attention, the following problem remained open:
\begin{center}
{\em Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate}: $|L|=|R|=O(|x|)$.
\end{center}
In this work, we resolve this open problem. Our technique for getting our main result is of independent interest. We
\begin{itemize}
\item[(a)] develop a generalization of non-malleable codes, called {\em non-malleable reductions};
\item[(b)] show simple composition theorem for non-malleable reductions;
\item[(c)] build a variety of such reductions connecting various (independently interesting) tampering families $\cF$ to each other; and
\item[(d)] construct our final, constant-rate, non-malleable code in the split-state model by applying the composition theorem to a series of easy to understand reductions.
\end{itemize}
Fri, 17 Oct 2014 11:31:41 +0300https://eccc.weizmann.ac.il/report/2014/128#revision1
Paper TR14-128
| Non-malleable Reductions and Applications |
Divesh Aggarwal,
Yevgeniy Dodis,
Tomasz Kazana ,
Maciej Obremski
https://eccc.weizmann.ac.il/report/2014/128Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely ``unrelated value''. Although such codes do not exist if the family of ``tampering functions'' $\cF$ allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families $\cF$.
The family which received the most attention~\cite{DPW10,LL12,DKO13,ADL14,CG14a,CG14b} is the family of tampering functions in the so called {\em split-state} model: here the message $x$ is encoded into two shares $L$ and $R$,
%of length $N$ each,
and the attacker is allowed to {\em arbitrarily} tamper with each $L$ and $R$ {\em individually}.
%
Despite this attention, the following problem remained open:
\begin{center}
{\em Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate}: $|L|=|R|=O(|x|)$.
\end{center}
In this work, we resolve this open problem. Our technique for getting our main result is of independent interest. We
\begin{itemize}
\item[(a)] develop a generalization of non-malleable codes, called {\em non-malleable reductions};
\item[(b)] show simple composition theorem for non-malleable reductions;
\item[(c)] build a variety of such reductions connecting various (independently interesting) tampering families $\cF$ to each other; and
\item[(d)] construct our final, constant-rate, non-malleable code in the split-state model by applying the composition theorem to a series of easy to understand reductions.
\end{itemize}
Fri, 17 Oct 2014 11:13:32 +0300https://eccc.weizmann.ac.il/report/2014/128