Paper 2016/064

Unconditionally Secure Revocable Storage: Tight Bounds, Optimal Construction, and Robustness

Yohei Watanabe, Goichiro Hanaoka, and Junji Shikata


Data stored in cloud storage sometimes requires long-term security due to its sensitivity (e.g., genome data), and therefore, it also requires flexible access control for handling entities who can use the data. Broadcast encryption can partially provide such flexibility by specifying privileged receivers so that only they can decrypt a ciphertext. However, once privileged receivers are specified, they can be no longer dynamically added and/or removed. In this paper, we propose a new type of broadcast encryption which provides long-term security and appropriate access control, which we call unconditionally secure revocable-storage broadcast encryption (RS-BE). In RS-BE, privileged receivers of a ciphertext can be dynamically updated without revealing any information on the underlying plaintext. Specifically, we define a model and security of RS-BE, derive tight lower bounds on sizes of secret keys required for secure RS-BE, and propose a construction of RS-BE which meets all of these bounds. Our lower bounds can be applied to traditional broadcast encryption. Furthermore, to detect an improper update, we consider security against modification attacks to a ciphertext, and present a concrete construction secure against this type of attacks.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Broadcast encryptioninformation-theoretic securityrevocable storagesecret-key cryptographyunconditional security
Contact author(s)
watanabe @ uec ac jp
2016-04-25: revised
2016-01-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yohei Watanabe and Goichiro Hanaoka and Junji Shikata},
      title = {Unconditionally Secure Revocable Storage: Tight Bounds, Optimal Construction, and Robustness},
      howpublished = {Cryptology ePrint Archive, Paper 2016/064},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.