Perpetual Encryption

We consider the problem of building a private blockchain (BC) on top of a public one. This has the advantage that users of the private BC do not need to build expensive consensus protocol, while still maintaining privacy. When building this object, we realize the need for a novel encryption scheme we call perpetual encryption (PE), which is a new primitive of independent interest.
 
Very roughly, PE schemes support dynamically changing keys sk_1, sk_2, ... in a way that ciphertext c_n for epoch n:
(1) can be efficiently decrypted using any future key sk_n, sk_{n+1},...
(2) looks random even given all past keys sk_1,..,sk_{n-1}.
 
We also show how to build an efficient PE from any public-key encryption, hashing and other standard symmetric primitives.