Abstract
We show that public-key bit encryption schemes which support weak (i.e., compact) homomorphic evaluation of any sufficiently “sensitive” collection of functions cannot be proved message indistinguishable beyond AM ∩ coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity. Examples of sensitive collections include parities, majorities, and the class consisting of all AND and OR functions.
We also give a method for converting a strong (i.e., distribution-preserving) homomorphic evaluator for essentially any boolean function (except the trivial ones, the NOT function, and the AND and OR functions) into a rerandomization algorithm: This is a procedure that converts a ciphertext into another ciphertext which is statistically close to being independent and identically distributed with the original one. Our transformation preserves negligible statistical error.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: Proceedings of the 38th ACM Symposium on Theory of Computing (2006)
Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the 28th ACM Symposium on Theory of Computing, STOC 1996, pp. 99–108. ACM, New York (1996)
Bhatnagar, N., Bogdanov, A., Mossel, E.: The computational complexity of estimating MCMC convergence time. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol. 6845, pp. 424–435. Springer, Heidelberg (2011)
Brassard, G.: Relativized cryptography. In: Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pp. 383–391 (1979)
Bogdanov, A., Trevisan, L.: On wost-case to average-case reductions for NP problems. SIAM J. Comp. 36(4) (2006)
Brakerski, Z., Vaikuntanathan, V.: Efficient Fully Homomorphic Encryption from (Standard) LWE. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (2011)
Even, S., Yacobi, Y.: Cryptography and NP-completeness. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 195–207. Springer, Heidelberg (1980)
Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM Journal on Computing 22, 994–1005 (1993)
El Gamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory 31(4), 469–472 (1985)
Gentry, C.: Fully Homomorphic Encryption Using Ideal Lattices. In: STOC, pp. 169–178 (2009)
Goldreich, O., Goldwasser, S.: On the possibility of basing cryptography on the assumption that P ≠ NP (1998) (unpublished manuscript)
Goldreich, O.: Candidate one-way functions based on expander graphs. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 7(90) (2000)
Haitner, I., Mahmoody, M., Xiao, D.: A new sampling protocol and applications to basing cryptographic primitives on NP. In: Proceeedings of 25th IEEE Conference on Computational Complexity (CCC), pp. 76–87 (2010)
Mahmoody, M., Xiao, D.: On the power of randomized reductions and the checkability of sat. In: Proceeedings of 25th IEEE Conference on Computational Complexity (CCC), pp. 64–75 (2010)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of the 41th ACM Symposium on Theory of Computing, pp. 333–342. ACM, New York (2009)
Pinsker, M.S.: Information and information stability of random variables and processes. Holden-Day (1964)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009)
Rothblum, R.: Homomorphic encryption: From private-key to public-key. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 219–234. Springer, Heidelberg (2011)
Simon, H.-U.: A tight loglogn-bound on the time for parallel ram’s to compute nondegenerated boolean functions. Information and Control 55(1), 102–107 (1982)
Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. J. ACM 50, 196–249 (2003)
van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully Homomorphic Encryption from Integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
Bogdanov, A., Lee, C.H. (2013). Limits of Provable Security for Homomorphic Encryption. In: Canetti, R., Garay, J.A. (eds) Advances in Cryptology – CRYPTO 2013. CRYPTO 2013. Lecture Notes in Computer Science, vol 8042. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40041-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-40041-4_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40040-7
Online ISBN: 978-3-642-40041-4
eBook Packages: Computer ScienceComputer Science (R0)