  Fully Homomorphic Encryption (FHE) is seeing increasing real-world deployment
to protect data in use by allowing computation over encrypted data. However,
the same malleability that enables homomorphic computations also raises
integrity issues, which have so far been mostly overlooked. While FHEs lack of
integrity has obvious implications for correctness, it also has severe
implications for confidentiality: a malicious server can leverage the lack of
integrity to carry out interactive key-recovery attacks. As a result, virtually
all FHE schemes and applications assume an honest-but-curious server who does
not deviate from the protocol. In practice, however, this assumption is
insufficient for a wide range of deployment scenarios. While there has been
work that aims to address this gap, these have remained isolated efforts
considering only aspects of the overall problem and fail to fully address the
needs and characteristics of modern FHE schemes and applications. In this
paper, we analyze existing FHE integrity approaches, present attacks that
exploit gaps in prior work, and propose a new notion for maliciously-secure
verifiable FHE. We then instantiate this new notion with a range of techniques,
analyzing them and evaluating their performance in a range of different
settings. We highlight their potential but also show where future work on
tailored integrity solutions for FHE is still required.
