1) We show that standard ID and signature schemes constructed from a large class of $\Sigma$-protocols (including the Okamoto scheme, for instance) are secure even if the adversary can arbitrarily tamper with the prover’s state a bounded number of times and obtain some bounded amount of leakage. Interestingly, for the Okamoto scheme we can allow also independent tampering with the public parameters.
2) 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 security 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 tamper-proof common reference string.
3) Finally, we explain how to boost bounded tampering and leakage resilience (as in 1. and 2. above) to continuous tampering and leakage resilience, in the so-called floppy model where each user has a personal hardware token (containing leak- and tamper-free information) which can be used to refresh the secret key.
We believe that bounded tampering is a meaningful and interesting alternative to avoid known impossibility results and can provide important insights into the security of existing standard cryptographic schemes.
Category / Keywords: public-key cryptography / related key security, bounded tamper resilience, public key encryption, identification schemes Original Publication (with minor differences): IACR-ASIACRYPT-2013 Date: received 23 Oct 2013, last revised 18 Feb 2015 Contact author: danone83 at gmail com Available format(s): PDF | BibTeX Citation Note: Fixed minor inconsistencies. Bibliography updated. Version: 20150218:113652 (All versions of this report) Short URL: ia.cr/2013/677 Discussion forum: Show discussion | Start new discussion