Lunch In Theory This Thursday (12:00 PM, 04/30, GCS 302c)

[Devansh Gupta]

Hi all,

Please join us for the last Lunch in Theory of the semester this Thursday, 04/30 at 12:00 PM in GCS 302c. This week we have Xinyu Mao giving his thesis defense. Please find the details below.

Reminder: Please bring your own lunch, as lunch will not be provided.

Best,

Devansh

===

Topic: Xinyu's Dissertation Defense
Time: Apr 30, 2026 12:00 PM Pacific Time (US and Canada)
Join Zoom Meeting
https://usc.zoom.us/j/7712694864?pwd=VFExYjBTZUZ1ei9weXN1MlJGdHF1dz09&omn=98738442880

Meeting ID: 771 269 4864
Passcode: 233233

===

Thank you!

===

Title: Advancing Theory of Hash Functions and Random Oracles: Collision Resistance, Universal Computational Extractor, and More

Committee members: Jiapeng Zhang (Chair), David Kempe, Shanghua Teng, and Jianfeng Zhang (from the math department).

 

Abstract. 

Hash functions with various security properties are among the most fundamental and versatile objects in cryptography. Hash functions also inspire one of the most fruitful paradigms for designing and analyzing cryptosystems — the random-oracle (RO) methodology. The security properties of hash functions, from weak to strong, form a wide spectrum.

This dissertation advances the theory of hash functions and random oracles by investigating the intrinsic complexity of several security properties and by constructing hash functions sufficient to instantiate random oracles. We focus on two main directions.

- Collision resistance and its relaxations. We study the theoretical landscape of collision-resistant hash functions (CRH) and their natural relaxations. We establish a black-box
separation for the multi-collision-resistant hash (MCRH) hierarchy, proving that standard CRH cannot be constructed from MCRH in a black-box manner. We also separate distributional CRH from MCRH in the black-box model. Exploring the weaker property of target collision resistance, we present the arguably simplest, and first non-adaptive, construction of universal one-way hash functions (UOWHFs) from arbitrary one-way functions. Our construction yields a construction of UOWHF in NC0 assuming one-way functions in NC1.

- Instantiating random oracles. We construct hash functions with strong, RO-like properties sufficient to securely instantiate random oracles in several applications. To this end, we introduce a new primitive called the obliviously programmable function (OPF), showing that it can effectively replace indistinguishability obfuscation in the constructions of hash functions with advanced properties. By combining OPF with point obfuscation with auxiliary input (AIPO), we construct (i) universal computational extractors, (ii) multi-bit AIPO, (iii) secure PKE under invertible key leakage, and (iv) universal hardcore functions with polynomial output length. Then we instantiate OPF and AIPO based on strong yet plausible lattice assumptions, and hence achieve the first post-quantum secure constructions of all the aforementioned primitives (i)-(iv).

Though the results in this dissertation involve very different assumptions and techniques—from black-box separation to advanced lattice-based constructions—they collectively represent progress toward understanding the wide spectrum of hash function security properties.

===