Understanding Adaptivity: Random Systems Revisited

详细信息    查看全文

• 作者：Dimitar Jetchev (18)
  Onur ?zen (18)
  Martijn Stam (19)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7658
• 期：1
• 全文大小：304KB
• 参考文献：1. Armknecht, F., Fleischmann, E., Krause, M., Lee, J., Stam, M., Steinberger, J.: The Preimage Security of Double-Block-Length Compression Functions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.?7073, pp. 233-51. Springer, Heidelberg (2011)
  2. Bellare, M., Rogaway, P.: The Security of Triple Encryption and a Framework?for?Code-Based?Game-Playing?Proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.?4004, pp. 409-26. Springer, Heidelberg (2006) CrossRef
  3. Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: FOCS, pp. 112-17. IEEE Computer Society (1982)
  4. Bogdanov, A., Knudsen, L.R., Leander, G., Standaert, F.-X., Steinberger, J., Tischhauser, E.: Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations (Extended Abstract). In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.?7237, pp. 45-2. Springer, Heidelberg (2012) CrossRef
  5. Ga?i, P., Maurer, U.: Free-Start Distinguishing: Combining Two Types of Indistinguishability Amplification. In: Kurosawa, K. (ed.) ICITS 2009. LNCS, vol.?5973, pp. 28-4. Springer, Heidelberg (2010) CrossRef
  6. Hirose, S.: Some Plausible Constructions of Double-Block-Length Hash Functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol.?4047, pp. 210-25. Springer, Heidelberg (2006) CrossRef
  7. Jetchev, D., ?zen, O., Stam, M.: Collisions Are Not Incidental: A Compression Function Exploiting Discrete Geometry. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.?7194, pp. 303-20. Springer, Heidelberg (2012) CrossRef
  8. Kilian, J., Rogaway, P.: How to Protect DES Against Exhaustive Key Search (an Analysis of DESX). J. Cryptology?14(1), 17-5 (2001) CrossRef
  9. Lee, J., Stam, M., Steinberger, J.: The Collision Security of Tandem-DM in the Ideal Cipher Model. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.?6841, pp. 561-77. Springer, Heidelberg (2011)
  10. Lucks, S.: A collision-resistant rate-1 double-block-length hash function. In: Biham, E., Handschuh, H., Lucks, S., Rijmen, V. (eds.) Symmetric Cryptography. No. 07021 in Dagstuhl Seminar Proceedings, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, Dagstuhl, Germany (2007), http://drops.dagstuhl.de/opus/volltexte/2007/1017
  11. Maurer, U.M.: Indistinguishability of Random Systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol.?2332, pp. 110-32. Springer, Heidelberg (2002) CrossRef
  12. Maurer, U., Pietrzak, K.: The Security of Many-Round Luby–Rackoff Pseudo-Random Permutations. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol.?2656, pp. 544-61. Springer, Heidelberg (2003) CrossRef
  13. Maurer, U.M., Pietrzak, K.: Composition of Random Systems: When Two Weak Make One Strong. In: Naor, M. (ed.) TCC 2004. LNCS, vol.?2951, pp. 410-27. Springer, Heidelberg (2004) CrossRef
  14. Maurer, U.M., Pietrzak, K., Renner, R.S.: Indistinguishability Amplification. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.?4622, pp. 130-49. Springer, Heidelberg (2007) CrossRef
  15. Pietrzak, K.: Indistinguishability and Composition of Random Systems. ETH Zurich, Ph.D. thesis (2005), http://homepages.cwi.nl/%7Epietrzak/publications/thesis05.ps
  16. Shoup, V.: Sequences of Games: A Tool for Taming Complexity in Security Proofs. Cryptology ePrint Archive, Report 2004/332 (2004), http://eprint.iacr.org/
  17. Steinberger, J.P.: The Collision Intractability of MDC-2 in the Ideal-Cipher Model. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol.?4515, pp. 34-1. Springer, Heidelberg (2007) CrossRef
  18. Steinberger, J.P.: Improved security bounds for key-alternating ciphers via hellinger distance. Cryptology ePrint Archive, Report 2012/481 (2012), http://eprint.iacr.org/
  
• 作者单位：Dimitar Jetchev (18)
  Onur ?zen (18)
  Martijn Stam (19)
  
  18. EPFL IC IIF LACAL, Station 14, CH-1015, Lausanne, Switzerland
  19. Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol, BS8 1UB, UK
  
• ISSN：1611-3349

文摘

We develop a conceptual approach for probabilistic analysis of adaptive adversaries via Maurer’s methodology of random systems (Eurocrypt-2). We first consider a well-known comparison theorem of Maurer according to which, under certain hypotheses, adaptivity does not help for achieving a certain event. This theorem has subsequently been misinterpreted, leading to a misrepresentation with one of Maurer’s hypotheses being omitted in various applications. In particular, the only proof of (a misrepresentation of) the theorem available in the literature contained a flaw. We clarify the theorem by pointing out a simple example illustrating why the hypothesis of Maurer is necessary for the comparison statement to hold and provide a correct proof. Furthermore, we prove several technical statements applicable in more general settings where adaptivity might be helpful, which can be seen as the random system analogue of the game-playing arguments recently proved by Jetchev, ?zen and Stam (TCC-2).