Lunch In Theory This Thursday (12:00, 10/2, GCS 502c)

[Devansh Gupta]

Hi all,

Please join us for Lunch in Theory this Thursday 10/2 at 12:00 in GCS 502c. 

Reminder: Please bring your own lunch, as lunch will not be provided. However, we’re very grateful to Xinyu, who has kindly brought snacks and soda for this week’s theory lunch.

This week we have Xinyu Mao giving his Thesis Proposal and he will be speaking on hash functions and cryptography. Please find the title and abstract attached.

We look forward to having you all in the talk.

Best,

Devansh

Title: Hash Functions from Weak to Strong: Collision-Resistance and Universal Computational Extractors

Abstract: 

Hash functions are fundamental primitives in modern cryptography, offering a wide spectrum of security properties from weak to strong. This thesis proposal investigates two significant notions in this spectrum: collision resistance and universal computational extractors.

The first part of this work explores relaxations of standard collision-resistant hash functions (CRHs). Our contributions include:

1. A new and arguably the simplest construction of Universal One-Way Hash Functions (UOWHFs), also known as target-collision resistance hash functions, from arbitrary one-way functions (EUROCRYPT 2023).

2. Proposed work to separate Multi-Collision-Resistant Hash Functions (MCRHs) from CRHs. We expect to prove that CRHs cannot be constructed from MCRHs in a black-box manner, meaning that MCRH is a strictly weaker primitive.

The second part focuses on Universal Computational Extractors (UCEs), a class of hash functions designed to securely replace the random oracle in various cryptographic schemes. Here, we present the first post-quantum secure (lattice-based) UCE construction that does not rely on indistinguishability obfuscation (EUROCRYPT 2025). 

Taken together, by providing new constructions and establishing a key separation result, this thesis advances our understanding of various security properties of hash functions.