Date: February 23, 2026
Time: 3:45-5 p.m.
Location: Computing and Information Science Building, Room 450 or Click here to attend via Zoom
Speaker: Satyajeet Nagargoje
This is joint work with Divesh Aggarwal, Pranjal Dutta, Saswata Mukherjee and Maciej Obremski.
Abstract: Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by generating nearly uniform randomness from two independent weak sources. Moreover, cryptographic systems must also be resilient to leakage and tampering attacks, necessitating the development of non-malleable two-source extractors.
In this work, we construct a two-source non-malleable extractor, where a random low-degree polynomial is sampled once and made accessible to independent random sources, the distinguisher, and the tamperer. We also construct a randomised two-source extractor on the way. Our extractor requires only linear min-entropy in both sources and doesn't rely on strong computational assumptions, in contrast to prior constructions requiring computational assumptions such as sub-exponential hardness of the Decisional Diffie-Hellman (DDH) problem. Notably, our construction builds upon and relies on the recent breakthrough proof of the polynomial Freiman-Ruzsa conjecture. A connection of the Freiman-Ruzsa conjecture with two-source extractors was considered in prior work [ZBS11],[AGMR24], but their construction did not achieve non-malleability.
This work appeared in CRYPTO2025.