Paper 2022/1044

Oblivious Revocable Functions and Encrypted Indexing

Kevin Lewi, Facebook (United States)
Jon Millican, Facebook (United Kingdom)
Ananth Raghunathan, Facebook (United States)
Arnab Roy, Facebook (United States)

Many online applications, such as online file backup services, support the sharing of indexed data between a set of devices. These systems may offer client-side encryption of the data, so that the stored data is inaccessible to the online host. A potentially desirable goal in this setting would be to protect not just the contents of the backed-up files, but also their identifiers. However, as these identifiers are typically used for indexing, a deterministic consistent mapping across devices is necessary. Additionally, in a multi-device setting, it may be desirable to maintain an ability to revoke a device’s access—e.g. through rotating encryption keys for new data. We present a new primitive, called the Oblivious Revocable Function (ORF), which operates in the above setting and allows identifiers to be obliviously mapped to a consistent value across multiple devices, while enabling the server to permanently remove an individual device’s ability to map values. This permits a stronger threat model against metadata, in which metadata cannot be derived from identifiers by a revoked device colluding with the service provider, so long as the service provider was honest at the instant of revocation. We describe a simple Diffie- Hellman-based construction that achieves ORFs and provide a proof of security under the UC framework.

Available format(s)
Cryptographic protocols
Publication info
oblivious revocable functionpseudorandom functionindexing
Contact author(s)
klewi @ fb com
jmillican @ fb com
ananthr @ fb com
arnabr @ fb com
2022-08-17: approved
2022-08-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kevin Lewi and Jon Millican and Ananth Raghunathan and Arnab Roy},
      title = {Oblivious Revocable Functions and Encrypted Indexing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1044},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.