[Colloquium] Reminder: [masters-presentation] Akshima/MS Presentation/Dec 6, 2019

[Margaret Jaffey]

This is a reminder about Akshima’s MS Presentation tomorrow.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey
Student Affairs Administrator
    for the PhD program
Department of Computer Science
The University of Chicago
John Crerar Library, Room 350
5730 S. Ellis Ave.

773-702-6011
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=


> On Nov 22, 2019, at 10:55 AM, Margaret Jaffey <margaret at cs.uchicago.edu> wrote:
> 
> This is an announcement of Akshima’s MS Presentation.  
> 
> ------------------------------------------------------------------------------
> Date:  Friday, December 6, 2019
> 
> Time:  2:00 PM
> 
> Place:  John Crerar Library 298
> 
> M.S. Candidate:  Akshima 
> 
> M.S. Paper Title: Time-Memory Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions
> 
> Abstract:
> We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary S-bit auxiliary advice input about the random oracle and T queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage Ω(ST^2/2^n), where n is the output length, beating the birthday bound by a factor of S. These attacks were shown to be optimal.
>    
>  We observe that the collisions produced are very long, on the order T blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find short collisions. We first exhibit a simple attack for finding B-block-long collisions achieving advantage Ω(STB/2^n). We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the ST^2/2^n bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length 1, length 2, and unbounded-length collisions: Namely, the optimal attacks achieve (up to logarithmic factors) order of (S+T)/2^n, ST/2^n and ST^2/2^n advantage.  We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.
> 
> Akshima's advisor is Prof. David Cash
> 
> Login to the Computer Science Department website for details:
> https://newtraell.cs.uchicago.edu/phd/ms_announcements#akshima <https://newtraell.cs.uchicago.edu/phd/ms_announcements#akshima>
> 
> =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> Margaret P. Jaffey
> Student Affairs Administrator
>     for the PhD program
> Department of Computer Science
> The University of Chicago
> John Crerar Library, Room 350
> 5730 S. Ellis Ave.
> 
> 773-702-6011
> =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> 
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191205/a1944146/attachment.html>