Complexity Theory and Cryptography
Overview
People
Outcome
Overview
In this project, deep questions in computational complexity theory are studied through the lens of cryptographic properties of functions.
Active from 2016
People
Outcome
- Saumya Goyal, Varun Narayanan, and Manoj Prabhakaran, “Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions,” TCC 2022.
- Kaartik Bhushan, Ankit Kumar Misra, Varun Narayanan and Manoj Prabhakaran, “Secure Non-Interactive Reducibility is Decidable,” TCC 2022.
- Pratyush Agarwal, Varun Narayanan, Shreya Pathak, Manoj Prabhakaran, Vinod Prabhakaran and Mohammad Ali Rehan, “Secure Non-Interactive Reduction and Spectral Analysis of Correlations,” Eurocrypt 2022.
- Shweta Agrawal, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan, Manoj Prabhakaran , Vinod Prabhakaran and Alon Rosen, “Secure Computation from One-Way Noisy Communication, or: Anti-Correlation via Anti-Concentration,” CRYPTO 2021.
- Shweta Agrawal, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan, Manoj Prabhakaran, Vinod Prabhakaran and Alon Rosen, “Cryptography from One-Way Communication: On the Completeness of Finite Channels,” Asiacrypt 2020.
- Varun Narayanan, Manoj Prabhakaran and Vinod Prabhakaran, “Zero-Communication Reductions,” TCC 2020.
