Yashvanth Kondi
|
Welcome!
Three-Round Threshold ECDSA
Jack Doerner, Yashvanth Kondi, Eysa Lee, and abhi shelat
Problem: Can we achieve 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 an "ECDSA tuple" [Abram et al., SP 22] in two rounds as a depth-1 multiplication, and then verify the correlation via simple pairwise checks in the exponent. The tuple then enables a simple information-theoretic signature assembly phase. We give a cost analysis for OT based multiplication, although our protocol can be instantiated with Paillier, or even BGW to improve the state of the art in the honest majority setting. 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. External Reviews
Journal of Cryptology, IEEE T-IFS.
EUROCRYPT (2023, 2022, 2021, 2020, 2019, 2018), CRYPTO (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) |