Algebraic Lower Bounds for Computing on Encrypted Data

Rafail Ostrovsky and William E. Skeith III

Abstract

In cryptography, there has been tremendous success in building primitives out of homomorphic semantically-secure encryption schemes, using homomorphic properties in a black-box way. A few notable examples of such primitives include items like private information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general methodology for determining what types of protocols can be implemented in this way and which cannot. This is accomplished by analyzing the computational power of various algebraic structures which are preserved by existing cryptosystems. More precisely, we demonstrate lower bounds for algebraically generating generalized characteristic vectors over certain algebraic structures, and subsequently we show how to directly apply this abstract algebraic results to put lower bounds on algebraic constructions of a number of cryptographic protocols, including PIR-writing and private keyword search protocols. We hope that this work will provide a simple litmus test'' of feasibility for use by other cryptographic researchers attempting to develop new protocols that require computation on encrypted data. Additionally, a precise mathematical language for reasoning about such problems is developed in this work, which may be of independent interest.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
homomorphic encryptioncomputing on encrypted dataprivate information retrievalkeyword searchPIR-writing
Contact author(s)
wskeith @ math ucla edu
History
Short URL
https://ia.cr/2007/064

CC BY

BibTeX

@misc{cryptoeprint:2007/064,
author = {Rafail Ostrovsky and William E.  Skeith III},
title = {Algebraic Lower Bounds for Computing on Encrypted Data},
howpublished = {Cryptology ePrint Archive, Paper 2007/064},
year = {2007},
note = {\url{https://eprint.iacr.org/2007/064}},
url = {https://eprint.iacr.org/2007/064}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.