Aarhus University Seal / Aarhus Universitets segl

Mark Simkin

Continuously non-malleable codes with split-state refresh

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

Continuously non-malleable codes with split-state refresh. / Faonio, Antonio; Buus Nielsen, Jesper; Simkin, Mark; Venturi, Daniele.

In: Theoretical Computer Science, Vol. 759, 02.2019, p. 98-132.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

Faonio, A, Buus Nielsen, J, Simkin, M & Venturi, D 2019, 'Continuously non-malleable codes with split-state refresh', Theoretical Computer Science, vol. 759, pp. 98-132. https://doi.org/10.1016/j.tcs.2018.12.028

APA

CBE

MLA

Faonio, Antonio et al. "Continuously non-malleable codes with split-state refresh". Theoretical Computer Science. 2019, 759. 98-132. https://doi.org/10.1016/j.tcs.2018.12.028

Vancouver

Author

Faonio, Antonio ; Buus Nielsen, Jesper ; Simkin, Mark ; Venturi, Daniele. / Continuously non-malleable codes with split-state refresh. In: Theoretical Computer Science. 2019 ; Vol. 759. pp. 98-132.

Bibtex

@article{be852871a82e44d98f29c40f5fe69401,
title = "Continuously non-malleable codes with split-state refresh",
abstract = "Non-malleable codes for the split-state model allow to encode a message into two parts, such that arbitrary independent tampering on each part, and subsequent decoding of the corresponding modified codeword, yields either the same as the original message, or a completely unrelated value. Continuously non-malleable codes further allow to tolerate an unbounded (polynomial) number of tampering attempts, until a decoding error happens. The drawback is that, after an error happens, the system must self-destruct and stop working, otherwise generic attacks become possible. In this paper we propose a solution to this limitation, by leveraging a split-state refreshing procedure. Namely, whenever a decoding error happens, the two parts of an encoding can be locally refreshed (i.e., without any interaction), which allows to avoid the self-destruct mechanism in some applications. Additionally, the refreshing procedure can be exploited in order to obtain security against continual leakage attacks. We give an abstract framework for building refreshable continuously non-malleable codes in the common reference string model, and provide a concrete instantiation based on the external Diffie–Hellman assumption. Finally, we explore applications in which our notion turns out to be essential. The first application is a signature scheme tolerating an arbitrary polynomial number of split-state tampering attempts, without requiring a self-destruct capability, and in a model where refreshing of the memory happens only after an invalid output is produced. This circumvents an impossibility result from a recent work by Fujisaki and Xagawa (Asiacrypt 2016). The second application is a compiler for tamper-resilient read-only RAM programs. In comparison to other tamper-resilient RAM compilers, ours has several advantages, among which the fact that, in some cases, it does not rely on the self-destruct feature.",
keywords = "Non-malleable codes, Split-state model, Tamper-resilient cryptography",
author = "Antonio Faonio and {Buus Nielsen}, Jesper and Mark Simkin and Daniele Venturi",
year = "2019",
month = "2",
doi = "10.1016/j.tcs.2018.12.028",
language = "English",
volume = "759",
pages = "98--132",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier BV",

}

RIS

TY - JOUR

T1 - Continuously non-malleable codes with split-state refresh

AU - Faonio, Antonio

AU - Buus Nielsen, Jesper

AU - Simkin, Mark

AU - Venturi, Daniele

PY - 2019/2

Y1 - 2019/2

N2 - Non-malleable codes for the split-state model allow to encode a message into two parts, such that arbitrary independent tampering on each part, and subsequent decoding of the corresponding modified codeword, yields either the same as the original message, or a completely unrelated value. Continuously non-malleable codes further allow to tolerate an unbounded (polynomial) number of tampering attempts, until a decoding error happens. The drawback is that, after an error happens, the system must self-destruct and stop working, otherwise generic attacks become possible. In this paper we propose a solution to this limitation, by leveraging a split-state refreshing procedure. Namely, whenever a decoding error happens, the two parts of an encoding can be locally refreshed (i.e., without any interaction), which allows to avoid the self-destruct mechanism in some applications. Additionally, the refreshing procedure can be exploited in order to obtain security against continual leakage attacks. We give an abstract framework for building refreshable continuously non-malleable codes in the common reference string model, and provide a concrete instantiation based on the external Diffie–Hellman assumption. Finally, we explore applications in which our notion turns out to be essential. The first application is a signature scheme tolerating an arbitrary polynomial number of split-state tampering attempts, without requiring a self-destruct capability, and in a model where refreshing of the memory happens only after an invalid output is produced. This circumvents an impossibility result from a recent work by Fujisaki and Xagawa (Asiacrypt 2016). The second application is a compiler for tamper-resilient read-only RAM programs. In comparison to other tamper-resilient RAM compilers, ours has several advantages, among which the fact that, in some cases, it does not rely on the self-destruct feature.

AB - Non-malleable codes for the split-state model allow to encode a message into two parts, such that arbitrary independent tampering on each part, and subsequent decoding of the corresponding modified codeword, yields either the same as the original message, or a completely unrelated value. Continuously non-malleable codes further allow to tolerate an unbounded (polynomial) number of tampering attempts, until a decoding error happens. The drawback is that, after an error happens, the system must self-destruct and stop working, otherwise generic attacks become possible. In this paper we propose a solution to this limitation, by leveraging a split-state refreshing procedure. Namely, whenever a decoding error happens, the two parts of an encoding can be locally refreshed (i.e., without any interaction), which allows to avoid the self-destruct mechanism in some applications. Additionally, the refreshing procedure can be exploited in order to obtain security against continual leakage attacks. We give an abstract framework for building refreshable continuously non-malleable codes in the common reference string model, and provide a concrete instantiation based on the external Diffie–Hellman assumption. Finally, we explore applications in which our notion turns out to be essential. The first application is a signature scheme tolerating an arbitrary polynomial number of split-state tampering attempts, without requiring a self-destruct capability, and in a model where refreshing of the memory happens only after an invalid output is produced. This circumvents an impossibility result from a recent work by Fujisaki and Xagawa (Asiacrypt 2016). The second application is a compiler for tamper-resilient read-only RAM programs. In comparison to other tamper-resilient RAM compilers, ours has several advantages, among which the fact that, in some cases, it does not rely on the self-destruct feature.

KW - Non-malleable codes

KW - Split-state model

KW - Tamper-resilient cryptography

UR - http://www.scopus.com/inward/record.url?scp=85059680752&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.12.028

DO - 10.1016/j.tcs.2018.12.028

M3 - Journal article

AN - SCOPUS:85059680752

VL - 759

SP - 98

EP - 132

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -