Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
Source abstract
Abstract
Threshold multi-party fully homomorphic encryption (TMFHE) schemes enable efficient computation to be performed on sensitive data while maintaining privacy. These schemes allow a subset of parties to perform threshold decryption of evaluation results via a distributed protocol without the need for a trusted dealer, and provide a degree of fault tolerance against a set of corrupted parties. However, existing TMFHE schemes can only provide correctness and security against honest-but-curious parties. We construct a compact TMFHE scheme based on the Learning with Errors (LWE) problem. The scheme applies Shamir secret sharing and share resharing to support an arbitrary t-out-of-N threshold access structure, and enables non-interactive reconstruction of secret key shares using additive shares derived from the current set of online participants. Furthermore, the scheme implements commitment and non-interactive zero-knowledge (NIZK) proof techniques to verify the TMFHE operations. Finally, our experiments demonstrate that the proposed scheme achieves active security against malicious adversaries. It overcomes the limitation of existing TMFHE schemes that can only guarantee correct computation under passive semi-honest adversaries.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Cryptography and Data Security · Cooperative Communication and Network Coding · Security in Wireless Sensor Networks
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Computer and Electronic Information, Guangxi University, Nanning 530004, China
Funding
Guangxi Key Research and Development Program Project
References (39)
Show source-provided references
1. Gentry, C. (June, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA.
2. Brakerski, Z., and Vaikuntanathan, V. (2011, January 22–25). Efficient Fully Homomorphic Encryption from (Standard) LWE. Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA.10.1109/FOCS.2011.12 ↗
3. Brakerski, Z., Gentry, C., and Vaikuntanathan, V. (2012, January 8–10). (Leveled) fully homomorphic encryption without bootstrapping. Proceedings of the 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012, Cambridge, MA, USA.10.1145/2090236.2090262 ↗
4. Gentry, C., Sahai, A., and Waters, B. (2013). Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2013, Proceedings, Part I, Springer.10.1007/978-3-642-40041-4_5 ↗
5. Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 3–7 December 2017, Proceedings, Part I, Springer International Publishing.10.1007/978-3-319-70694-8_15 ↗
6. López-Alt, A., Tromer, E., and Vaikuntanathan, V. (2012, January 19). On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA.10.1145/2213977.2214086 ↗
7. Clear, M., and McGoldrick, C. (2015). Multi-identity and multi-key leveled FHE from learning with errors. Advances in Cryptology–CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2015, Proceedings, Part II, Springer.10.1007/978-3-662-48000-7_31 ↗
8. Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., and Wichs, D. (2012). Multiparty computation with low communication, computation and interaction via threshold FHE. Advances in Cryptology–EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 15–19 April 2012, Proceedings, Springer.10.1007/978-3-642-29011-4_29 ↗
9. Mukherjee, P., and Wichs, D. (2016). Two round multiparty computation via multi-key FHE. Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 8–12 May 2016, Proceedings, Part II, Springer.10.1007/978-3-662-49896-5_26 ↗
10. Peikert, C., and Shiehian, S. (2016). Multi-key FHE from LWE, revisited. Theory of Cryptography—14th International Conference, TCC 2016-B, Beijing, China, 31 October–3 November 2016, Proceedings, Part II, Springer.10.1007/978-3-662-53644-5_9 ↗
11. Brakerski, Z., and Perlman, R. (2016). Lattice-based fully dynamic multi-key FHE with short ciphertexts. Advances in Cryptology—CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, 14–18 August 2016, Proceedings, Part I, Springer.10.1007/978-3-662-53018-4_8 ↗
12. Chen, L., Zhang, Z., and Wang, X. (2017). Batched multi-hop multi-key FHE from ring-LWE with compact ciphertext extension. Theory of Cryptography—15th International Conference, TCC 2017, Baltimore, MD, USA, 12–15 November 2017, Proceedings, Part II, Springer International Publishing.10.1007/978-3-319-70503-3_20 ↗
13. Chen, H., Chillotti, I., and Song, Y. (2019). Multi-key homomorphic encryption from TFHE. Advances in Cryptology–ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 8–12 December 2019, Proceedings, Part II, Springer International Publishing.10.1007/978-3-030-34621-8_16 ↗
14. Dynamic multi-key FHE in asymmetric key setting from LWE10.1109/TIFS.2021.3127023 ↗
15. Chen, H., Dai, W., Kim, M., and Song, Y. (2019, January 11–15). Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK.10.1145/3319535.3363207 ↗
16. Deriving genomic diagnoses without revealing patient genomes10.1126/science.aam9710 ↗
17. Truly privacy-preserving federated analytics for precision medicine with multiparty homomorphic encryption10.1038/s41467-021-25972-y ↗
18. Fiat, A., and Shamir, A. (1986, January 17–21). How to prove yourself: Practical solutions to identification and signature problems. Proceedings of the Conference on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, USA.
19. Boneh, D., Gennaro, R., Goldfeder, S., Jain, A., Kim, S., Rasmussen, P.M.R., and Sahai, A. (2018). Threshold cryptosystems from threshold fully homomorphic encryption. Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2018, Proceedings, Part I, Springer International Publishing.10.1007/978-3-319-96884-1_19 ↗
20. Chatel, S., Mouchet, C., Sahin, A.U., Pyrgelis, A., Troncoso, C., and Hubaux, J.P. (2023, January 26–30). Pelta-shielding multiparty-fhe against malicious adversaries. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, Copenhagen, Denmark.10.1145/3576915.3623139 ↗
21. An efficient threshold access-structure for rlwe-based multiparty homomorphic encryption10.1007/s00145-023-09452-8 ↗
22. Bendlin, R., and Damgård, I. (2010). Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems. Theory of Cryptography—7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, 9–11 February 2010, Proceedings, Springer.10.1007/978-3-642-11799-2_13 ↗
23. Regev, O. (2005, January 22–24). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.10.1145/1060590.1060603 ↗
24. Xie, X., Xue, R., and Zhang, R. (2011). Efficient threshold encryption from lossy trapdoor functions. Post-Quantum Cryptography: 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, 29 November–2 December 2011, Proceedings, Springer.
25. Round-optimal lattice-based threshold signatures, revisited
26. Crystals-dilithium: A lattice-based digital signature scheme10.46586/tches.v2018.i1.238-268 ↗
27. Multiparty homomorphic encryption from ring-learning-with-errors10.2478/popets-2021-0071 ↗
28. Efficient Commitments and Zero-Knowledge Protocols from Ring-SIS with Applications to Lattice-based Threshold Cryptosystems
29. Baum, C., Damgård, I., Lyubashevsky, V., Oechsner, S., and Peikert, C. (2018). More efficient commitments from structured lattice assumptions. Security and Cryptography for Networks—11th International Conference, SCN 2018, Amalfi, Italy, 5–7 September 2018, Proceedings, Springer International Publishing.10.1007/978-3-319-98113-0_20 ↗
30. Yang, R., Au, M.H., Zhang, Z., Xu, Q., and Yu, Z. (2019). Efficient lattice-based zero-knowledge arguments with standard soundness: Construction and applications. Advances in Cryptology—CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2019, Proceedings, Part I, Springer International Publishing.10.1007/978-3-030-26948-7_6 ↗
31. Actively secure setup for SPDZ10.1007/s00145-021-09416-w ↗
32. Gentry, C., Halevi, S., and Lyubashevsky, V. (2022). Practical non-interactive publicly verifiable secret sharing with thousands of parties. Advances in Cryptology—EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, 30 May–3 June 2022, Proceedings, Part I, Springer International Publishing.10.1007/978-3-031-06944-4_16 ↗
33. Viand, A., Knabenhans, C., and Hithnawi, A. (2023). Verifiable fully homomorphic encryption. arXiv.10.1145/3689945.3694806 ↗
34. Two-Round Threshold Lattice Signatures from Threshold Homomorphic Encryption
35. Aranha, D.F., Baum, C., Gjøsteen, K., Silde, T., and Stratmann, P. (2023, January 26–30). Verifiable mix-nets and distributed decryption for voting from lattice-based assumptions. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, Copenhagen, Denmark.10.1145/3576915.3616683 ↗
36. Micciancio, D., and Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. Advances in Cryptology—EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 15–19 April 2012, Proceedings, Springer.
37. How to share a secret10.1145/359168.359176 ↗
38. How to exchange (secret) keys10.1145/357360.357368 ↗
39. De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., and Sahai, A. (2001). Robust non-interactive zero knowledge. Advances in Cryptology—CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2001, Proceedings, Springer.10.1007/3-540-44647-8_33 ↗