Quantum Cryptography | Cryptographic Proofs | Non-Malleable Cryptography | Round-Efficient MPC | Information-Theoretic Cryptography | Obfuscation
Assumptions in Quantum Cryptography.
The last several years of research have helped us aqcuire a rich understanding of the generic assumptions that enable core cryptographic primitives such as digital signatures, commmitments, encryption, generating pseudorandomness, coin flipping, secure computation and more. For instance, a one-way function is a classically efficiently computable function that is hard to invert. This is a fundamental hardness assumption, necessary for the existence of much of modern classical cryptography. The class “minicrypt” contains primitives like pseudorandom generators, digital signatures and symmetric encryption, that can all be based on the existence of one-way functions. At the same time, tasks like key exchange and secure multi-party computation require even stronger, more structured assumptions.
Preliminary research indicates that the landscape of complexity-based hardness changes dramatically when building cryptographic protocols where participants can prepare (and transmit) quantum states. For example, it is often possible to relax computational hardness assumptions by instead relying on the unique properties of quantum information -- such as the fact that measurements delete information. My work, described below, aims to understand the landscape of cryptographic complexity. In particular, the works below describe how cryptographic commitments can be based on a natural quantum relaxation of one-way functions, how this relaxation can be realized from problems that may be #P-hard, and how the existence of cryptographic commitments implies the ability to securely compute on distributed data.
Understanding Secure Computation.
The following works enable a deeper understanding of secure computation in a quantum world, which allows a set of mutually distrustful participants to jointly compute a classical or quantum function on their private inputs, while only revealing the output of the computation to each other. We study tradeoffs in interaction and computational assumptions required for various tasks such as ``zero-knowledge'' teleportation.
Uniquely Quantum Capabilities.
Can a server that obtains a computational encoding of a secret later prove that they deleted the underlying secret, and will not be able to recover it even given unbounded resources or leaked keys? This is classically impossible, but we show how the inherently ``destructive'' nature of quantum information can enable such deletion. While prior work studied deletion in settings where encodings themselves would information-theoretically hide underlying secrets, the following sequence of works enable computationally inaccessible but statistically accessible information to be provably, statistically removed.
The last several years of research have helped us aqcuire a rich understanding of the generic assumptions that enable core cryptographic primitives such as digital signatures, commmitments, encryption, generating pseudorandomness, coin flipping, secure computation and more. For instance, a one-way function is a classically efficiently computable function that is hard to invert. This is a fundamental hardness assumption, necessary for the existence of much of modern classical cryptography. The class “minicrypt” contains primitives like pseudorandom generators, digital signatures and symmetric encryption, that can all be based on the existence of one-way functions. At the same time, tasks like key exchange and secure multi-party computation require even stronger, more structured assumptions.
Preliminary research indicates that the landscape of complexity-based hardness changes dramatically when building cryptographic protocols where participants can prepare (and transmit) quantum states. For example, it is often possible to relax computational hardness assumptions by instead relying on the unique properties of quantum information -- such as the fact that measurements delete information. My work, described below, aims to understand the landscape of cryptographic complexity. In particular, the works below describe how cryptographic commitments can be based on a natural quantum relaxation of one-way functions, how this relaxation can be realized from problems that may be #P-hard, and how the existence of cryptographic commitments implies the ability to securely compute on distributed data.
- Founding Quantum Cryptography on Quantum Advantage (or, Towards Cryptography from #P-Hardness)
with Kabir Tomer (preprint) - Commitments from Quantum One-wayness
with Kabir Tomer (STOC 2024, QIP 2024) - One-way Functions imply Secure Computation in a Quantum World
with James Bartusek, Andrea Coladangelo and Fermi Ma. (CRYPTO 2021, QIP 2021 - Long Plenary Talk, QCrypt 2021 - Invited Talk, both joint with GLSV)
Understanding Secure Computation.
The following works enable a deeper understanding of secure computation in a quantum world, which allows a set of mutually distrustful participants to jointly compute a classical or quantum function on their private inputs, while only revealing the output of the computation to each other. We study tradeoffs in interaction and computational assumptions required for various tasks such as ``zero-knowledge'' teleportation.
- Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)
with James Bartusek and Akshayaram Srinivasan. (CRYPTO 2023, QCRYPT 2023) - A New Framework for Quantum Oblivious Transfer
with Amit Agarwal, James Bartusek and Nishant Kumar. (EUROCRYPT 2023) - On the Round Complexity of Secure Quantum Computation
with James Bartusek, Andrea Coladangelo and Fermi Ma. (CRYPTO 2021, QIP 2021, QCRYPT 2021) - Post-Quantum Multi-Party Computation
with Amit Agarwal, James Bartusek, Vipul Goyal and Giulio Malavolta. (EUROCRYPT 2021)
Uniquely Quantum Capabilities.
Can a server that obtains a computational encoding of a secret later prove that they deleted the underlying secret, and will not be able to recover it even given unbounded resources or leaked keys? This is classically impossible, but we show how the inherently ``destructive'' nature of quantum information can enable such deletion. While prior work studied deletion in settings where encodings themselves would information-theoretically hide underlying secrets, the following sequence of works enable computationally inaccessible but statistically accessible information to be provably, statistically removed.
- Cryptography with Certified Deletion
with James Bartusek. (CRYPTO 2023, QIP 2023) - Publicly-Verifiable Deletion via Target-Collapsing Functions
with James Bartusek and Alexander Poremba. (CRYPTO 2023, QCRYPT 2023) - Obfuscation and Outsourced Computation with Certified Deletion
with James Bartusek, Sanjam Garg, Vipul Goyal, Giulio Malavolta, Justin Raizes and Bhaskar Roberts (Preprint, Preliminary version at QIP 2023) - Weakening Assumptions for Publicly-Verifiable Deletion
with James Bartusek, Giulio Malavolta, Alexander Poremba and Michael Walter. (TCC 2023) - Unclonable Non-interactive Zero-Knowledge
with Ruta Jawale (Preprint)
Zero-Knowledge and Succinct Proof Systems
Many cryptographic settings demand security against malicious attacks, where an adversary may deviate from protocol and behave in arbitrary ways. Cryptographic proofs form the bedrock of security against such attacks, and have facilitated a multitude of powerful capabilities. The following works aim to push the limits of what is achievable in this area: Can we hide secrets in non-interactive proofs, without relying on external sources of trust? Can we efficiently verify the results of inefficient computation?
Despite being startlingly simple to state and tremendously useful, these problems continue to be poorly understood. This is in large part due to limitations in current methods to reason about security, which have been formalized into ``black-box'' barriers. These barriers rule out proof techniques that only access an adversary as a black-box, remaining oblivious to its code. But an adversary's code could be arbitrarily obfuscated or scrambled, and in these settings, it is completely unclear how to use this code in a meaningful way. My work develops new proof techniques that overcome some of these barriers.
Many cryptographic settings demand security against malicious attacks, where an adversary may deviate from protocol and behave in arbitrary ways. Cryptographic proofs form the bedrock of security against such attacks, and have facilitated a multitude of powerful capabilities. The following works aim to push the limits of what is achievable in this area: Can we hide secrets in non-interactive proofs, without relying on external sources of trust? Can we efficiently verify the results of inefficient computation?
Despite being startlingly simple to state and tremendously useful, these problems continue to be poorly understood. This is in large part due to limitations in current methods to reason about security, which have been formalized into ``black-box'' barriers. These barriers rule out proof techniques that only access an adversary as a black-box, remaining oblivious to its code. But an adversary's code could be arbitrarily obfuscated or scrambled, and in these settings, it is completely unclear how to use this code in a meaningful way. My work develops new proof techniques that overcome some of these barriers.
- On Black-Box Verifiable Outsourcing
with Amit Agarwal, Navid Alamati, Srinivasan Raghuraman and Peter Rindal. (TCC 2023) - Weak Zero-Knowledge via the Goldreich-Levin Theorem
with Giulio Malavolta and Kabir Tomer. (ASIACRYPT 2023) - SNARGs for P from Sub-exponential DDH and QR
with James Hulett, Ruta Jawale and Akshayaram Srinivasan. (EUROCRYPT 2022) - SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE
with Ruta Jawale, Yael Kalai and Rachel Zhang. (STOC 2021)
Merge of [JK20] and [KZ20]. - Non-Interactive Distributional Indistinguishability and Non-Malleable Commitments
Dakshita Khurana. (EUROCRYPT 2021) - Compact Ring Signatures from Learning with Errors
with Rohit Chatterjee, Sanjam Garg, Mohammad Hajiabadi, Xiao Liang, Giulio Malavolta, Omkant Pandey and Sina Shiehian. (CRYPTO 2021) - Statistical ZAP Arguments
with Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain and Amit Sahai. (EUROCRYPT 2020) - Weak Zero-Knowledge Beyond the Black-Box Barrier
with Nir Bitansky and Omer Paneth. (STOC 2019, Invited to the SICOMP Special Issue for STOC 2019) - Non-interactive Delegation for Low Space Non-Deterministic Computation
with Saikrishna Badrinarayanan, Yael Kalai, Amit Sahai and Daniel Wichs. (STOC 2018) - Statistical WI (and More) in Two Messages
with Yael Kalai and Amit Sahai. (EUROCRYPT 2018) - Promise Zero Knowledge and Applications to Round Optimal MPC
with Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Yael Kalai and Amit Sahai. (CRYPTO 2018) - Round Optimal Black-Box ``Commit-and-Prove''
with Rafail Ostrovsky and Akshayaram Srinivasan. (TCC 2018) - Distinguisher-Dependent Simulation in 2 Rounds and Applications
with Abhishek Jain, Yael Kalai and Ron Rothblum. (CRYPTO 2017)
Non-Malleable Cryptography
Non-malleable cryptography prevents an adversary from correlating its inputs with those of other honest participants. These have applications to secure auctions, distributed computation, and to systems that remain secure when many sessions are executed concurrently on the internet. My works have demonstrated the possibility of non-malleability without back-and-forth interaction by overcoming strong impossibility results, resolving one of the principal open problems in the area. Some of my followup works have continued to obtain simpler protocols that require no interaction and rely on well-studied assumptions.
Non-malleable cryptography prevents an adversary from correlating its inputs with those of other honest participants. These have applications to secure auctions, distributed computation, and to systems that remain secure when many sessions are executed concurrently on the internet. My works have demonstrated the possibility of non-malleability without back-and-forth interaction by overcoming strong impossibility results, resolving one of the principal open problems in the area. Some of my followup works have continued to obtain simpler protocols that require no interaction and rely on well-studied assumptions.
- On Non-Uniform Security for Black-Box Non-interactive CCA Commitments
with Rachit Garg, George Lu and Brent Waters (EUROCRYPT 2023) - COA-Secure Obfuscation and Applications
with Ran Canetti, Suvradip Chakraborty, Nishant Kumar, Oxana Poburinnaya and Manoj Prabhakaran. (EUROCRYPT 2022) - Black-box Non-Interactive Non-Malleable Commitments
with Rachit Garg, George Lu and Brent Waters. (EUROCRYPT 2021) - Non-Interactive Distributional Indistinguishability and Non-Malleable Commitments
Dakshita Khurana. (EUROCRYPT 2021) - Improved Computational Extractors and their Applications
with Akshayaram Srinivasan. (CRYPTO 2021) - On the CCA Compatibility of Public-Key Infrastructure
with Brent Waters. (PKC 2021) - Computational Extractors with Negligible Error in the CRS Model
with Ankit Garg and Yael Kalai. (EUROCRYPT 2020) - Non-interactive non-malleability from Quantum Supremacy
with Yael Kalai. (CRYPTO 2019) - How to Achieve Non-Malleability in One or Two Rounds
with Amit Sahai. (FOCS 2017, Invited to the SICOMP Special Issue for FOCS 2017) - Round Optimal Concurrent Non-Malleability from Polynomial Hardness
Dakshita Khurana. (TCC 2017) - Breaking the 3 Round Barrier for Non-Malleable Commitments
with Vipul Goyal and Amit Sahai. (FOCS 2016)
Round Efficient (Classical) Multi-party Computation
- Round Optimal Black-Box MPC in the Plain Model
with Yuval Ishai, Amit Sahai and Akshayaram Srinivasan. (CRYPTO 2023) - Round Optimal Black-Box Protocol Compilers
with Yuval Ishai, Amit Sahai and Akshayaram Srinivasan. (EUROCRYPT 2022) - Round-Optimal Black-Box Secure Computation from Two-Round Malicious OT
with Yuval Ishai, Amit Sahai and Akshayaram Srinivasan. (TCC 2022) - Two-Round Maliciously Secure Computation with Super-Polynomial Simulation
with Amit Agarwal, James Bartusek, Vipul Goyal and Giulio Malavolta. (TCC 2021) - On the Round Complexity of Black-Box Secure MPC
with Yuval Ishai, Akshayaram Srinivasan and Amit Sahai. (CRYPTO 2021) - Post-Quantum Multi-Party Computation
with Amit Agarwal, James Bartusek, Vipul Goyal and Giulio Malavolta. (EUROCRYPT 2021) - On Statistical Security in Two Party Computation
with Muhammad Haris Mughees. (TCC 2020) - Promise Zero Knowledge and Applications to Round Optimal MPC
with Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Yael Kalai and Amit Sahai. (CRYPTO 2018) - Round Optimal Concurrent MPC via Strong Simulation
with Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain and Amit Sahai. (TCC 2017)
merged version of [BKS17] and [GJ17]
Questions in Information-Theoretic Cryptography.
- Revisiting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC
with Saikrishna Badrinarayanan, Yuval Ishai, Amit Sahai and Daniel Wichs. (ITC 2022) - New Feasibility Results in Unconditional UC-Secure Computation with (Malicious) PUFs
with Saikrishna Badrinarayanan, Rafail Ostrovsky and Ivan Visconti. (EUROCRYPT 2017) - All Complete Functionalities are Reversible
with Daniel Kraschewski, Hemanta Maji, Manoj Prabhakaran and Amit Sahai. (EUROCRYPT 2016) - Secure Computation from Elastic Noisy Channels
with Hemanta Maji and Amit Sahai. (EUROCRYPT 2016) - Do Distributed Differentially-Private Protocols Require Oblivious Transfer?
with Vipul Goyal, Ilya Mironov, Omkant Pandey and Amit Sahai. (ICALP 2016 - Track A) - Statistical Randomized Encodings: A Complexity Theoretic View
with Shweta Agarwal, Yuval Ishai and Anat Paskin-Cherniavsky. (ICALP 2015 - Track A) - Non-Malleable Multi-Prover Interactive Proofs and Witness Signatures
with Aayush Jain and Vipul Goyal. (Cryptology ePrint Archive 2015) - Black-Box Separations for Differentially Private Protocols
with Hemanta Maji and Amit Sahai. (ASIACRYPT 2014)
Applications of Program Obfuscation.
- Non-Interactive Distributional Indistinguishability and Non-Malleable Commitments
Dakshita Khurana. (EUROCRYPT 2021) - Upgrading to Functional Encryption
with Saikrishna Badrinarayanan, Amit Sahai and Brent Waters. (TCC 2018) - How to Generate and Use Universal Samplers
with Dennis Hofheinz, Tibor Jager, Amit Sahai, Brent Waters and Mark Zhandry. (ASIACRYPT 2016)
merged version of [HJZ14] and [KSW14] - Multi-Party Key Exchange for Unbounded Parties from Indistinguishability Obfuscation
with Vanishree Rao and Amit Sahai. (ASIACRYPT 2015)