Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model. / Cramer, Ronald; Damgård, Ivan; Döttling, Nico; Giacomelli, Irene; Xing, Chaoping.

Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings. ed. / Junji Shikata. Vol. 10681 Springer VS, 2017. p. 1-25 (Lecture Notes in Computer Science, Vol. 10681).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Cramer, R, Damgård, I, Döttling, N, Giacomelli, I & Xing, C 2017, Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model. in J Shikata (ed.), Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings. vol. 10681, Springer VS, Lecture Notes in Computer Science, vol. 10681, pp. 1-25, 10th International Conference, ICITS 2017, Hong Kong, China, 29/11/2017. https://doi.org/10.1007/978-3-319-72089-0_1

APA

Cramer, R., Damgård, I., Döttling, N., Giacomelli, I., & Xing, C. (2017). Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model. In J. Shikata (Ed.), Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings (Vol. 10681, pp. 1-25). Springer VS. Lecture Notes in Computer Science, Vol.. 10681 https://doi.org/10.1007/978-3-319-72089-0_1

CBE

Cramer R, Damgård I, Döttling N, Giacomelli I, Xing C. 2017. Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model. Shikata J, editor. In Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings. Springer VS. pp. 1-25. (Lecture Notes in Computer Science, Vol. 10681). https://doi.org/10.1007/978-3-319-72089-0_1

MLA

Cramer, Ronald et al. "Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model". Shikata, Junji (ed.). Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings. Springer VS. (Lecture Notes in Computer Science, Vol. 10681). 2017, 1-25. https://doi.org/10.1007/978-3-319-72089-0_1

Vancouver

Cramer R, Damgård I, Döttling N, Giacomelli I, Xing C. Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model. In Shikata J, editor, Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings. Vol. 10681. Springer VS. 2017. p. 1-25. (Lecture Notes in Computer Science, Vol. 10681). https://doi.org/10.1007/978-3-319-72089-0_1

Author

Cramer, Ronald ; Damgård, Ivan ; Döttling, Nico ; Giacomelli, Irene ; Xing, Chaoping. / Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model. Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings. editor / Junji Shikata. Vol. 10681 Springer VS, 2017. pp. 1-25 (Lecture Notes in Computer Science, Vol. 10681).

Bibtex

@inproceedings{5c04160e77b246d49a947f59bb277594,
title = "Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model",
abstract = "Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m ′ (possibly ⊥) completely unrelated to m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established feasibility results of non-malleable codes against different families of tampering functions. However, for many interesting families the challenge of finding “good” non-malleable codes remains open. In particular, we would like to have explicit constructions of non-malleable codes with high-rate and efficient encoding/decoding algorithms (i.e. low computational complexity). In this work we present two explicit constructions: the first one is a natural generalization of the work of Dziembowski et al. and gives rise to the first constant-rate non-malleable code with linear-time complexity (in a model including bit-wise independent tampering). The second construction is inspired by the recent works about non-malleable codes of Agrawal et al. (TCC 2015) and of Cheraghchi and Guruswami (TCC 2014) and improves our previous result in the bit-wise independent tampering model: it builds the first non-malleable codes with linear-time complexity and optimal-rate (i.e. rate 1 - o(1)). ",
keywords = "Bit-wise independent tampering, Linear-time, Non-malleable codes, Secret-sharing",
author = "Ronald Cramer and Ivan Damg{\aa}rd and Nico D{\"o}ttling and Irene Giacomelli and Chaoping Xing",
year = "2017",
doi = "10.1007/978-3-319-72089-0_1",
language = "English",
isbn = "9783319720883",
volume = "10681",
series = "Lecture Notes in Computer Science",
publisher = "Springer VS",
pages = "1--25",
editor = "Junji Shikata",
booktitle = "Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings",
note = "null ; Conference date: 29-11-2017 Through 02-12-2017",
url = "http://www.inc.cuhk.edu.hk/icits2017/",

}

RIS

TY - GEN

T1 - Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model

AU - Cramer, Ronald

AU - Damgård, Ivan

AU - Döttling, Nico

AU - Giacomelli, Irene

AU - Xing, Chaoping

N1 - Conference code: 10

PY - 2017

Y1 - 2017

N2 - Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m ′ (possibly ⊥) completely unrelated to m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established feasibility results of non-malleable codes against different families of tampering functions. However, for many interesting families the challenge of finding “good” non-malleable codes remains open. In particular, we would like to have explicit constructions of non-malleable codes with high-rate and efficient encoding/decoding algorithms (i.e. low computational complexity). In this work we present two explicit constructions: the first one is a natural generalization of the work of Dziembowski et al. and gives rise to the first constant-rate non-malleable code with linear-time complexity (in a model including bit-wise independent tampering). The second construction is inspired by the recent works about non-malleable codes of Agrawal et al. (TCC 2015) and of Cheraghchi and Guruswami (TCC 2014) and improves our previous result in the bit-wise independent tampering model: it builds the first non-malleable codes with linear-time complexity and optimal-rate (i.e. rate 1 - o(1)).

AB - Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m ′ (possibly ⊥) completely unrelated to m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established feasibility results of non-malleable codes against different families of tampering functions. However, for many interesting families the challenge of finding “good” non-malleable codes remains open. In particular, we would like to have explicit constructions of non-malleable codes with high-rate and efficient encoding/decoding algorithms (i.e. low computational complexity). In this work we present two explicit constructions: the first one is a natural generalization of the work of Dziembowski et al. and gives rise to the first constant-rate non-malleable code with linear-time complexity (in a model including bit-wise independent tampering). The second construction is inspired by the recent works about non-malleable codes of Agrawal et al. (TCC 2015) and of Cheraghchi and Guruswami (TCC 2014) and improves our previous result in the bit-wise independent tampering model: it builds the first non-malleable codes with linear-time complexity and optimal-rate (i.e. rate 1 - o(1)).

KW - Bit-wise independent tampering

KW - Linear-time

KW - Non-malleable codes

KW - Secret-sharing

U2 - 10.1007/978-3-319-72089-0_1

DO - 10.1007/978-3-319-72089-0_1

M3 - Article in proceedings

SN - 9783319720883

VL - 10681

T3 - Lecture Notes in Computer Science

SP - 1

EP - 25

BT - Information Theoretic Security - 10th International Conference, ICITS 2017, Proceedings

A2 - Shikata, Junji

PB - Springer VS

Y2 - 29 November 2017 through 2 December 2017

ER -