Cryptanalysis on Lightweight Verifiable Homomorphic Encryption

Verifiable Homomorphic Encryption (VHE) is a cryptographic technique that integrates Homomorphic Encryption (HE) with Verifiable Computation (VC). It serves as a crucial technology for ensuring both privacy and integrity in outsourced computation, where a client sends input ciphertexts ct and a function f to a server and verifies the correctness of the evaluation upon receiving the evaluation result f(ct) from the server. At CCS, Chatel et al. introduced two lightweight VHE schemes: Replication Encoding (REP) and Polynomial Encoding (PE). A similar approach to REP was used by Albrecht et al. in Eurocrypt to develop a Verifiable Oblivious PRF scheme (vADDG). A key approach in these schemes is to embed specific secret information within HE ciphertexts to verify homomorphic evaluations. This paper presents efficient attacks that exploit the homomorphic properties of encryption schemes. The one strategy is to retrieve the secret information in encrypted state from the input ciphertexts and then leverage it to modify the resulting ciphertext without being detected by the verification algorithm. The other is to exploit the secret embedding structure to modify the evaluation function f into f' which works well on input values for verification purposes. Our forgery attack on vADDG demonstrates that the proposed 80-bit security parameters in fact offer less than 10-bits of concrete security. Our attack on REP and PE achieves a probability 1 attack with linear time complexity when using fully homomorphic encryption.