Reproduce “Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Yijia Chang, Songze Li
This work formalizes Approximate Secret Sharing (ApproxSS) as a new primitive and introduces ATASSES, an efficient Arbitrary-Threshold Fully Homomorphic Encryption (AThFHE) scheme. ATASSES significantly reduces computational and communication complexity compared to prior methods, achieving up to a 15.4x speedup for systems with 1000 parties.
Key insights
- The 'encrypted share' approach, where shares and local noises are homomorphically combined in ciphertext form, effectively mitigates the 'blown-up noise' problem associated with large Lagrange coefficients in Shamir Secret Sharing.
- Arbitrary-Threshold FHE can be generically built from ApproxSS, providing a modular framework for designing robust threshold decryption protocols.
- By sharing constant-sized encryption keys rather than data-size-dependent noisy shares, the complexity of AThFHE can be substantially reduced while maintaining security.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.