Resettable Public-Key Encryption: How to Encrypt on a Virtual Machine


Scott Yilek


Typical security models used for proving security of deployed cryptographic primitives do not allow adversaries to rewind or reset honest parties to an earlier state. Thus, it is common to see cryptographic protocols rely on the assumption that fresh random numbers can be continually generated. In this paper, we argue that because of the growing popularity of virtual machines and, specifically, their state snapshot and revert features, the security of cryptographic protocols proven under these assumptions is called into question. We focus on public-key encryption security in a setting where resetting is possible and random numbers might be reused. We show that existing schemes and security models are insufficient in this setting. We then provide new formal security models and show that making a simple and efficient modification to any existing PKE scheme gives us security under our new models.


Scott Yilek.
Resettable Public-Key Encryption: How to Encrypt on a Virtual Machine
Topics in Cryptology - CT-RSA 2010. LNCS Vol. 5985, pp. 41-56, J. Pieprzyk ed., Springer, 2010.


Conference Version
Preliminary Version on ePrint


Paterson, Schuldt, and Sibborn, in their PKC 2014 paper (full version available here), point out a flaw in the proof of the second claim in the Security Definition section (that considering IND-RA security against 1 LR query is equivalent to q LR queries). Nevertheless, they found that the main scheme presented is still secure under the more general IND-RA definition with q LR queries. See their paper for more details.

See Also

RSA Conference 2010
CT-RSA 2010