Abstract
In trying to provide formal evidence that composition has security increasing properties, we ask if the composition of non-adaptively secure permutation generators necessarily produces adaptively secure generators. We show the existence of oracles relative to which there are non-adaptively secure permutation generators, but where the composition of such generators fail to achieve security against adaptive adversaries. Thus, any proof of security for such a construction would need to be non-relativizing. This result can be used to partially justify the lack of formal evidence we have that composition increases security, even though it is a belief shared by many cryptographers.
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Bellare, M., Di Crescenzo, G., Vekatesan, R.: Security amplification by composition: The case of doubly-iterated, ideal ciphers. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 390–407. Springer, Heidelberg (1998)
Baker, T., Gill, J., Solovay, R.: Relativizations of the P =? NP question. SIAM Journal on Computing 4(4), 431–442 (1975)
Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-sound zeroknowledge and its applications. In: 42nd IEEE Symposium on Foundations of Computer Science, pp. 116–125. IEEE Computer Society Press, Los Alamitos (2001)
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Proceedings of the 20th Annual Symposium on Theory of Computing, pp. 103–112. ACM Press, New York (1988)
Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st Annual Symposium on Foundations of Computer Science, pp. 305–313. IEEE Computer Society Press, Los Alamitos (2000)
Gennaro, R., Gertner, Y., Katz, J.: Lower bounds on the efficiency of encryption and digital signature schemes. In: Proceedings of the thirty-fifth ACM symposium on Theory of computing, pp. 417–425. ACM Press, New York (2003)
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: IEEE (ed.) 41st Annual Symposium on Foundations of Computer Science, pp. 325–335. IEEE Computer Society Press, Los Alamitos (2000)
Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: IEEE (ed.) 42nd IEEE Symposium on Foundations of Computer Science, pp. 126–135. IEEE Computer Society Press, Los Alamitos (2001)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM 33(4), 792–807 (1986)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM 38(3), 690–728 (1991)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. In: Proceedings of the 17th Annual Symposium on Theory of Computing, pp. 291–304. ACM Press, New York (1985)
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 44–61. ACM Press, New York (1989)
Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: 40th Annual Symposium on Foundations of Computer Science, pp. 535–542. IEEE Computer Society Press, Los Alamitos (1999)
Luby, M., Rackoff, C.: Pseudo-random permutation generators and cryptographic composition. In: Proceedings of the 18th Annual Symposium on Theory of Computing, pp. 353–363. ACM, New York (1986)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing 17, 373–386 (1988)
Maurer, U., Pietrzak, K.: Composition of random systems: When two weak make one strong. In: The First Theory of Cryptography Conference (2004)
Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of psuedo-random functions. In: 36th Annual Symposium on Foundations of Computer Science, pp. 170–181. IEEE, Los Alamitos (1995)
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosenciphertext security. In: 40th Annual Symposium on Foundations of Computer Science, pp. 543–553. IEEE Computer Society Press, Los Alamitos (1999)
Simon, D.R.: Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Myers, S. (2004). Black-Box Composition Does Not Imply Adaptive Security. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive