Study Identifies Vulnerabilities in Threshold Fully Homomorphic Encryption
/ 4 min read
Quick take - The paper “Insecurity of Threshold Fully Homomorphic Encryption based on Shamir Secret Sharing” by Jiseung Kim and Changmin Lee analyzes vulnerabilities in existing t-out-of-N threshold fully homomorphic encryption schemes, proposing theoretical adjustments and enhancements to address security flaws while noting practical implementation challenges with current encryption libraries.
Fast Facts
- The paper by Jiseung Kim and Changmin Lee identifies vulnerabilities in two t-out-of-N threshold fully homomorphic encryption (TFHE) schemes proposed by Boneh et al. at CRYPTO’18, challenging their claimed simulation security.
- The authors present polynomial time algorithms that allow adversaries to recover the secret key under specific conditions without violating original security proofs.
- They propose increasing security parameters from (N!)² to (N!)⁴, but note practical implementation challenges with existing libraries like OpenFHE and HElib, which fail to achieve simulation security.
- The paper discusses attacks that exploit noise bounds and multiple partial decryptions, revealing weaknesses in current FHE library operations and the potential for key recovery.
- Recommendations include using error-refreshing algorithms and reevaluating security proofs to address identified vulnerabilities and enhance the robustness of TFHE schemes.
Insecurity of Threshold Fully Homomorphic Encryption based on Shamir Secret Sharing
A recent paper titled “Insecurity of Threshold Fully Homomorphic Encryption based on Shamir Secret Sharing” has been published by Jiseung Kim from Jeonbuk National University and Changmin Lee from the Korea Institute for Advanced Study. The paper examines vulnerabilities in two t-out-of-N threshold fully homomorphic encryption (TFHE) schemes, which were initially proposed by Boneh et al. at CRYPTO’18.
Vulnerabilities in TFHE Schemes
Boneh et al. had previously asserted that their TFHE schemes maintained simulation security, a property that prevents information leakage during both partial and final decryption processes. However, Kim and Lee present two polynomial time algorithms that challenge this security. Their findings suggest that under specific constraints regarding the threshold (t) and the total number of participants (N), an adversary can recover the secret key without violating the conditions of the original security proofs.
In response to these vulnerabilities, the authors propose a theoretical adjustment involving increasing the parameters from (N!)² to (N!)⁴ to enhance security. Despite this proposed fix, practical challenges remain, as the authors highlight difficulties in implementing the modified TFHE scheme using existing fully homomorphic encryption libraries, including OpenFHE and HElib. The modified scheme does not achieve simulation security in practical implementations with current FHE libraries.
Recommendations for Improvement
To bolster resistance against attacks, the paper recommends using error-refreshing algorithms, such as bootstrapping or modulus switching for each addition operation. However, this approach may incur performance trade-offs. The paper provides a foundational overview of threshold cryptography, which involves partitioning a secret key into N shares, where at least t shares are necessary for decryption. This mechanism ensures that t-1 shares alone do not leak information.
The authors also explore threshold fully homomorphic encryption, which merges secure fully homomorphic encryption with secret-sharing methodologies to preserve simulation security during decryption. The paper discusses a basic attack that leverages constraints on noise bound BB, breaching simulation security and enabling adversaries to recover the secret key with high probability in polynomial time. An improved attack method is also detailed, exploiting multiple partial decryptions to further relax constraints and facilitate key recovery.
Experimental Results and Future Directions
In their analysis, the authors present heuristic evaluations yielding experimental results that illustrate the vulnerabilities of TFHE constructions, particularly when certain parameter choices are applied. They construct a practical attack targeting weaknesses in the addition operations of FHE libraries, indicating that current implementations may not uphold essential special decryption properties.
The authors recommend modifications to the parameters to ensure theoretical security and suggest enhancing existing libraries through robust error-refreshing algorithms. A reevaluation of security proofs is advised to address the identified flaws. This research highlights critical security concerns within TFHE schemes and paves the way for future improvements in the field of fully homomorphic encryption.
Original Source: Read the Full Article Here
