Experiments with the plaintext space in Gentry’s somewhat homomorphic scheme

Abstract

In this paper we propose an interesting improvement of the im-
plementation of the original Gentry-Halevi somewhat homomorphic scheme. We
suggest to choose a bigger plaintext space, by changing the underlying ideal from
$I = (2) to I = (p)$

for some bigger prime $p$.
Our analysis show that bigger plaintext space will improve the homomor-
phic computation of the somewhat homomorphic scheme while it only slightly
increases the complexity of the key generation procedure. The encryption and de-
cryption functions have the same complexity. We provide also some experimental
computations that support the analysis.