Back to Search
Start Over
Efficient Non-Malleable Codes and Key Derivation for Poly-Size Tampering Circuits.
- Source :
-
IEEE Transactions on Information Theory . Dec2016, Vol. 62 Issue 12, p7179-7194. 16p. - Publication Year :
- 2016
-
Abstract
- Non-malleable codes, defined by Dziembowski, Pietrzak, and Wichs (ICS ’10), provide roughly the following guarantee: if a codeword c encoding some message x is tampered to c' = f(c) such that c' \neq c , then the tampered message x' contained in c' reveals no information about x . The non-malleable codes have applications to immunizing cryptosystems against tampering attacks and related-key attacks. One cannot have an efficient non-malleable code that protects against all efficient tampering functions f . However, in this paper we show “the next best thing”: for any polynomial bound s of size | \mathcal F| \leq 2^s , there is an efficient non-malleable code that protects against all f \in \mathcal F . The rate of our codes, defined as the ratio of message to codeword size, approaches 1. Our results are information-theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the “common reference string” model. We also introduce a new notion of non-malleable key derivation, which uses randomness $x$ to derive a secret key $y = h(x)$ in such a way that, even if $x$ is tampered to a different value $x' = f(x)$ , the derived key $y' = h(x')$ does not reveal any information about $y$ . Our results for non-malleable key derivation are analogous to those for non-malleable codes. As a useful tool in our analysis, we rely on the notion of “leakage-resilient storage” of Davì, Dziembowski, and Venturi (SCN ’10), and, as a result of independent interest, we also significantly improve on the parameters of such schemes. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 62
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 119616349
- Full Text :
- https://doi.org/10.1109/TIT.2016.2613919