|
Welcome!
I am a PhD candidate at Northeastern, where I am advised by abhi shelat.
My research interests lie in the design of cryptographic protocols with a focus on secure multiparty computation (MPC). Specifically, I am interested in developing MPC techniques to realize functionalities of practical relevance, for instance to decentralize the computation of ECDSA, Schnorr/EdDSA, and RSA.
Reach me at ykondi at ccs dot neu dot edu.
I received my Bachelor's and Master's degrees from the International Institute of Information Technology, Bangalore (IIITB) in 2017, where I was advised by Ashish Choudhury. I was also supervised by Arpita Patra at the CrIS Lab, Indian Institute of Science (IISc).
I spent summer 2020 (and part-time Fall 2020) interning with the crypto group at Novi Research, where I was hosted by Valeria Nikolaenko.
I visited Claudio Orlandi at the Aarhus Crypto Group in summer 2019.
Manuscript(s)
Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation
Yashvanth Kondi and abhi shelat
[TL;DR]
[paper]
Problem: Is Fischlin's transform computationally optimal, and is it inherently limited to Sigma protocols with quasi-unique responses?
Result: With EdDSA signature aggregation as a motivating application, we show how a multicollision based proof-of-work and a uniquely suited polynomial evaluation algorithm can improve the computation cost of the baseline construction [CGKN21] by 70x-200x. The multicollision based proof-of-work also improves the random oracle query complexity of Fischlin's NIZK, in some cases even matching a new lower bound that we present. Finally, we show by means of an attack that Fischlin's transform does not preserve Witness Indistinguishability in certain contexts. We also show how randomizing Fischlin's transform fixes the problem, thereby extending its applicability to any strong special sound Sigma protocol.
Publications
Guaranteed Output in O(sqrt(n)) Rounds for Round-Robin Sampling Protocols
EUROCRYPT 2022
Ran Cohen, Jack Doerner, Yashvanth Kondi, and abhi shelat
[ TL;DR]
[ paper]
Problem: Is it possible to achieve Guaranteed Output Delivery for a non-trivial n-party functionality with resilience to n-1 corruptions, in o(n) rounds?
Result: Yes, we give a general transformation which when applied to a "round robin" sampling protocol that requires O(n) sequential broadcast rounds, yields an O(√n) round protocol that achieves the same functionality (albeit permitting inconsequential bias). This class of protocols includes the "powers of Tau" protocol for sampling the trusted setup for pairing based schemes (such as SNARKs and polynomial commitments), as well as certain verifiable mixnets.
Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions
CRYPTO 2021
François Garillot, Yashvanth Kondi, Payman Mohassel, and Valeria Nikolaenko
[ TL;DR]
[ paper]
[videos: short, long]
[ slides]
[ .bib]
Problem: How can we construct a threshold Schnorr signing scheme with resilience to state resets and bad randomness during signing, like EdDSA offers for the single party setting?
Result: The bottleneck for this problem lies in stateless deterministic multiparty nonce derivation, which requires all parties to prove that they have derived a nonce by applying a PRF on a committed key. We instantiate such a proof in the zero-knowledge from garbled circuits (ZKGC) paradigm, and construct two new tools to improve efficiency: an exponentiation garbling gadget, and committed OT from UC Commitments, both of which are of benefit to the ZKGC paradigm in other settings as well. A proof per our scheme costs only a small constant number of exponentiations.
Non-interactive half-aggregation of EdDSA and variants of Schnorr signatures
CT-RSA 2021
Konstantinos Chalkias, François Garillot, Yashvanth Kondi, and Valeria Nikolaenko
[ TL;DR]
[ paper]
[ video]
[ slides]
[ code]
[ .bib]
Problem: Can we aggregate the effect of a number of independent Schnorr signatures into a single compressed signature?
Result: We construct two non-interactive proof-of-knowledge schemes for the language of Schnorr signatures, so that a proof can serve as an aggregation of multiple signatures. The basic scheme (with a rewinding extractor) saves 50% in bandwidth relative to naive transmission of the signatures, while the scheme with online extraction saves 50-e% for some parameter e. We benchmark both schemes to demonstrate their practicality. Additionally, we give strong evidence that achieving better compression would imply proving statements specific to the hash function in Schnorr’s scheme, which would entail significant effort for standardized schemes such as SHA2 in EdDSA.
Refresh When You Wake Up: Proactive Threshold Wallets with Offline Devices
IEEE S&P (Oakland) 2021
Yashvanth Kondi, Bernardo Magri, Claudio Orlandi, and Omer Shlomovits
[ TL;DR]
[ paper]
[ video]
[ slides]
[ code]
[ .bib]
Problem: Can we design a (t,n) threshold signature scheme where only t parties come online to rerandomize the state of the whole system, while the n-t offline folks catch up at their own pace?
Result: In the (2,n) setting we give an efficient protocol tailored to cryptocurrency wallets, exploiting the structure of ECDSA/Schnorr and using the transactions that the wallet already sends to the blockchain to synchronize. However in the general (t,n) setting we prove this task is possible if and only if there is an honest majority among t.
Multiparty Generation of an RSA Modulus
CRYPTO 2020
Journal of Cryptology (full version)
Megan Chen, Ran Cohen, Jack Doerner, Yashvanth Kondi, Eysa Lee, Schuyler Rosefield, and abhi shelat
[ TL;DR]
[ paper]
[videos: short, long (Jack)]
[ slides]
[ .bib]
Problem: Can we construct a clean, generically instantiable multiparty protocol for distributed RSA modulus sampling?
Result: Yes, we give an MPC protocol for sampling an RSA modulus with a clean abstract description and proof, only assuming that factoring is hard. The tools are generic and permit various instantiations, and we give a specific one using OT (extension) that substantially improves on prior work.
Threshold ECDSA from ECDSA Assumptions: The Multiparty Case
IEEE S&P (Oakland) 2019
Jack Doerner, Yashvanth Kondi, Eysa Lee, and abhi shelat
[ TL;DR]
[ paper]
[ video]
[ slides]
[ code]
[ .bib]
Problem: How can we construct arbitrary (t,n) ECDSA signing using tools native to ECDSA?
Result: Using a few generic unauthenticated multipliers to produce candidate signature shares, we devise an efficient "check in the exponent" mechanism to confirm honest behaviour, and prove that subverting these checks implies solving CDH in the ECDSA curve. Signing avoids zero-knowledge proofs, and can be completely preprocessed to avoid interaction once the message is known.
Secure Two-party Threshold ECDSA from ECDSA Assumptions
IEEE S&P (Oakland) 2018
Jack Doerner, Yashvanth Kondi, Eysa Lee, and abhi shelat
[ TL;DR]
[ paper]
[ slides]
[ code]
[ .bib]
Problem: How can we construct threshold two-party ECDSA signing using tools native to ECDSA?
Result: We show that OT extension based multipliers combined with checking non-linear relations in the exponent yields very efficient trustless (2,n) ECDSA signing that only relies on hardness of CDH in the ECDSA curve. Signing can be compressed to only two messages, and is shown via benchmarks to be substantially more efficient than prior Paillier-based protocols.
Efficient Adaptively Secure Zero-knowledge from Garbled Circuits
PKC 2018
Chaya Ganesh, Yashvanth Kondi, Arpita Patra, and Pratik Sarkar
[ TL;DR]
[ paper]
[ slides]
[ .bib]
Problem: Can ZK secure against adaptive corruptions be practical?
Result: Yes, we show that the practical garbled-circuit based ZK protocol of JKO13 can be made adaptively secure with the correct choice of OT. Moreover we show how to compress JKO13 to only three rounds in the random oracle model.
Privacy-Free Garbled Circuits for Formulas: Size Zero and Information-Theoretic
CRYPTO 2017
Yashvanth Kondi and Arpita Patra
[ TL;DR]
[ paper]
[ video]
[ .bib]
Problem: Can we circumvent the 1-ciphertext lower bound for privacy-free grabling?
Result: Yes, we give an information-theoretic construction that gets around this lower bound. It can be composed to natively garble formulas that comprise AND, XOR, negation, and threshold gates in the privacy-free setting.
External Reviews
Journal of Cryptology, IEEE T-IFS.
EUROCRYPT (2022, 2021, 2020, 2019, 2018), CRYPTO (2021, 2018), PODC (2021), ASIACRYPT (2020, 2019, 2018, 2017),
CCS (2019), TCC (2020, 2019), PKC (2022, 2021, 2019, 2017), SCN (2020)
|