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.