A New ElGamal-Based Algebraic Homomorphism and Its Application

Sander and Tschudin proposed mobile code protection scheme - evaluation of encrypted functions implemented by homomorphisms based on exponentiation and Goldwasser Micali, but no homomorphisms enable to hide the skeleton and equal coefficient information of a polynomial. To solve the problems, an idea of approximate decryption and a new revised ElGamal are proposed in this paper. Three new public-key homomorphisms based on the new ElGamal (HNE) are defined. Security analyses show that HNE can resist known-plaintext attacks and chosen-ciphertext attacks. The problems of leaks about polynomial skeleton and equal coefficient are solved when HNE are used to encrypt polynomials. Then non-interactive evaluation of encrypted polynomials can be securely performed on a remote malicious host.