Non-Malleable Cryptography | Succinct (and/or) ZK Proof Systems | (Post-)Quantum MPC | Round-Efficient MPC | Information-Theoretic Cryptography | Program Obfuscation
Quantum and Post-Quantum Multi-Party Computation.
Multi-party computation (MPC) enables a set of mutually untrusted participants to jointly compute a function of their private inputs while provably hiding inputs from each other. We investigate foundational questions in quantum and post-quantum MPC. We demonstrate that quantum-hard one-way functions together with quantum communication can be used in a black-box way to obtain general-purpose MPC. This is in contrast to the classical setting, where black-box use of one-way functions does not suffice for MPC. We also investigate the round complexity of protocols for securely computing on private quantum states in the two-party and multi-party settings. Finally, we also obtain the first protocols enabling general-purpose MPC protocol with classical participants but with security against quantum adversaries.
Multi-party computation (MPC) enables a set of mutually untrusted participants to jointly compute a function of their private inputs while provably hiding inputs from each other. We investigate foundational questions in quantum and post-quantum MPC. We demonstrate that quantum-hard one-way functions together with quantum communication can be used in a black-box way to obtain general-purpose MPC. This is in contrast to the classical setting, where black-box use of one-way functions does not suffice for MPC. We also investigate the round complexity of protocols for securely computing on private quantum states in the two-party and multi-party settings. Finally, we also obtain the first protocols enabling general-purpose MPC protocol with classical participants but with security against quantum adversaries.
- One-way Functions imply Secure Computation in a Quantum World
with James Bartusek, Andrea Coladangelo and Fermi Ma. (CRYPTO 2021. Long Plenary Talk at QIP 2021, Invited Talk at QCrypt 2021, both joint with GLSV) - On the Round Complexity of Secure Quantum Computation
with James Bartusek, Andrea Coladangelo and Fermi Ma. (CRYPTO 2021, Contributed Talk at QIP 2021 and QCrypt 2021) - Post-Quantum Multi-Party Computation
with Amit Agarwal, James Bartusek, Vipul Goyal and Giulio Malavolta. (EUROCRYPT 2021)
Succinct (and/or) ZK Proof Systems, and their Applications.
A succinct non-interactive argument (SNARG) is a short, efficiently publicly verifiable proof system attesting to the correctness of relatively inefficient computation, with applications to verifiable outsourcing and scalable blockchains. ZK (zero-knowledge) proofs enable a prover to demonstrate that a statement is true while keeping all associated secrets hidden. We aim to build proof systems for NP (or large subclasses thereof) satisfying succinctness and/or zero-knowledge based on standard, falsifiable cryptographic assumptions. We aim to build non-interactive proof systems while also minimizing reliance on external sources of trust.
A succinct non-interactive argument (SNARG) is a short, efficiently publicly verifiable proof system attesting to the correctness of relatively inefficient computation, with applications to verifiable outsourcing and scalable blockchains. ZK (zero-knowledge) proofs enable a prover to demonstrate that a statement is true while keeping all associated secrets hidden. We aim to build proof systems for NP (or large subclasses thereof) satisfying succinctness and/or zero-knowledge based on standard, falsifiable cryptographic assumptions. We aim to build non-interactive proof systems while also minimizing reliance on external sources of trust.
- 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.
When protocols are executed simultaneously over the internet, one must ensure that an adversary cannot correlate its input with those of other (honest) participants, or use information obtained from one protocol session to launch an attack on another. Non-malleable protocols are a key cryptographic tool that make such defenses possible. We address the following fundamental question in various contexts, with applications to commitments, multi-party computation and randomness extraction. Can one generate cryptographic encodings where given an encoding of a secret, it is impossible to generate an encoding of a related secret? As in the case of proof systems, much of this work focuses on making these encodings non-interactive without relying on external sources of trust.
When protocols are executed simultaneously over the internet, one must ensure that an adversary cannot correlate its input with those of other (honest) participants, or use information obtained from one protocol session to launch an attack on another. Non-malleable protocols are a key cryptographic tool that make such defenses possible. We address the following fundamental question in various contexts, with applications to commitments, multi-party computation and randomness extraction. Can one generate cryptographic encodings where given an encoding of a secret, it is impossible to generate an encoding of a related secret? As in the case of proof systems, much of this work focuses on making these encodings non-interactive without relying on external sources of trust.
- 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 Multi-party Computation.
Multi-party computation (MPC) enables a set of mutually untrusted participants to jointly compute a function of their private inputs while provably hiding inputs from each other. We minimize the round complexity of general-purpose synchronous secure computation under different notions of security against malicious adversaries from a variety of standard assumptions.
Multi-party computation (MPC) enables a set of mutually untrusted participants to jointly compute a function of their private inputs while provably hiding inputs from each other. We minimize the round complexity of general-purpose synchronous secure computation under different notions of security against malicious adversaries from a variety of standard assumptions.
- 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.
We study how ideal realizations of one primitive (often modeled as access to an ideal functionality) enable unconditionally secure realizations of a different primitive. This question is studied in the context of physically inclinable functions implying secure computation, reversing secure access to functionalities, building secure computation from noisy channels and from differentially private multi-party protocols with sufficiently high accuracy.
We study how ideal realizations of one primitive (often modeled as access to an ideal functionality) enable unconditionally secure realizations of a different primitive. This question is studied in the context of physically inclinable functions implying secure computation, reversing secure access to functionalities, building secure computation from noisy channels and from differentially private multi-party protocols with sufficiently high accuracy.
- 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.
Program obfuscation allows one to scramble a program to hide implementation details while retaining its input/output behavior. We study applications of program obfuscation to achieving new types of non-interactive privacy-preserving proofs without setup, upgrading public-key encryption schemes to functional encryption schemes, sampling securely from arbitrary distributions, and variants of non-interactive key exchange for an unbounded number of participants.
Program obfuscation allows one to scramble a program to hide implementation details while retaining its input/output behavior. We study applications of program obfuscation to achieving new types of non-interactive privacy-preserving proofs without setup, upgrading public-key encryption schemes to functional encryption schemes, sampling securely from arbitrary distributions, and variants of non-interactive key exchange for an unbounded number of participants.
- 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)