We show that any private-key encryption scheme that is weakly
homomorphic with respect to addition modulo 2, can be transformed
into a public-key encryption scheme. The homomorphic feature
referred to is a minimalistic one; that is, the length of a
homomorphically generated encryption should be independent of the
number of ciphertexts from which it was created. We do not require
anything else on the distribution of homomorphically generated
encryptions (in particular, we do not require them to be
distributed like real ciphertexts). Our resulting public-key
scheme is homomorphic in the following sense. If $i+1$ repeated
applications of homomorphic operations can be applied to the
private-key scheme, then $i$ repeated applications can be applied
to the public-key scheme.