Abstract
A multiparty computation protocol is said to be adaptively secure if it retains its security even in the presence of an adversary who can corrupt participants as the protocol proceeds. This is in contrast to the static corruption model where the adversary is forced to choose which participants to corrupt before the protocol begins.
A central tool for constructing adaptively secure protocols is noncommitting encryption (Canetti, Feige, Goldreich and Naor, STOC ’96). The original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was linear in the security parameter. In this work, we present the first non-committing encryption scheme that achieves ciphertext expansion that is logarithmic in the message length.
Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key of size \(\tilde{\mathcal O}(n\lambda)\) where n is the message length and λ is the security parameter. The second message consists of a ciphertext of size \({\mathcal O}( n \log n + \lambda )\). The security of our scheme is proved based on the Φ-hiding problem.
Chapter PDF
Similar content being viewed by others
Keywords
- Security Parameter
- Message Length
- Private Evaluation
- Probabilistic Polynomial Time
- Secure Multiparty Computation
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
Beaver, D.: Plug and play encryption. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 75–89. Springer, Heidelberg (1997)
Bellare, M., Boldyreva, A., Kurosawa, K., Staddon, J.: Multirecipient Encryption Schemes: How to Save on Bandwidth and Computation Without Sacrificing Security. IEEE Transactions on Information Theory 53(11), 3927–3943 (2007)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: STOC 1988, pp. 1–10. ACM, New York (1988)
Cachin, C., Micali, S., Stadler, M.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: STOC 1996: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 639–648. ACM, New York (1996)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally Composable Two-Party and Multi-Party Secure Computation. In: STOC 2002 (2002)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty Unconditionally Secure Protocols. In: STOC, pp. 11–19 (1988)
Choi, S.G., Dachman-Soled, D., Malkin, T., Wee, H.: Improved Non-committing Encryption with Applications to Adaptively Secure Protocols. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 287–302. Springer, Heidelberg (2009)
Coppersmith, D.: Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. Journal of Cryptology 10(4), 233–260 (1997)
Cramer, R., Shoup, V.: Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)
Damgård, I., Nielsen, J.B.: Improved Non-committing Encryption Schemes Based on a General Complexity Assumption. In: Crypto 2000: Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, pp. 432–450. Springer, Heidelberg (2000)
Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press (March 2012)
Gentry, C., Ramzan, Z.: Single-Database Private Information Retrieval with Constant Communication Rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)
Goldreich, O., Micali, S., Wigderson, A.: How to Play any Mental Game. In: STOC 1987, pp. 218–229 (1987)
Guruswami, V., Umans, C., Vadhan, S.: Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes. J. ACM 56(4) (July 2009)
Hemenway, B., Ostrovsky, R.: Extended-DDH and Lossy Trapdoor Functions. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 627–643. Springer, Heidelberg (2012), http://eccc.hpi-web.de/report/2009/127/
Kiltz, E., O’Neill, A., Smith, A.: Instantiability of RSA-OAEP under chosen-plaintext attack. In: Proceedings of the 30th annual conference on Advances in cryptology, Santa Barbara, CA, USA. LNCS, pp. 295–313. Springer, Heidelberg (2010)
Lewko, M., O’Neill, A., Smith, A.: Regularity of Lossy RSA on Subdomains and Its Applications. In: Johansson, T., Nguyen, P. (eds.) Advances in Cryptology EUROCRYPT 2013. LNCS, vol. 7881, pp. 55–75. Springer, Heidelberg (2013)
Micali, S., Peikert, C., Sudan, M., Wilson, D.A.: Optimal Error Correction Against Computationally Bounded Noise. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 1–16. Springer, Heidelberg (2005)
Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC 2008: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 187–196. ACM, New York (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Hemenway, B., Ostrovsky, R., Rosen, A. (2015). Non-committing Encryption from Φ-hiding. In: Dodis, Y., Nielsen, J.B. (eds) Theory of Cryptography. TCC 2015. Lecture Notes in Computer Science, vol 9014. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46494-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-46494-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46493-9
Online ISBN: 978-3-662-46494-6
eBook Packages: Computer ScienceComputer Science (R0)