Inception Makes Non-malleable Codes Stronger
Non-malleable codes (NMCs), introduced by Dziembowski et al. [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 ov
- PDF / 563,892 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 204 Views
National University of Singapore, Singapore, Singapore [email protected] 2 University of Warsaw, Warsaw, Poland 3 Aarhus University, Aarhus, Denmark
Abstract. Non-malleable codes (NMCs), introduced by Dziembowski et al. [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. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. A large body of the recent work has focused on various constructions of non-malleable codes in the split-state model. Many variants of NMCs have been introduced in the literature i.e. strong NMCs, super strong NMCs and continuous NMCs. Perhaps the most useful notion among these is that of continuous non-malleable codes, that allows for continuous tampering by the adversary. In this paper we give the first efficient, information-theoretic secure construction of continuous non-malleable codes in the split-state model. Enroute to our main result, we obtain constructions for almost all possible notions of non-malleable codes that have been considered in the split-state model, and for which such a construction is possible. Our result is obtained by a series of black-box reductions starting from the non-malleable codes from [ADL14]. One of the main technical ingredient of our result is a new concept that we call inception coding. We believe it may be of independent interest. Also our construction is used as a building block for non-persistent (resettable) continuous non-malleable codes in constant split-state model in [DNO16].
1
Introduction
Non-malleable Codes. Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs [DPW10], provide a useful message integrity This work is supported by: The Singapore Ministry of Education and the National Research Foundation, also through the Tier 3 Grant Random numbers from quantum processes MOE2012-T31-009; Polish National Science Centre (NCN) SONATA GRANT UMO-2014/13/D/ST6/ 03252; and European research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme (grant agreement No. 669255). c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 319–343, 2017. https://doi.org/10.1007/978-3-319-70503-3_10
320
D. Aggarwal et al.
guarantee in situations where traditional error-correction (and even errordetection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. Informally, given a tampering family F, an NMC (Enc, Dec) against F encodes a given message m into a codeword c ← Enc(m) in a way that, if the adversary modifies c to c = f (c) for some f ∈ F, then the message m = Dec(c ) is either the original message m, or a completely “unrelated value”. As has been shown by the recent progress [DPW1
Data Loading...
