Scooby: improved multi-party homomorphic secret sharing based on FHE. (English) Zbl 1518.94111
Galdi, Clemente (ed.) et al., Security and cryptography for networks. 13th International conference, SCN 2022, Amalfi (SA), Italy, September 12–14, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13409, 540-563 (2022).
Summary: We present new constructions of multi-party homomorphic secret sharing (HSS) based on a new primitive that we call homomorphic encryption with decryption to shares (HEDS). Our first construction, which we call Scooby, is based on many popular fully homomorphic encryption (FHE) schemes with a linear decryption property. Scooby achieves an \(n\)-party HSS for general circuits with complexity \(O(|F| + \log n)\), as opposed to \(O(n^2 \cdot |F|)\) for the prior best construction based on multi-key FHE. Scooby can be based on (ring)-LWE with a super-polynomial modulus-to-noise ratio. In our second construction, Scrappy, assuming any generic FHE plus HSS for NC1-circuits, we obtain a HEDS scheme which does not require a super-polynomial modulus. While these schemes all require FHE, in another instantiation, Shaggy, we show how in some cases it is possible to obtain multi-party HSS without FHE, for a small number of parties and constant-degree polynomials. Finally, we show that our Scooby scheme can be adapted to use multi-key fully homomorphic encryption, giving more efficient spooky encryption and setup-free HSS. This latter scheme, Casper, if concretely instantiated with a B/FV-style multi-key FHE scheme, for functions \(F\) which do not require bootstrapping, gives an HSS complexity of \(O(n \cdot |F| + n^2 \cdot \log n)\).
For the entire collection see [Zbl 1515.94006].
For the entire collection see [Zbl 1515.94006].
References:
| [1] | Abram, D., Damgård, I., Orlandi, C., Scholl, P.: An algebraic framework for silent preprocessing with trustless setup and active security. Cryptology ePrint Archive, Report 2022/363 (2022). https://ia.cr/2022/363 · Zbl 1517.94045 |
| [2] | Beame, P., Cook, S., Hoover, H.: Log depth circuits for division and related problems. In: 25th Annual Symposium on Foundations of Computer Science, pp. 1-6 (1984). doi:10.1109/SFCS.1984.715894 · Zbl 0797.68074 |
| [3] | Boyle, E.; Couteau, G.; Gilboa, N.; Ishai, Y.; Kohl, L.; Scholl, P.; Boldyreva, A.; Micciancio, D., Efficient pseudorandom correlation generators: silent OT extension and more, Advances in Cryptology - CRYPTO 2019, 489-518 (2019), Cham: Springer, Cham · Zbl 1498.68048 · doi:10.1007/978-3-030-26954-8_16 |
| [4] | Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Correlated pseudorandom functions from variable-density LPN. In: 61st FOCS, pp. 1069-1080. IEEE Computer Society Press, November 2020. doi:10.1109/FOCS46700.2020.00103 |
| [5] | Boyle, E.; Gilboa, N.; Ishai, Y.; Oswald, E.; Fischlin, M., Function secret sharing, Advances in Cryptology - EUROCRYPT 2015, 337-367 (2015), Heidelberg: Springer, Heidelberg · Zbl 1371.94664 · doi:10.1007/978-3-662-46803-6_12 |
| [6] | Boyle, E.; Gilboa, N.; Ishai, Y.; Robshaw, M.; Katz, J., Breaking the circuit size barrier for secure computation under DDH, Advances in Cryptology - CRYPTO 2016, 509-539 (2016), Heidelberg: Springer, Heidelberg · Zbl 1384.94038 · doi:10.1007/978-3-662-53018-4_19 |
| [7] | Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1292-1303. ACM Press, October 2016. doi:10.1145/2976749.2978429 |
| [8] | Boyle, E., Gilboa, N., Ishai, Y., Lin, H., Tessaro, S.: Foundations of homomorphic secret sharing. In: Karlin, A.R. (ed.) ITCS 2018, vol. 94, pp. 21:1-21:21. LIPIcs, January 2018. doi:10.4230/LIPIcs.ITCS.2018.21 · Zbl 1462.94053 |
| [9] | Boyle, E.; Kohl, L.; Scholl, P.; Ishai, Y.; Rijmen, V., Homomorphic secret sharing from lattices without FHE, Advances in Cryptology - EUROCRYPT 2019, 3-33 (2019), Cham: Springer, Cham · Zbl 1428.94103 · doi:10.1007/978-3-030-17656-3_1 |
| [10] | Brakerski, Z.; Döttling, N.; Garg, S.; Malavolta, G.; Hofheinz, D.; Rosen, A., Leveraging linear decryption: rate-1 fully-homomorphic encryption and time-lock puzzles, Theory of Cryptography, 407-437 (2019), Cham: Springer, Cham · Zbl 1455.94132 · doi:10.1007/978-3-030-36033-7_16 |
| [11] | Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309-325. ACM, January 2012. doi:10.1145/2090236.2090262 · Zbl 1347.68120 |
| [12] | Brakerski, Z., Vaikuntanathan, V.: Lattice-based FHE as secure as PKE. In: Naor, M. (ed.) ITCS 2014, pp. 1-12. ACM, January 2014. doi:10.1145/2554797.2554799 · Zbl 1364.94528 |
| [13] | Chillotti, I.; Gama, N.; Georgieva, M.; Izabachène, M.; Cheon, JH; Takagi, T., Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds, Advances in Cryptology - ASIACRYPT 2016, 3-33 (2016), Heidelberg: Springer, Heidelberg · Zbl 1384.94044 · doi:10.1007/978-3-662-53887-6_1 |
| [14] | Chillotti, I.; Gama, N.; Georgieva, M.; Izabachène, M., TFHE: fast fully homomorphic encryption over the torus, J. Cryptol., 33, 1, 34-91 (2019) · Zbl 1455.94141 · doi:10.1007/s00145-019-09319-x |
| [15] | Clear, M.; McGoldrick, C.; Gennaro, R.; Robshaw, M., Multi-identity and multi-key leveled FHE from learning with errors, Advances in Cryptology - CRYPTO 2015, 630-656 (2015), Heidelberg: Springer, Heidelberg · Zbl 1351.94033 · doi:10.1007/978-3-662-48000-7_31 |
| [16] | Dodis, Y.; Halevi, S.; Rothblum, RD; Wichs, D.; Robshaw, M.; Katz, J., Spooky encryption and its applications, Advances in Cryptology - CRYPTO 2016, 93-122 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94045 · doi:10.1007/978-3-662-53015-3_4 |
| [17] | Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 523-535. ACM Press, October/November 2017. doi:10.1145/3133956.3133967 |
| [18] | Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012). https://eprint.iacr.org/2012/144 |
| [19] | Gentry, C.; Halevi, S.; Hofheinz, D.; Rosen, A., Compressible FHE with applications to PIR, Theory of Cryptography, 438-464 (2019), Cham: Springer, Cham · Zbl 1455.94158 · doi:10.1007/978-3-030-36033-7_17 |
| [20] | Gentry, C.; Sahai, A.; Waters, B.; Canetti, R.; Garay, JA, Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based, Advances in Cryptology - CRYPTO 2013, 75-92 (2013), Heidelberg: Springer, Heidelberg · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5 |
| [21] | Gilboa, N.; Ishai, Y.; Nguyen, PQ; Oswald, E., Distributed point functions and their applications, Advances in Cryptology - EUROCRYPT 2014, 640-658 (2014), Heidelberg: Springer, Heidelberg · Zbl 1328.68054 · doi:10.1007/978-3-642-55220-5_35 |
| [22] | Halevi, S.; Shoup, V., Bootstrapping for HElib, J. Cryptol., 34, 1, 1-44 (2021) · Zbl 1460.94046 · doi:10.1007/s00145-020-09368-7 |
| [23] | Mukherjee, P.; Wichs, D.; Fischlin, M.; Coron, J-S, Two round multiparty computation via multi-key FHE, Advances in Cryptology - EUROCRYPT 2016, 735-763 (2016), Heidelberg: Springer, Heidelberg · Zbl 1351.94060 · doi:10.1007/978-3-662-49896-5_26 |
| [24] | Naor, M.; Reingold, O., Number-theoretic constructions of efficient pseudo-random functions, J. ACM, 51, 2, 231-262 (2004) · Zbl 1248.94086 · doi:10.1145/972639.972643 |
| [25] | Orlandi, C.; Scholl, P.; Yakoubov, S.; Canteaut, A.; Standaert, F-X, The rise of Paillier: homomorphic secret sharing and public-key silent OT, Advances in Cryptology - EUROCRYPT 2021, 678-708 (2021), Cham: Springer, Cham · Zbl 1479.94339 · doi:10.1007/978-3-030-77870-5_24 |
| [26] | Rotaru, D.; Smart, NP; Tanguy, T.; Vercauteren, F.; Wood, T., Actively secure setup for SPDZ, J. Cryptol., 35, 1, 1-32 (2021) · Zbl 1481.94122 · doi:10.1007/s00145-021-09416-w |
| [27] | Roy, L.; Singh, J.; Malkin, T.; Peikert, C., Large message homomorphic secret sharing from DCR and applications, Advances in Cryptology - CRYPTO 2021, 687-717 (2021), Cham: Springer, Cham · Zbl 1487.94158 · doi:10.1007/978-3-030-84252-9_23 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
