Yashvanth Kondi
|
Welcome!
Threshold ECDSA in Three Rounds
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. Secure Multiparty Computation with Identifiable Abort from Vindicating Release 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). Publications
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 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. Program Committees
EUROCRYPT 2024, TPMPC 2023
External Reviews
Journal of Cryptology, IEEE T-IFS.
EUROCRYPT (2023, 2022, 2021, 2020, 2019, 2018), CRYPTO (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) |