TL;DR
This paper presents novel attacks against "lightweight" verifiable homomorphic encryption (VHE) schemes, demonstrating that current security parameters may be insufficient. The authors introduce efficient forgery attacks that exploit the underlying homomorphic encryption properties, undermining the verifiability guarantees of these schemes.
What Problem Does This Paper Address?
Verifiable Homomorphic Encryption (VHE) is a promising cryptographic technique that combines Homomorphic Encryption (HE) for privacy with Verifiable Computation (VC) for integrity. This allows clients to outsource computations to a server while ensuring both the confidentiality of their data and the correctness of the results. Recent "lightweight" VHE schemes, like those proposed by Chatel et al. (VERITAS) and Albrecht et al. (vADDG), aim to achieve VHE with lower computational overhead by cleverly embedding secret information within ciphertexts to verify homomorphic evaluations. However, the effectiveness and security of these lightweight approaches, particularly against sophisticated adversaries, remain an open question. This paper addresses this by performing a cryptanalysis of these schemes, specifically targeting their verifiability guarantees.
Methods
The paper introduces two main attack strategies:
- Forgery Attacks on vADDG and REP: The authors develop attacks that extract secret information (like index sets or characteristic functions) from encrypted inputs. This extracted information is then used to forge valid ciphertexts that pass the verification process without being detected. For vADDG, a pseudorandom characteristic function is employed to overcome limitations imposed by shallow bootstrapping depths. For REP, the attack focuses on identifying "computation slots" within encrypted data, enabling the construction of malicious outputs that appear legitimate.
- Forgery Attack on PE: The attack on Polynomial Encoding (PE) exploits its algebraic structure. Instead of directly recovering the secret value 'a', the authors devise a circuit that interpolates desired ciphertexts at specific points, effectively bypassing the need to know 'a' or its encryption. This attack leverages the Re-Quadratization (ReQ) protocol as a subroutine.
The methodology relies heavily on the homomorphic properties of the underlying HE schemes (like BFV and TFHE) to perform computations on encrypted data, allowing the adversary to recover secret information or construct forged ciphertexts without decrypting them.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Lightweight VHE is not inherently secure: The paper demonstrates that current "lightweight" VHE schemes, despite their clever design, are vulnerable to sophisticated cryptanalytic attacks.
- Exploiting HE properties for forgery: The core insight is that the homomorphic capabilities of HE can be turned against VHE schemes to forge results that appear valid.
- Shallow circuits can be powerful: The attack on vADDG shows that even with shallow circuit depths (a design goal of these schemes), forgery attacks are possible.
- Parameter choice is critical but not always sufficient: While adjusting parameters (like the number of verification values) can mitigate some attacks, it doesn't always provide a complete solution, especially against malicious adversaries.
- The importance of underlying HE primitives: The security of VHE schemes is intrinsically linked to the security and capabilities of the underlying HE schemes.
Key Results
- vADDG: The proposed 80-bit security parameters for vADDG provide at most 10 bits of concrete security against the presented attack.
- REP: The attack on REP achieves a probability 1 attack with linear time complexity when using fully homomorphic encryption.
- PE: A deterministic forgery attack on PE with computational cost O(log t) is presented.
- REPmsk: The "patch" using multiple secret keys for REP is shown to be vulnerable to a similar characteristic function attack, reducing its security to O(n⁻¹) against malicious adversaries.
- Practical Feasibility: The authors implemented attacks on REP and REPmsk, demonstrating their practical feasibility on a single-threaded environment.
Limitations and Future Work
- Bootstrapping Dependency: The implementation of attacks on REP and REPmsk was performed without BFV bootstrapping due to library limitations. The authors note that in a bootstrappable setting, these attacks would remain feasible. The attack on PE was not implemented due to the lack of bootstrapping functionality.
- Covert Adversary: While the attacks are effective against malicious adversaries, the paper notes that for REP, the attack is not feasible against a covert adversary.
- PE Attack Detection: The PE attack can be detected by counting the number of ReQ calls, which increases compared to the honest circuit.
- Future Work: The paper suggests further analysis of efficient pseudorandom characteristic function evaluation, especially for the case p=2. It also calls for more precise analysis of the "multiple secrets" approach for achieving malicious security. The authors also pose an open question about whether a method exists to successfully execute a forgery attack with overwhelming probability on REPmsk.
Summary updated