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.