Tight time-space lower bounds for finding multiple collision pairs and their applications

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We consider a collision search problem (CSP), where given a parameter C, the goal is to find C collision pairs in a random function (Formula presented) (where (Formula presented) using S bits of memory. Algorithms for CSP have numerous cryptanalytic applications such as space-efficient attacks on double and triple encryption. The best known algorithm for CSP is parallel collision search (PCS) published by van Oorschot and Wiener, which achieves the time-space tradeoff (Formula presented). In this paper, we prove that any algorithm for CSP satisfies (Formula presented), hence the best known time-space tradeoff is optimal (up to poly-logarithmic factors in N). On the other hand, we give strong evidence that proving similar unconditional time-space tradeoff lower bounds on CSP applications (such as breaking double and triple encryption) may be very difficult, and would imply a breakthrough in complexity theory. Hence, we propose a new restricted model of computation and prove that under this model, the best known time-space tradeoff attack on double encryption is optimal.

اللغة الأصليةإنجليزيّة أمريكيّة
عنوان منشور المضيفAdvances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
المحررونAnne Canteaut, Yuval Ishai
ناشرSpringer
الصفحات405-434
عدد الصفحات30
رقم المعيار الدولي للكتب (المطبوع)9783030457204
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يناير 2020
الحدث39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, كرواتيا
المدة: ١٠ مايو ٢٠٢٠١٤ مايو ٢٠٢٠

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت12105 LNCS

!!Conference

!!Conference39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
الدولة/الإقليمكرواتيا
المدينةZagreb
المدة١٠/٠٥/٢٠١٤/٠٥/٢٠

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Tight time-space lower bounds for finding multiple collision pairs and their applications'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا