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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2020
אירוע39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, קרואטיה
משך הזמן: 10 מאי 202014 מאי 2020

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך12105 LNCS

כנס

כנס39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
מדינה/אזורקרואטיה
עירZagreb
תקופה10/05/2014/05/20

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Tight time-space lower bounds for finding multiple collision pairs and their applications'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי