Elette Boyle
ABSTRACT
We continue the study of Homomorphic Secret Sharing (HSS), recently introduced by Boyle et al. (Crypto 2016, Eurocrypt 2017). A (2-party) HSS scheme splits an input x into shares (x0,x1) such that (1) each share computationally hides x, and (2) there exists an efficient homomorphic evaluation algorithm $\Eval$ such that for any function (or "program") from a given class it holds that Eval(x0,P)+Eval(x1,P)=P(x). Boyle et al. show how to construct an HSS scheme for branching programs, with an inverse polynomial error, using discrete-log type assumptions such as DDH.
We make two types of contributions.
Optimizations. We introduce new optimizations that speed up the previous optimized implementation of Boyle et al. by more than a factor of 30, significantly reduce the share size, and reduce the rate of leakage induced by selective failure.
Applications. Our optimizations are motivated by the observation that there are natural application scenarios in which HSS is useful even when applied to simple computations on short inputs. We demonstrate the practical feasibility of our HSS implementation in the context of such applications.
Supplemental Material
- Benny Applebaum. 2013. Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions. SIAM J. Comput., Vol. 42, 5 (2013), 2008--2037. Google Scholar
Digital Library
- Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, and Lior Zichron. 2017. Secure Arithmetic Computation with Constant Computational Overhead Crypto'17. 223--254.Google Scholar
- Benny Applebaum and Shachar Lovett 2016. Algebraic attacks against random local functions and their countermeasures STOC. 1087--1100.Google Scholar
- Donald Beaver. 1992. Foundations of Secure Interactive Computing. In CRYPTO'91, Vol. Vol. 576. 377--391. Google ScholarCross Ref
- Donald Beaver. 1995. Precomputing Oblivious Transfer. In CRYPTO'95, Vol. Vol. 963. 97--109. Google ScholarCross Ref
- Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In STOC. 1--10.Google Scholar
- Josh Cohen Benaloh. 1986. Cryptographic Capsules: A Disjunctive Primative for Interactive Protocols CRYPTO. 213--222.Google Scholar
- Josh Cohen Benaloh. 1986. Secret Sharing Homomorphisms: Keeping Shares of A Secret Sharing CRYPTO. 251--260.Google Scholar
- Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias 2011. Semi-homomorphic Encryption and Multiparty Computation EUROCRYPT 2011, Vol. Vol. 6632. 169--188.Google Scholar
- E. Boyle, N. Gilboa, and Y. Ishai 2015. Function Secret Sharing. In EUROCRYPT. 337--367. Google ScholarCross Ref
- Elette Boyle, Niv Gilboa, and Yuval Ishai 2016. Breaking the Circuit Size Barrier for Secure Computation Under DDH CRYPTO. 509--539. Full version: IACR Cryptology ePrint Archive 2016: 585 (2016).Google Scholar
- Elette Boyle, Niv Gilboa, and Yuval Ishai 2016. Function Secret Sharing: Improvements and Extensions ACM CCS. 1292--1303.Google Scholar
- Elette Boyle, Niv Gilboa, and Yuval Ishai 2017. Group-Based Secure Computation: Optimizing Rounds, Communication, and Computation Eurocrypt'17. 163--193.Google Scholar
- Zvika Brakerski and Guy N. Rothblum 2013. Obfuscating Conjunctions. In CRYPTO 2013, Part II, Vol. Vol. 8043. 416--434. Google ScholarCross Ref
- Zvika Brakerski and Vinod Vaikuntanathan 2014. Efficient Fully Homomorphic Encryption from (Standard) LWE. SIAM J. Comput. 43, 2 (2014), 831--871. Google ScholarCross Ref
- Ran Canetti. 1997. Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information CRYPTO'97, Vol. Vol. 1294. 455--469.Google Scholar
- David Chaum, Claude Crépeau, and Ivan Damgård. 1988. Multiparty Unconditionally Secure Protocols (Extended Abstract) STOC. 11--19.Google Scholar
- Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène 2016. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds Asiacrypt'16. 3--33.Google Scholar
- Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan 1995. Private information retrieval. In FOCS'95. 41--50. Google ScholarCross Ref
- Richard Cleve. 1991. Towards Optimal Simulations of Formulas by Bounded-Width Programs. Computational Complexity Vol. 1 (1991), 91--105. Google ScholarCross Ref
- Ivan Damgård, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci 2017. Gate-scrambling Revisited - or: The TinyTable protocol for 2-Party Secure Computation. Crypto'17 (2017).Google Scholar
- Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias 2012. Multiparty Computation from Somewhat Homomorphic Encryption CRYPTO 2012, Vol. Vol. 7417. 643--662.Google Scholar
- Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs 2016. Spooky Encryption and Its Applications. In CRYPTO. 93--122. Google ScholarDigital Library
- Léo Ducas and Daniele Micciancio 2015. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second EUROCRYPT. 617--640.Google Scholar
- Sanjam Garg, Craig Gentry, Shai Halevi, and Mariana Raykova 2014. Two-Round Secure MPC from Indistinguishability Obfuscation TCC. 74--94.Google Scholar
- Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. STOC. 169--178.Google Scholar
- Craig Gentry, Amit Sahai, and Brent Waters 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Crypto'13. 75--92.Google Scholar
- Satrajit Ghosh, Jesper Buus Nielsen, and Tobias Nilges 2017. Maliciously Secure Oblivious Linear Function Evaluation with Constant Overhead. IACR Cryptology ePrint Archive (2017), 409.Google Scholar
- Niv Gilboa. 1999. Two Party RSA Key Generation. In CRYPTO'99, Vol. Vol. 1666. 116--129. Google ScholarCross Ref
- Niv Gilboa and Yuval Ishai 2014. Distributed Point Functions and Their Applications EUROCRYPT 2014, Vol. Vol. 8441. 640--658.Google Scholar
- Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority STOC. 218--229.Google Scholar
- Shai Halevi and Victor Shoup 2015. Bootstrapping for HElib. In EUROCRYPT. 641--670. https://doi.org/10.1007/978-3-662-46800-5_25Google Scholar
- Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi, and Anat Paskin-Cherniavsky. 2013. On the Power of Correlated Randomness in Secure Computation TCC 2013, Vol. Vol. 7785. 600--620.Google Scholar
- Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai 2008. Cryptography with constant computational overhead. 40th ACM STOC, bibfieldeditorRichard E. Ladner and Cynthia Dwork (Eds.). ACM Press, 433--442.Google Scholar
- Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2009. Secure Arithmetic Computation with No Honest Majority TCC'09. 294--314.Google Scholar
- Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 830--842.Google ScholarDigital Library
- Vladimir Kolesnikov and Ranjit Kumaresan 2013. Improved OT Extension for Transferring Short Secrets CRYPTO 2013, Part II, Vol. Vol. 8043. 54--70.Google Scholar
- Eyal Kushilevitz and Rafail Ostrovsky 1997. Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval 38th FOCS. 364--373.Google Scholar
- Pratyay Mukherjee and Daniel Wichs 2016. Two Round Multiparty Computation via Multi-key FHE Proc. EUROCRYPT 2016. 735--763. https://doi.org/10.1007/978-3-662-49896-5_26Google ScholarCross Ref
- Moni Naor and Benny Pinkas 2006. Oblivious Polynomial Evaluation. SIAM J. Comput., Vol. 35, 5 (2006), 1254--1281. Google ScholarDigital Library
- Rafail Ostrovsky and William E. Skeith III. 2005. Private Searching on Streaming Data. In Proc. CRYPTO 2005. 223--240. Google ScholarDigital Library
- Ronald L. Rivest, Len Adleman, and Michael L. Dertouzos. 1978. On data banks and privacy homomorphisms. Foundations of secure computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977). Academic, New York, 169--179.Google Scholar
- SECG 2010. SEC 2: Recommended Elliptic Curve Domain Parameters, Version 2. http://www.secg.org. (2010).Google Scholar
- Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan 2010. Fully Homomorphic Encryption over the Integers. In Proc. EUROCRYPT 2010. 24--43. Google ScholarDigital Library
- Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets (Extended Abstract) FOCS. 162--167.Google Scholar
Index Terms
- Homomorphic Secret Sharing: Optimizations and Applications
Recommendations
Sum It Up: Verifiable Additive Homomorphic Secret Sharing
Information Security and Cryptology – ICISC 2019AbstractIn many situations, clients (e.g., researchers, companies, hospitals) need to outsource joint computations based on joint inputs to external cloud servers in order to provide useful results. Often clients want to guarantee that the results are ...
Chosen ciphertext secure keyed-homomorphic public-key cryptosystems
In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can "freely" perform the operation inevitably means ...
Comments