Cryptanalysis on Lightweight Verifiable Homomorphic Encryption

Verifiable Homomorphic Encryption (VHE) integrates Homomorphic Encryption (HE) with Verifiable Computation (VC), aiming to provide privacy and integrity for outsourced computation. Chatel et al. introduced two VHE schemes, Replication Encoding (REP) and Polynomial Encoding (PE), and a similar approach to REP was used by Albrecht et al. to develop a Verifiable Oblivious PRF scheme (vADDG).

This paper gives efficient forgery attacks against the verifiability guarantees of these schemes. The first strategy targets REP and vADDG by extracting embedded secret information in encrypted form and using it to forge output ciphertexts that pass verification. The second targets PE by exploiting its secret embedding structure to forge outputs that remain valid on verification inputs while violating verifiability. The vADDG attack shows that the proposed 80-bit parameters provide at most 10 bits of concrete security, and the REP and PE attacks succeed with probability 1 in linear time when fully homomorphic encryption is used.