Tamper Resilient Cryptography Without Self-Destruct.
Ivan Damgård, Sebastian Faust, Pratyay Mukherjee, Daniele Venturi · 2013
We initiate a general study of schemes resilient to both tampering an d leakage attacks. Tamper- ing attacks are powerful cryptanalytic attacks where an advers ary can change the secret state and observes the effect of such changes at the output. Our cont ributions are outlined below: 1. We propose a general construction showing that any cryptographic primitive where the secret key can be chosen as a uniformly random string can be made s ecure against bounded tampering and leakage. This holds in a restricted model where the ta mpering functions must be chosen from a set of bounded size after the public paramet ers have been sampled. Our result covers pseudorandom functions, and many encryption and signature schemes. 2. We show that standard ID and signature schemes constructed from a large class of Σ- protocols (including the Okamoto scheme, for instance) are secur e even if the adversary can arbitrarily tamper with the prover’s state a bounded number of times and/or obtain some bounded amount of leakage. Interestingly, for the Okamoto scheme we can allow also independent tampering with the public parameters. 3. We show a bounded tamper and leakage resilient CCA secure public key cryptosystem based on the DDH assumption. We first define a weaker CPA-like secu rity notion that we can instantiate based on DDH, and then we give a general compiler that yields CCA- security with tamper and leakage resilience. This requires a public tam per-proof common reference string. 4. Finally, we explain how to boost bounded tampering and leakage res ilience (as in 2. and 3. above) to continuous tampering and leakage resilience, in the so-called floppy model where each user has a personal floppy (containing leak- and tamper-fre e information) which can be used to refresh the secret key (note that if the key is not upda ted, continuous tamper resilience is known to be impossible). For the case of ID schemes, we a lso show that if the underlying protocol is secure in the bounded retrieval model, then our compiler remains secure, even if the adversary can tamper with the computation performed by the device. In some earlier work, the implementation of the tamper resilient primit ive was assumed to be aware of the possibility of tampering, in that it would switch to a spe cial mode and, e.g., self-destruct if tampering was detected. None of our results req uire this assumption