Adriana López-Alt
ABSTRACT
We propose a new notion of secure multiparty computation aided by a computationally-powerful but untrusted "cloud" server. In this notion that we call on-the-fly multiparty computation (MPC), the cloud can non-interactively perform arbitrary, dynamically chosen computations on data belonging to arbitrary sets of users chosen on-the-fly. All user's input data and intermediate results are protected from snooping by the cloud as well as other users. This extends the standard notion of fully homomorphic encryption (FHE), where users can only enlist the cloud's help in evaluating functions on their own encrypted data.
In on-the-fly MPC, each user is involved only when initially uploading his (encrypted) data to the cloud, and in a final output decryption phase when outputs are revealed; the complexity of both is independent of the function being computed and the total number of users in the system. When users upload their data, they need not decide in advance which function will be computed, nor who they will compute with; they need only retroactively approve the eventually-chosen functions and on whose data the functions were evaluated.
This notion is qualitatively the best possible in minimizing interaction, since the users' interaction in the decryption stage is inevitable: we show that removing it would imply generic program obfuscation and is thus impossible.
Our contributions are two-fold:- We show how on-the-fly MPC can be achieved using a new type of encryption scheme that we call multikey FHE, which is capable of operating on inputs encrypted under multiple, unrelated keys. A ciphertext resulting from a multikey evaluation can be jointly decrypted using the secret keys of all the users involved in the computation. - We construct a multikey FHE scheme based on NTRU, a very efficient public-key encryption scheme proposed in the 1990s. It was previously not known how to make NTRU fully homomorphic even for a single party. We view the construction of (multikey) FHE from NTRU encryption as a main contribution of independent interest. Although the transformation to a fully homomorphic system deteriorates the efficiency of NTRU somewhat, we believe that this system is a leading candidate for a practical FHE scheme.
Supplemental Material
- M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In STOC, pages 284--293, 1997. Google Scholar
Digital Library
- B. Applebaum, D. Cash, C. Peikert, and A. Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In S. Halevi, editor, CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 595--618. Springer, 2009. Google ScholarDigital Library
- B. Applebaum, Y. Ishai, and E. Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis, editors, ICALP (1), volume 6198 of Lecture Notes in Computer Science, pages 152--163. Springer, 2010. Google ScholarDigital Library
- G. Asharov, A. Jain, A. López-Alt, E. Tromer, V. Vaikuntanathan, and D. Wichs. Multi-party computation with low communication, computation and interaction from threshold fhe. In EUROCRYPT, 2012. Google ScholarDigital Library
- M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In STOC, pages 1--10, 1988. Google ScholarDigital Library
- E. Ben-Sasson, A. Chiesa, D. Genkin, and E. Tromer. Fast reductions from rams to delegatable succinct constraint satisfaction problems. Cryptology ePrint Archive: Report 2012/071, 2012.Google Scholar
- N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In ITCS, 2012. Google ScholarDigital Library
- N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. Recursive composition and bootstrapping for snarks and proof-carrying data. Cryptology ePrint Archive: Report 2012/095, 2012.Google Scholar
- A. Blum, M. L. Furst, M. J. Kearns, and R. J. Lipton. Cryptographic primitives based on hard learning problems. In D. R. Stinson, editor, CRYPTO, volume 773 of Lecture Notes in Computer Science, pages 278--291. Springer, 1993. Google ScholarDigital Library
- Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully homomorphic encryption without bootstrapping. In ITCS, 2012. Google ScholarDigital Library
- Z. Brakerski and V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. In Ostrovsky FOCS2011, pages 97--106. Google ScholarDigital Library
- Z. Brakerski and V. Vaikuntanathan. Fully homomorphic encryption from ring-lwe and security for key dependent messages. In Rogaway CRYPTO2011, pages 505--524. Google ScholarDigital Library
- D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols (extended abstract). In STOC, pages 11--19, 1988. Google ScholarDigital Library
- K.-M. Chung, Y. T. Kalai, and S. P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In Rabin CRYPTO2010, pages 483--501. Google ScholarDigital Library
- R. Cramer, I. Damgård, and J. B. Nielsen. Multiparty computation from threshold homomorphic encryption. In EUROCRYPT, pages 280--299, 2001. Google ScholarDigital Library
- I. Damgård, Y. Ishai, and M. Krøigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In Gilbert ERUOCRYPT2010, pages 445--465. Google ScholarDigital Library
- I. Damgård, Y. Ishai, M. Krøigaard, J. B. Nielsen, and A. Smith. Scalable multiparty computation with nearly optimal work and resilience. In D. Wagner, editor, CRYPTO, volume 5157 of Lecture Notes in Computer Science, pages 241--261. Springer, 2008. Google ScholarDigital Library
- R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Rabin CRYPTO2010, pages 465--482. Google ScholarDigital Library
- C. Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. crypto.stanford.edu/craig. Google ScholarDigital Library
- C. Gentry. Fully homomorphic encryption using ideal lattices. In M. Mitzenmacher, editor, STOC, pages 169--178. ACM, 2009. Google ScholarDigital Library
- C. Gentry and S. Halevi. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In Ostrovsky FOCS2011, pages 107--109. Google ScholarDigital Library
- C. Gentry, S. Halevi, V. Lyubashevsky, C. Peikert, J. Silverman, and N. Smart. Personal communication, 2011.Google Scholar
- C. Gentry and D. Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In L. Fortnow and S. P. Vadhan, editors, STOC, pages 99--108. ACM, 2011. Google ScholarDigital Library
- H. Gilbert, editor. Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science. Springer, 2010. Google ScholarDigital Library
- O. Goldreich, S. Goldwasser, and S. Halevi. Public-key cryptosystems from lattice reduction problems. In B. S. K. Jr., editor, CRYPTO, volume 1294 of Lecture Notes in Computer Science, pages 112--131. Springer, 1997. Google ScholarDigital Library
- O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In STOC, pages 218--229, 1987. Google ScholarDigital Library
- S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. Delegating computation: interactive proofs for muggles. In C. Dwork, editor, STOC, pages 113--122. ACM, 2008. Google ScholarDigital Library
- S. Goldwasser, H. Lin, and A. Rubinstein. Delegation of computation without rejection problem from designated verifier cs-proofs. Cryptology ePrint Archive: Report 2011/456, 2011.Google Scholar
- S. Halevi, Y. Lindell, and B. Pinkas. Secure computation on the web: Computing without simultaneous interaction. In Rogaway CRYPTO2011, pages 132--150. Google ScholarDigital Library
- J. Hoffstein, J. Pipher, and J. H. Silverman. Ntru: A ring-based public key cryptosystem. In J. Buhler, editor, ANTS, volume 1423 of Lecture Notes in Computer Science, pages 267--288. Springer, 1998. Google ScholarDigital Library
- S. Kamara, P. Mohassel, and M. Raykova. Outsourcing multi-party computation. Cryptology ePrint Archive, Report 2011/272, 2011. http://eprint.iacr.org/.Google Scholar
- J. Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC, pages 723--732. ACM, 1992. Google ScholarDigital Library
- J. Kilian. Improved efficient arguments (preliminary version). In D. Coppersmith, editor, CRYPTO, volume 963 of Lecture Notes in Computer Science, pages 311--324. Springer, 1995. Google ScholarDigital Library
- V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors, ICALP (2), volume 4052 of Lecture Notes in Computer Science, pages 144--155. Springer, 2006. Google ScholarDigital Library
- V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In Gilbert EUROCRYPT2010, pages 1--23. Google ScholarDigital Library
- S. Micali. Cs proofs (extended abstracts). In FOCS, pages 436--453. IEEE, 1994. Google ScholarDigital Library
- D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 37(1):267--302, 2007. Google ScholarDigital Library
- M. Naor. On cryptographic assumptions and challenges. In D. Boneh, editor, CRYPTO, volume 2729 of Lecture Notes in Computer Science, pages 96--109. Springer, 2003.Google Scholar
- R. Ostrovsky, editor. IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22--25, 2011. IEEE, 2011.Google Scholar
- T. Rabin, editor. Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15--19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science. Springer, 2010. Google ScholarDigital Library
- O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In H. N. Gabow and R. Fagin, editors, STOC, pages 84--93. ACM, 2005. Google ScholarDigital Library
- O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. Google ScholarDigital Library
- T. Ristenpart, E. Tromer, H. Shacham, and S. Savage. Hey, you, get off of my cloud: exploring information leakage in third-party compute clouds. In ACM Conference on Computer and Communications Security, pages 199--212, 2009. Google ScholarDigital Library
- P. Rogaway, editor. Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14--18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science. Springer, 2011. Google ScholarDigital Library
- N. P. Smart and F. Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Public Key Cryptography, pages 420--443, 2010. Google ScholarDigital Library
- D. Stehlé and R. Steinfeld. Making ntru as secure as worst-case problems over ideal lattices. In K. G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 27--47. Springer, 2011. Google ScholarDigital Library
- P. Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In R. Canetti, editor, TCC, volume 4948 of Lecture Notes in Computer Science, pages 1--18. Springer, 2008. Google ScholarDigital Library
- M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. In Gilbert EUROCRYPT2010, pages 24--43. Google ScholarDigital Library
- A. C.-C. Yao. Protocols for secure computations (extended abstract). In FOCS, pages 160--164, 1982. Google ScholarDigital Library
Index Terms
- On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption
Recommendations
(Leveled) fully homomorphic encryption without bootstrapping
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science ConferenceWe present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic ...
Multikey Fully Homomorphic Encryption and Applications
We propose a new notion of secure multiparty computation aided by a computationally powerful but untrusted “cloud” server. In this notion, on-the-fly multiparty computation (MPC), the cloud can noninteractively perform arbitrary dynamically chosen ...
CCA-Secure Keyed-Fully Homomorphic Encryption
Proceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 9614To simultaneously achieve CCA security and homomorphic property for encryption, Emura et al. introduced a new cryptographic primitive named keyed-homomorphic encryption, in which homomorphic ciphertext manipulations can only be performed by someone ...
Comments