{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T12:36:29Z","timestamp":1778589389951,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose and implement a multiparty homomorphic encryption (MHE) scheme with a <jats:inline-formula><jats:alternatives><jats:tex-math>$$t$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>t<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-out-of-<jats:inline-formula><jats:alternatives><jats:tex-math>$$N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>N<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-threshold access-structure that is efficient and does not require a trusted dealer in the common random string model. We construct this scheme from the ring-learning-with-error assumptions and as an extension of the MHE scheme of Mouchet et al. (PETS 21). By means of a specially adapted <jats:italic>share re-sharing<\/jats:italic> procedure, this extension can be used to relax the <jats:inline-formula><jats:alternatives><jats:tex-math>$$N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>N<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-out-of-<jats:inline-formula><jats:alternatives><jats:tex-math>$$N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>N<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-threshold access-structure of the original scheme into a <jats:inline-formula><jats:alternatives><jats:tex-math>$$t$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>t<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-out-of-<jats:inline-formula><jats:alternatives><jats:tex-math>$$N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>N<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-threshold one. This procedure introduces only a single round of communication during the setup phase, after which any set of at least <jats:italic>t<\/jats:italic> parties can compute a <jats:italic>t<\/jats:italic>-out-of-<jats:italic>t<\/jats:italic> additive sharing of the secret-key with no interaction; this new sharing can be used directly in the scheme of Mouchet et al. We show that, by performing Shamir re-sharing over the MHE ciphertext-space ring with a carefully chosen exceptional set, this reconstruction procedure can be made secure and has negligible overhead. Moreover, it only requires the parties to store a constant-size state after its setup phase. Hence, in addition to fault tolerance, lowering the corruption threshold also yields considerable efficiency benefits, by enabling the distribution of batched secret-key operations among the online parties. We implemented and open-sourced our scheme in the Lattigo library.<\/jats:p>","DOI":"10.1007\/s00145-023-09452-8","type":"journal-article","created":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:03:26Z","timestamp":1679443406000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["An Efficient Threshold Access-Structure for RLWE-Based Multiparty Homomorphic Encryption"],"prefix":"10.1007","volume":"36","author":[{"given":"Christian","family":"Mouchet","sequence":"first","affiliation":[]},{"given":"Elliott","family":"Bertrand","sequence":"additional","affiliation":[]},{"given":"Jean-Pierre","family":"Hubaux","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,22]]},"reference":[{"key":"9452_CR1","doi-asserted-by":"crossref","unstructured":"M. Abspoel, R. Cramer, I. Damg\u00e5rd, D. Escudero, C. Yuan, Efficient information-theoretic secure multiparty computation over $${\\mathbb{Z}}\/p^{k}{\\mathbb{Z}}$$ via galois rings, in Theory of Cryptography Conference (Springer, 2019), pp. 471\u2013501","DOI":"10.1007\/978-3-030-36030-6_19"},{"key":"9452_CR2","unstructured":"M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai, V. Vaikuntanathan, Homomorphic encryption security standard, HomomorphicEncryption.org, Toronto, Canada, Tech. Rep. (2018)"},{"key":"9452_CR3","doi-asserted-by":"crossref","unstructured":"G. Asharov, A. Jain, A. L\u00f3pez-Alt, E. Tromer, V. Vaikuntanathan, D. Wichs, Multiparty computation with low communication, computation and interaction via threshold FHE, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2012), pp. 483\u2013501","DOI":"10.1007\/978-3-642-29011-4_29"},{"key":"9452_CR4","doi-asserted-by":"crossref","unstructured":"R. Bendlin, I. Damg\u00e5rd, Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems, in Theory of Cryptography Conference (Springer, 2010), pp. 201\u2013218","DOI":"10.1007\/978-3-642-11799-2_13"},{"key":"9452_CR5","doi-asserted-by":"crossref","unstructured":"D. Boneh, R. Gennaro, S. Goldfeder, A. Jain, S. Kim, P. M. Rasmussen, A. Sahai, Threshold cryptosystems from threshold fully homomorphic encryption, in Annual International Cryptology Conference (Springer, 2018), pp. 565\u2013596","DOI":"10.1007\/978-3-319-96884-1_19"},{"key":"9452_CR6","doi-asserted-by":"crossref","unstructured":"J.-P. Bossuat, C. Mouchet, J. Troncoso-Pastoriza, J.-P. Hubaux, Efficient bootstrapping for approximate homomorphic encryption with nonsparse keys, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2021), pp. 587\u2013617","DOI":"10.1007\/978-3-030-77870-5_21"},{"key":"9452_CR7","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, Fully homomorphic encryption without modulus switching from classical GapSVP, in Annual Cryptology Conference (Springer, 2012), pp. 868\u2013886","DOI":"10.1007\/978-3-642-32009-5_50"},{"issue":"3","key":"9452_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2633600","volume":"6","author":"Z Brakerski","year":"2014","unstructured":"Z. Brakerski, C. Gentry, V. Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory (TOCT) 6(3), 1\u201336 (2014)","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"key":"9452_CR9","doi-asserted-by":"crossref","unstructured":"J.H. Cheon, A. Kim, M. Kim, Y. Song, Homomorphic encryption for arithmetic of approximate numbers, in International Conference on the Theory and Application of Cryptology and Information Security (Springer, 2017), pp. 409\u2013437","DOI":"10.1007\/978-3-319-70694-8_15"},{"key":"9452_CR10","doi-asserted-by":"publisher","unstructured":"R. Cramer, I.B. Damg\u00e5rd, J.B. Nielsen, Secure multiparty computation and secret sharing, in Secure Multiparty Computation and Secret Sharing (Cambridge University Press, 2015), pp. 236\u2013298. https:\/\/doi.org\/10.1017\/CBO9781107337756.012","DOI":"10.1017\/CBO9781107337756.012"},{"key":"9452_CR11","first-page":"144","volume":"2012","author":"J Fan","year":"2012","unstructured":"J. Fan, F. Vercauteren, Somewhat practical fully homomorphic encryption. IACR Cryptol. ePrint Arch. 2012, 144 (2012)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"9452_CR12","unstructured":"Lattigo v3, Online: https:\/\/github.com\/tuneinsight\/lattigo, EPFLLDS, Tune Insight SA (2022)"},{"key":"9452_CR13","unstructured":"C. Mouchet, J.-P. Bossuat, J. Troncoso-Pastoriza, J. Hubaux, Lattigo: A multiparty homomorphic encryption library in Go, in WAHC 2020-8th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, vol. 15 (2020)"},{"issue":"4","key":"9452_CR14","doi-asserted-by":"publisher","first-page":"291","DOI":"10.2478\/popets-2021-0071","volume":"2021","author":"C Mouchet","year":"2021","unstructured":"C. Mouchet, J. Troncoso-Pastoriza, J.-P. Bossuat, J.-P. Hubaux, Multiparty homomorphic encryption from ring-learning-with-errors. Proc. Privacy Enhancing Technol. 2021(4), 291\u2013311 (2021)","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"9452_CR15","unstructured":"Palisade homomorphic encryption software library, Online: https:\/\/palisadecrypto.org\/."},{"key":"9452_CR16","doi-asserted-by":"crossref","unstructured":"S. Sav, A. Pyrgelis, J.R. Troncoso-Pastoriza, D. Froelicher, J.-P. Bossuat, J.S. Sousa, J.-P. Hubaux, Poseidon: Privacy-preserving federated neural network learning, in 28th Annual Network and Distributed System Security Symposium (2021)","DOI":"10.14722\/ndss.2021.24119"},{"issue":"11","key":"9452_CR17","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A Shamir","year":"1979","unstructured":"A. Shamir, How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Communications of the ACM"},{"key":"9452_CR18","unstructured":"A. Urban, M. Rambaud, Share and shrink: Ad-hoc threshold fhe with short ciphertexts and its application to almost-asynchronous mpc, Cryptology ePrint Archive, Paper 2022\/378, https:\/\/eprint.iacr.org\/2022\/378 (2022)"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09452-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09452-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09452-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,25]],"date-time":"2023-04-25T17:07:44Z","timestamp":1682442464000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09452-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,22]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["9452"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09452-8","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,22]]},"assertion":[{"value":"27 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"10"}}