Yashvanth Kondi
|
Welcome!
[+] Selected Projects
Threshold cryptography refers to a class of custom MPC protocols to securely decentralize cryptographic operations. I work on the design of such protocols, particularly in settings that involve cumbersome non-linearity such as threshold ECDSA signing, RSA modulus sampling, and EdDSA-style deterministic nonce derivation among others.
Open Finance frameworks enable the portability of personal financial data, in order to avail of financial services. However, most such ecosystems expose user data in plaintext form to Data Fiduciaries, which can have several unintended consequences as they effectively become single points of failure. My team at Silence Laboratories provides an MPC-based solution to decentralize the processing of user data in such ecosystems, which you can read about in our whitepaper (accompanying technical overview), my RWC talk, or an external opinion piece. Screening Transactions in the context of cross-border payments is necessary to comply with anti-money laundering regulations across jurisdictions. However, this screening is commonly an opaque process executed by trusted third parties with a high false positive rate. The Bank for International Settlements' Project Mandala seeks to streamline this process by having banks screen transactions directly peer-to-peer, via a secure protocol that incorporates private inputs. Our Silent Compute library provides the secure two-party computation in their pilot deployment, which you can learn more about from the BIS report, or my talk at RWMPC. [+] Papers
Publications
Separating Broadcast from Cheater Identification Yashvanth Kondi and Divya Ravi ACM CCS 2025
Problem: How can we identify non-responsive and cheating parties in MPC without invoking broadcast, in a manner that is certifiable to outside parties?
Result: We define the problem precisely, and show that in the absence of a broadcast channel (i.e. p2p channels only) even with a PKI, it is impossible to achieve this notion in the dishonest majority setting. We give a simple construction of a suitable broadcast-like primitive in the honest majority setting, and use it to construct a compiler that removes the dependence of any MPC protocol on broadcast when Identifiable Abort is desired. We report benchmarks of an implementation of our technique applied to threshold ECDSA signing, showing that with a signing threshold t = 10, the computational burden of the worst case execution path is under 500ms. Sometimes You Can't Distribute Random-Oracle-Based Proofs CRYPTO 2024 Jack Doerner, Yashvanth Kondi, and Leah Namisa Rosenbloom
Problem: Under what conditions does a random oracle based NIZK permit an MPC protocol to distribute its computation?
Result: We investigate the conditions under which straight-line extractable NIZKs in the random oracle model (i.e. without a CRS) permit multiparty realizations that are black-box in the same random oracle. We show that even in the semi-honest setting, any MPC protocol to compute such a NIZK cannot make black-box use of the random oracle or a hash function instantiating it if security against all-but-one corruptions is desired, unless the size of the NIZK grows with the number of parties. Secure Multiparty Computation with Identifiable Abort from Vindicating Release CRYPTO 2024 Ran Cohen, Jack Doerner, Yashvanth Kondi, and abhi shelat
Problem: How much does it cost to identify cheaters in practical dishonest majority MPC?
Result: We show that standard protocols for dishonest majority MPC, when carefully augmented with the ability to open one of the party's inputs ("vindicating release"), yields identifiable abort. Our constructions are straightforward to analyze and use as they function in the real-ideal paradigm, in contrast to previous works that rely on concrete protocols as building blocks. We show that our simple abstractions do not pay a penalty in efficiency, by means of a concrete construction based on the PVW OT, plugged into SoftSpoken OT extension, which in turn is used to build VOLE and then MPC for any sampling functionality (such as correlated randomness consumed by MPC-IA protocols for private inputs).
Threshold ECDSA in Three Rounds
IEEE S&P (Oakland) 2024 Jack Doerner, Yashvanth Kondi, Eysa Lee, and abhi shelat
Problem: Can we achieve efficient threshold ECDSA signing in three rounds?
Result: We give a simple such protocol that makes blackbox use of any two-round secure multiplication primitive. Roughly, we first generate a candidate "ECDSA tuple" [ANOSS22] in two rounds with straightforward use of VOLE, and then verify the correctness of the correlation via simple pairwise checks in the exponent. Each check is statistical, costs each party a couple of exponentiations, can be done in parallel with the VOLE, and requires no additional information or machinery. Once verified, the tuple then enables a simple non-interactive information-theoretic signature assembly phase. We give a cost analysis for OT based VOLE, although our protocol can in principle be instantiated with Additively Homomorphic Encryption, or even BGW/GRR to improve the state of the art in the honest majority setting. Two-Round Stateless Deterministic Two-Party Schnorr Signatures From Pseudorandom Correlation Functions CRYPTO 2023 Yashvanth Kondi, Claudio Orlandi, and Lawrence Roy
Problem: Can we construct threshold Schnorr signing protocols that are resilient to state resets, while making only blackbox use of cryptography?
Result: We give a novel approach to resettable threshold Schnorr signing, by making only blackbox use of Pseudorandom Correlation Functions. This avoids having to prove statements about PRFs in ZK—which was the only previously known approach, and was bottlenecked by the circuit complexity of PRFs. We leverage recent progress in PCFs based on PRFs and Paillier, to obtain resettable threshold Schnorr protocols that are resilient to covert and malicious adversaries respectively. Our covert protocol is nearly as efficient as semi-honest signing, and the malicious protocol achieves the lowest known bandwidth consumption. Witness-Succinct Universally-Composable SNARKs EUROCRYPT 2023 Chaya Ganesh, Yashvanth Kondi, Claudio Orlandi, Mahak Pancholi, Akira Takahashi, and Daniel Tschudi
Problem: Is it feasible to obtain UC-secure witness-succinct SNARKs under well-studied setup assumptions?
Result: Yes---we give a compiler in the random oracle model that lifts any simulation extractable SNARK (with non-blackbox extraction) to a UC secure one, while preserving the same level of witness succinctness. This enables us to obtain the first constant-sized UC secure SNARK as a corollary. Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance IEEE S&P (Oakland) 2023 Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat, and LaKyah Tyner
Problem: Given the non-linear structure of BBS+ credentials, how can we distribute their issuance?
Result: Leveraging techniques developed in the context of Threshold ECDSA for secure inversion, we construct a distributed issuance protocol for BBS+ credentials. The protocol has a 'single roundtrip' interaction pattern: the client sends a message to the servers, the servers are able to compute shares of a credential within a single roundtrip of communication with each other, and finally these shares are communicated to the client, who then assembles the credential locally. Our benchmarks show that the "MPC overhead" of this distributed issuance structure is only a few milliseconds for common parameters. Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation ASIACRYPT 2022 Yashvanth Kondi and abhi shelat
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.
Guaranteed Output in O(sqrt(n)) Rounds for Round-Robin Sampling Protocols
EUROCRYPT 2022 Journal of Cryptology (full version) Ran Cohen, Jack Doerner, Yashvanth Kondi, and abhi shelat
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
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
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
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
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
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
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
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
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. [+] Service Program Committees
Financial Cryptography (2026, 2025), ACM ASIACCS 2026, LATINCRYPT 2025 , TPMPC (2025, 2023), EUROCRYPT 2024
External Reviews
Journal of Cryptology, IEEE T-IFS, IEEE TDSC.
EUROCRYPT (2023, 2022, 2021, 2020, 2019, 2018), CRYPTO (2024, 2023, 2022, 2021, 2018), CCS (2022, 2019) PODC (2021), ASIACRYPT (2022, 2020, 2019, 2018, 2017), TCC (2020, 2019), PKC (2022, 2021, 2019, 2017), ACNS (2023), SCN (2020) [+] Brief Bio
I currently live in Singapore with my partner Anisha, who does amazing work on climate justice. Up until Fall '23, I was a Postdoctoral Researcher at the Cryptography and Security Group at Aarhus University, where I was hosted by Claudio Orlandi.
Prior to that, I completed my PhD at Northeastern in 2022 (thesis), under the supervision of abhi shelat.
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 spent 2016-17 visiting Arpita Patra at the CrIS Lab, Indian Institute of Science (IISc).
|