Abstract
To prove that a secure key-agreement protocol exists one must at least show P ≠NP. Moreover any proof that the sequential composition of two non-adaptively secure pseudorandom functions is secure against at least two adaptive queries must falsify the decisional Diffie-Hellman assumption, a standard assumption from public-key cryptography. Hence proving any of this two seemingly unrelated statements would require a significant breakthrough. We show that at least one of the two statements is true.
To our knowledge this gives the first positive cryptographic result (namely that composition implies some weak adaptive security) which holds in Minicrypt, but not in Cryptomania, i.e. under the assumption that one-way functions exist, but public-key cryptography does not.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-34547-3_36
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
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory IT-22(6), 644–654 (1976)
El-Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4), 469–472 (1985)
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The Relationship between Public Key Encryption and Oblivious Transfer. In: FOCS, pp. 325–335 (2000)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)
Harnik, D., Naor, M.: On the Compressibility of NP instances and Cryptographic Applications (manuscript, 2005)
Holenstein, T.: Personal Communication (2005)
Holenstein, T.: Immunization of key-agreement schemes, PhD.thesis. PhD thesis, ETH Zürich (to appear, 2006)
Impagliazzo, R.: A personal view of average-case complexity. In: Structure in Complexity Theory Conference, pp. 134–147 (1995)
Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-way Permutations. In: Proc, 21th ACM Symposium on the Theory of Computing (STOC), pp. 44–61 (1989)
Maurer, U.M.: Secret key agreement by public discussion from common information. IEEE Transactions on Information Theory 39(3), 733–742 (1993)
Maurer, U., Pietrzak, K., Renner, R.: Indistinguishability Amplification (manuscript, 2006)
Myers, S.: Black-box composition does not imply adaptive security. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 189–206. Springer, Heidelberg (2004)
Pietrzak, K.: Composition does not imply adaptive security. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 55–65. Springer, Heidelberg (2005)
Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)
Rudich, S.: The use of interaction in public cryptosystems (extended abstract). In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 242–251. Springer, Heidelberg (1992)
Shannon, C.E.: A mathematical theory of communication. Bell Systems Technical Journal 27, 373–423, 623–656 (1948)
Wee, H.: Finding pessiland. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 429–442. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pietrzak, K. (2006). Composition Implies Adaptive Security in Minicrypt. In: Vaudenay, S. (eds) Advances in Cryptology - EUROCRYPT 2006. EUROCRYPT 2006. Lecture Notes in Computer Science, vol 4004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11761679_20
Download citation
DOI: https://doi.org/10.1007/11761679_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34546-6
Online ISBN: 978-3-540-34547-3
eBook Packages: Computer ScienceComputer Science (R0)