Paper 2019/438

Oblivious PRF on Committed Vector Inputs and Application to Deduplication of Encrypted Data

Jan Camenisch, Angelo De Caro, Esha Ghosh, and Alessandro Sorniotti


Ensuring secure deduplication of encrypted data is a very active topic of research because deduplication is effective at reducing storage costs. Schemes supporting deduplication of encrypted data that are not vulnerable to content guessing attacks (such as Message Locked Encryption) have been proposed recently [Bellare et al. 2013, Li et al. 2015]. However in all these schemes, there is a key derivation phase that solely depends on a short hash of the data and not the data itself. Therefore, a file specofic key can be obtained by anyone possessing the hash. Since hash values are usually not meant to be secret, a desired solution will be a more robust oblivious key generation protocol where file hashes need not be kept private. Motivated by this use-case, we propose a new primitive for oblivious pseudorandom function (OPRF) on committed vector inputs in the universal composable (UC) framework. We formalize this functionality as $\mathcal{F}_\mathsf{OOPRF}$, where $\mathsf{OOPRF}$ stands for Ownership-based Oblivious PRF. $\mathcal{F}_\mathsf{OOPRF}$ produces a unique random key on input a vector digest provided the client proves knowledge of a (parametrisable) number of random positions of the input vector. To construct an efficient $\mathsf{OOPRF}$ protocol, we carefully combine a hiding vector commitment scheme, a variant of the PRF scheme of Dodis- Yampolskiy [Dodis et al. 2005] and a homomorphic encryption scheme glued together with concrete, efficient instantiations of proofs of knowledge. To the best of our knowledge, our work shows for the first time how these primitives can be combined in a secure, efficient and useful way. We also propose a new vector commitment scheme with constant sized public parameters but $(\log n)$ size witnesses where n is the length of the committed vector. This can be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
public-key cryptographyapplicationspseudo-random functions
Contact author(s)
esha ghosh @ microsoft com
jan @ dfinity org
aso @ zurich ibm com
ADC @ zurich ibm com
2019-05-03: received
Short URL
Creative Commons Attribution


      author = {Jan Camenisch and Angelo De Caro and Esha Ghosh and Alessandro Sorniotti},
      title = {Oblivious PRF on Committed Vector Inputs and Application to Deduplication of Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2019/438},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.