  Rekeying refers to an operation of replacing an existing key with a new key
for encryption. It renews security protection, so as to protect against key
compromise and enable dynamic access control in cryptographic storage. However,
it is non-trivial to realize efficient rekeying in encrypted deduplication
storage systems, which use deterministic content-derived encryption keys to
allow deduplication on ciphertexts. We design and implement REED, a
rekeying-aware encrypted deduplication storage system. REED builds on a
deterministic version of all-or-nothing transform (AONT), such that it enables
secure and lightweight rekeying, while preserving the deduplication capability.
We propose two REED encryption schemes that trade between performance and
security, and extend REED for dynamic access control. We implement a REED
prototype with various performance optimization techniques and demonstrate how
we can exploit similarity to mitigate key generation overhead. Our trace-driven
testbed evaluation shows that our REED prototype maintains high performance and
storage efficiency.
