Continuously Non-malleable Codes in the Split-State Model
- PDF / 1,153,047 Bytes
- 44 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 175 Views
Continuously Non-malleable Codes in the Split-State Model Sebastian Faust Technical University of Darmstadt, Darmstadt, Germany
Pratyay Mukherjee Visa Research, Palo Alto, USA
Jesper Buus Nielsen Aarhus University, Aarhus, Denmark
Daniele Venturi Sapienza University of Rome, Rome, Italy [email protected] Communicated by Jonathan Katz. Received 13 March 2015 / Revised 3 July 2020
Abstract. Non-malleable codes (Dziembowski et al., ICS’10 and J. ACM’18) are a natural relaxation of error correcting/detecting codes with useful applications in cryptography. Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a message can only leave it unchanged or modify it to the encoding of an unrelated value. This paper introduces continuous non-malleability, a generalization of standard non-malleability where the adversary is allowed to tamper continuously with the same encoding. This is in contrast to the standard definition of non-malleable codes, where the adversary can only tamper a single time. The only restriction is that after the first invalid codeword is ever generated, a special self-destruct mechanism is triggered and no further tampering is allowed; this restriction can easily be shown to be necessary. We focus on the split-state model, where an encoding consists of two parts and the tampering functions can be arbitrary as long as they act independently on each part. Our main contributions are outlined below. • We show that continuous non-malleability in the split-state model is impossible without relying on computational assumptions. • We construct a computationally secure split-state code satisfying continuous non-malleability in the common reference string (CRS) model. Our scheme can be instantiated assuming the existence of collision-resistant hash functions and (doubly enhanced) trapdoor permutations, but we also give concrete instantiations based on standard number-theoretic assumptions. • We revisit the application of non-malleable codes to protecting arbitrary cryptographic primitives against related-key attacks. Previous applications of non-malleable codes in this setting required perfect erasures and the adversary to be restricted in memory. We show that continuously non-malleable codes allow to avoid these restrictions. © The Author(s) 2020
S. Faust et al. Keywords. Non-malleable codes, Tamper resistance, Split-state model.
1. Introduction Physical attacks targeting cryptographic implementations instead of breaking the blackbox security of the underlying algorithm are amongst the most severe threats for cryptographic systems. A particularly important attack on implementations is the so-called tampering attack, where the adversary changes the secret key to some related value and observes the effect of such changes at the output. Traditional black-box security notions do not incorporate adversaries that change the secret key to some related value; even worse, as shown in the celebrated work of Boneh et al. [22], already minor changes to the key suffice for complet
Data Loading...
