Abstract
Non-malleable codes are a natural relaxation of error correcting/ detecting codes that have useful applications in the context of tamper resilient cryptography. Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a given message can only leave it unchanged or modify it to the encoding of a completely unrelated value. This paper introduces an extension of the standard non-malleability security notion - so-called continuous non-malleability - where we allow the adversary to tamper continuously with an encoding. This is in contrast to the standard notion of non-malleable codes where the adversary only is allowed to tamper a single time with an encoding. We show how to construct continuous non-malleable codes in the common split-state model where an encoding consist of two parts and the tampering can be arbitrary but has to be independent with both parts. Our main contributions are outlined below:
We propose a new uniqueness requirement of split-state codes which states that it is computationally hard to find two codewords X = (X 0,X 1) and X′ = (X 0,X 1′) such that both codewords are valid, but X 0 is the same in both X and X′. A simple attack shows that uniqueness is necessary to achieve continuous non-malleability in the split-state model. Moreover, we illustrate that none of the existing constructions satisfies our uniqueness property and hence is not secure in the continuous setting.
We construct a split-state code satisfying continuous non-malleability. Our scheme is based on the inner product function, collision-resistant hashing and non-interactive zero-knowledge proofs of knowledge and requires an untamperable common reference string.
We apply continuous non-malleable codes to protect arbitrary cryptographic primitives against tampering attacks. Previous applications of non-malleable codes in this setting required to perfectly erase the entire memory after each execution and required the adversary to be restricted in memory. We show that continuous non-malleable codes avoid these restrictions.
We propose a new uniqueness requirement of split-state codes which states that it is computationally hard to find two codewords X = (X 0,X 1) and X′ = (X 0,X 1′) such that both codewords are valid, but X 0 is the same in both X and X′. A simple attack shows that uniqueness is necessary to achieve continuous non-malleability in the split-state model. Moreover, we illustrate that none of the existing constructions satisfies our uniqueness property and hence is not secure in the continuous setting.
We construct a split-state code satisfying continuous non-malleability. Our scheme is based on the inner product function, collision-resistant hashing and non-interactive zero-knowledge proofs of knowledge and requires an untamperable common reference string.
We apply continuous non-malleable codes to protect arbitrary cryptographic primitives against tampering attacks. Previous applications of non-malleable codes in this setting required to perfectly erase the entire memory after each execution and required the adversary to be restricted in memory. We show that continuous non-malleable codes avoid these restrictions.
| Originalsprog | Engelsk |
|---|---|
| Titel | Theory of Cryptography : 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings |
| Redaktører | Yehuda Lindell |
| Antal sider | 24 |
| Forlag | Springer |
| Publikationsdato | 2014 |
| Sider | 465-488 |
| ISBN (Trykt) | 978-3-642-54241-1 |
| ISBN (Elektronisk) | 978-3-642-54242-8 |
| DOI | |
| Status | Udgivet - 2014 |
| Begivenhed | Theory of Cryptography Conference - San Diego, USA Varighed: 24 feb. 2014 → 26 feb. 2014 Konferencens nummer: 11 |
Konference
| Konference | Theory of Cryptography Conference |
|---|---|
| Nummer | 11 |
| Land/Område | USA |
| By | San Diego |
| Periode | 24/02/2014 → 26/02/2014 |
| Navn | Lecture Notes in Computer Science |
|---|---|
| Vol/bind | 8349 |
| ISSN | 0302-9743 |
Emneord
- non-malleable codes
- split-state
- tamper resilience