Paper 2019/912

I Want to Forget: Fine-Grained Encryption with Full Forward Secrecy in the Distributed Setting

David Derler and Sebastian Ramacher and Daniel Slamanig and Christoph Striecks

Abstract

Managing sensitive data in highly-distributed environments is gaining a lot of attention recently. Often, once data is presented to such environments, this data is persistent there. Being able to "forget" in such environments constitutes a very desired feature due to data security and privacy issues. In particular, applying the European General Data Protection Regulation (GDPR), the "Right to be Forgotten" essentially became a data owner right. In this work, we seek for cryptographic solutions that offer the possibility to willfully lose access to data in distributed environments (which can be seen equivalent to removing that data). We argue that simple encryption mechanisms do not suffice to cover all desired requirements and provide a solution that offers several strong security and privacy features. In particular, our solution achieves forward secrecy for all participants in the system (i.e., even when user keys leak), ensures strong privacy against public observers of the system (i.e., key anonymity against tracking), and enables fine-grained access control. Having those features in parallel was unknown from the cryptographic literature. We base our solution on a novel cryptographic primitive we dub Identity-Based Puncturable Encryption (IBPE) which significantly enhances previous ideas on Puncturable Encryption (PE) due to Green and Miers (IEEE S&P 2015) and Günther et al. (EUROCRYPT 2017). We argue that black-box constructions from Hierarchical Identity-Based Encryption (HIBE) do not seem to work, albeit we do know how to construct PE from HIBE. We further introduce an important feature being crucial in the setting of always-accessible and public data, namely that of key-anonymity for IBPE such that an IBPE ciphertext reveals nothing about the encryption key. We demonstrate the feasibility of our IBPE construction with a practical prototype implementation. Finally, we show that IBPE is a very versatile tool by using it to generically instantiate forward-secret IBE and forward-secret digital signatures, latter also being of importance in a distributed setting.