Paper 2023/561

vr${}^2$FHE- Securing FHE from Reaction-based Key Recovery Attacks

Abstract

Fully Homomorphic Encryption (FHE) inherently lacks data integrity mechanisms, allowing a malicious server to arbitrarily tamper with the data associated with FHE computations on its end. A series of works named reaction attacks further demonstrates that a malicious server can exploit this lack of integrity checks to carry out interactive full-key recovery attacks on state-of-the-art FHE schemes. In this paper, we propose an efficient solution to this problem by utilizing the concept of the Merkle tree. Our solution uses cryptographic hash functions to ensure the integrity of data involved in FHE computations. The efficiency of our solution comes from the lower sizes and ease of computations of the hash values, which subsequently leads to a reduction in both the network and computation overhead. Given that protecting the entire FHE circuit can lead to tremendous network overhead, we further perform scheme-specific optimizations by identifying a small portion of the FHE circuit, protecting which is sufficient to thwart these reaction-based attacks. Finally, we propose a framework that evaluates different FHE schemes based on the overhead that will be incurred when protecting these schemes through our solution. Our framework can be leveraged by application developers to choose an optimal FHE scheme in terms of both performance and overhead.