Abstract
This paper describes our recent results in information theoretically secure homomorphic encryption. The main question that stands in the basis of these works concerns the possibility of modifying encrypted data obliviously. This possibility is useful for various applications, e.g., multiparty computation, outsourcing of computations, and quantum key distribution (QKD).
The works presented here consider the scenario in which a user wishes to outsource the storage and computation of confidential data to an untrusted server. The first two works consider the approach of employing multiple servers and distributing secret shares of the data among the servers. The first work introduces a method for evaluating quadratic functions over a dynamic database, with no communication between the servers. The second work allows communication and considers a method for homomorphic evaluation of polynomials of arbitrary degree over non-zero secret shares in a single round of communication. We present protocols that enable the evaluation of multivariate polynomials over shares of a non-zero secret without requiring a secret sharing phase invoked in an offline preprocessing phase, and deal with possibly-zero secrets in several ways.
The third work reviewed here considers the approach of employing a single server. That work assumes that the user and server have quantum capabilities, and attempts to enable the homomorphic evaluation of encrypted classical data using quantum devices. The homomorphic encryption scheme presented in that work is used to construct a QKD scheme resilient against weak measurements. Weak measurement based attacks over known QKD schemes are also introduced in the third work, along with the innovative concept of securing entanglement.
We would like to thank the Lynne and William Frankel Center for Computer Science, the Rita Altura Trust Chair in Computer Science. This work was also partially supported by a grant from the Ministry of Science and Technology, Israel & the Japan Science and Technology Agency (JST), and the German Research Funding (DFG, Grant#8767581199).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It is not possible to copy general qubits due to the no-cloning theorem.
References
Acar, A., Aksu, H., Uluagac, A.S., Conti, M.: A survey on homomorphic encryption schemes: theory and implementation. ACM Comput. Surv. (CSUR) 51(4), 1–35 (2018)
Akavia, A., Gentry, C., Halevi, S., Leibovich, M.: Setup-free secure search on encrypted data: Faster and post-processing free. Technical report, Cryptology ePrint Archive Report (2018)
Ambainis, A., Mosca, M., Tapp, A., de Wolf, R.: Private quantum channels. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pp. 547–553 (2000)
Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34
Beaver, D.: Commodity-based cryptography. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 446–455. ACM (1997)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 1–10. ACM (1988)
Bennett, C. H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. IEEE, New York (2020)
Berend, D., Bitan, D., Dolev, S.: Polynomials whose secret shares multiplication preserves degree for 2-CNF circuits over a dynamic set of secrets. IACR Cryptol. ePrint Arch. (2019)
Bitan, D., Dolev, S.: One-round secure multiparty computation of arithmetic streams and functions. In: Dinur, I., Dolev, S., Lodha, S. (eds.) CSCML 2018. LNCS, vol. 10879, pp. 255–273. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94147-9_20
Bitan, D., Dolev, S.: Optimal-round preprocessing-mpc via polynomial representation and distributed random matrix (extended abstract). IACR Cryptol. ePrint Arch. (2019)
Bitan, D., Dolev, S.: Randomly choose an angle from immense number of angles to rotate qubits, compute and reverse. IACR Cryptol. ePrint Arch. (2019)
Blakley, G.R.: Safeguarding cryptographic keys. In: 1979 International Workshop on Managing Requirements Knowledge (MARK), pp. 313–318. IEEE (1979)
Brakerski, Z., Perlman, R.: Lattice-based fully dynamic multi-key FHE with short ciphertexts. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 190–213. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_8
Couteau, G.: A note on the communication complexity of multiparty computation in the correlated randomness model. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 473–503. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_17
Damgård, I., Larsen, K.G., Nielsen, J.B.: Communication lower bounds for statistically secure MPC, with or without preprocessing. IACR Cryptol. ePrint Arch. 2019, 220 (2019)
Damgård, I., Nielsen, J.B., Nielsen, M., Ranellucci, S.: The TinyTable protocol for 2-party secure computation, or: gate-scrambling revisited. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 167–187. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_6
Deng, F.-G., Long, G.L.: Secure direct communication with a quantum one-time pad. Phys. Rev. A 69(5), 052319 (2004)
Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439(1907), 553–558 (1992)
Dolev, S., Garay, J., Gilboa, N., Kolesnikov, V., Yuditsky, Y.: Towards efficient private distributed computation on unbounded input streams. J. Math. Cryptol. 9(2), 79–94 (2015)
Dolev, S., Garay, J.A., Gilboa, N., Kolesnikov, V., Kumaramangalam, M.V.: Perennial secure multi-party computation of universal turing machine. Theor. Comput. Sci. 769, 43–62 (2019)
Dolev, S., Gilboa, N., Li, X.: Accumulating automata and cascaded equations automata for communicationless information theoretically secure multi-party computation. In: Proceedings of the 3rd International Workshop on Security in Cloud Computing, pp. 21–29. ACM (2015)
Dolev, S., Li, Y.: Secret shared random access machine. In: Karydis, I., Sioutas, S., Triantafillou, P., Tsoumakos, D. (eds.) ALGOCLOUD 2015. LNCS, vol. 9511, pp. 19–34. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29919-8_2
Gentry, C.: A fully homomorphic encryption scheme. Stanford University (2009)
Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465–482. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_28
Gentry, C.B., Halevi, S., Smart, N.P.: Homomorphic evaluation including key switching, modulus switching, and dynamic noise management. US Patent 9,281,941 (2016)
Ghodosi, H., Pieprzyk, J., Steinfeld, R.: Multi-party computation with conversion of secret sharing. Des. Codes Cryptogr. 62(3), 259–272 (2012)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 218–229. ACM (1987)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM (1996)
Horodecki, R., Horodecki, P., Horodecki, M., Horodecki, K.: Quantum entanglement. Rev. Mod. Phys. 81(2), 865 (2009)
Ishai, Y., Kushilevitz, E., Meldgaard, S., Orlandi, C., Paskin-Cherniavsky, A.: On the power of correlated randomness in secure computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 600–620. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_34
Naehrig, M., Lauter, K., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, pp. 113–124 (2011)
Patra, A., Ravi, D.: On the exact round complexity of secure three-party computation. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 425–458. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_15
Rivest, R.: Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer. Unpublished manuscript (1999)
Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. Found. Secure Comput. 4(11), 169–180 (1978)
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings, pp. 124–134. IEEE (1994)
Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_25
van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_2
Xu, J., Wei, L., Zhang, Y., Wang, A., Zhou, F., Gao, C.-Z.: Dynamic fully homomorphic encryption-based merkle tree for lightweight streaming authenticated data structures. J. Netw. Comput. Appl. 107, 113–124 (2018)
Yao, A.C.-C.: Protocols for secure computations. In: FOCS, vol. 82, pp.160–164 (1982)
Yu, L., Pérez-Delgado, C.A., Fitzsimons, J.F.: Limitations on information-theoretically-secure quantum homomorphic encryption. Phys. Rev. A 90(5), 050303 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bitan, D., Dolev, S. (2020). Invited Paper: Homomorphic Operations Techniques Yielding Communication Efficiency. In: Devismes, S., Mittal, N. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2020. Lecture Notes in Computer Science(), vol 12514. Springer, Cham. https://doi.org/10.1007/978-3-030-64348-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-64348-5_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64347-8
Online ISBN: 978-3-030-64348-5
eBook Packages: Computer ScienceComputer Science (R0)