Aniket Kate

We present a new framework for constructing practically efficient publicly verifiable secret sharing (PVSS) with non-interactive dealers, in that the dealer may go offline after sending a single message, and is not involved in the share verification process. We use identity-based encryption (IBE) and commitments as the main ingredients and avoid expensive zero-knowledge proofs. By instantiating them with post-quantum secure schemes, a lattice-based IBE and a hash-based commitment, we obtain our first construction: a post-quantum secure PVSS with non-interactive dealers that outperforms the prior lattice-based practical construction by Gentry et al. [Eurocrypt 2022]. However, to enable the aggregation of PVSS transcripts (which facilitates many additional applications such as secure voting), we propose our second construction by replacing hash-based commitments with Pedersen's homomorphic commitments. While this does not achieve full-fledged post-quantum security (as Pedersen's scheme is not quantum safe), it still provides privacy against a post-quantum adversary. We prove the security of this construction in a new model, which we call long-lasting security. This model guarantees that the protocol is secure in the present (pre-quantum era) while maintaining privacy in the long term (post-quantum era). This new model is of independent interest for constructing efficient schemes that are resilient to the harvest-now-decrypt-later line of attacks. In this model, we propose a blockchain-compatible secure voting scheme using our PVSS scheme. Our PVSS schemes demonstrate practical efficiency: our post-quantum PVSS shares a secret among 1024 receivers in 667 ms and verifies the dealing in < 5 ms, and communicates 4.4MB, overall whereas the state of the art [Gentry et al., Eurocrypt 2022] communicates 251MB and requires 2060s for dealing the secret.

We develop a distributed service for generating correlated randomness (e.g. permutations) for multiple parties, where each party's output is private but the computation is publicly verifiable. This service provides users with a low-cost publicly verifiable way to play on-chain poker in real-time, without a trusted party. Our privacy-preserving service is backed by a committee of compute providers, who run a multi-party computation (MPC) protocol to produce an (identity-based) encrypted permutation of a deck of cards, in an offline phase well ahead of when players' identities are known. When the players join, what we call the online phase, they decrypt their designated cards immediately after deriving the identity-based decryption keys, a much simpler computation. The MPC protocol also generates a publicly-verifiable proof that the output is a permutation – this is achieved by applying collaborative SNARK techniques by Ozdemir and Boneh [Usenix Sec'22]. In our construction, we introduce a new notion of succinctly verifiable multi-identity-based encryption (SVME), which extends the existing notion of verifiable encryption to a multi-identity-based setting, but with a constant-sized proof – this may be of independent interest. We instantiate this for a permutation relation (defined over a small set) along with identity-based encryption, polynomial commitments, and succinct proofs – our choices are made to enable a distributed computation when the card deck is always secret-shared. Moreover, we design a new protocol to efficiently generate a secret-sharing of random permutation of a small set, which is run prior to distributed SVME. We offer a rigorous UC-based formalization in a highly modularized fashion. Finally, we demonstrate practicality with an implementation that shows that for 8 MPC parties, generating a secret publicly verifiable permutation of 52 cards offline takes under 3 seconds, while accessing cards for a player takes under 0.3 seconds. When playing over a smart contract, a player incurs at most 200 gas units for each hand of two cards ( 0.002 o n A p t o s a t t h e t i m e o f w r i t i n g ) . A s h u f f l i n g s e r v i c e w i t h 8 n o d e s i n c u r s 0.0015 in cloud compute fees to produce a shuffled deck of 52 cards.

The Tor network offers network anonymity to its users by routing their traffic through a sequence of relays. A group of nine directory authorities maintains information about all available relay nodes using a distributed directory protocol. We observe that the current protocol makes a strong synchrony assumption, which makes it vulnerable to natural as well as adversarial non-synchronous communication scenarios over the Internet. In this paper, we show that it is possible to cause a failure in the Tor directory protocol by targeting a majority of the authorities for only five minutes using a well-executed distributed denial-of-service (DDoS) attack. We demonstrate this attack in a controlled environment and show that it is cost-effective for as little as $53.28 per month to disrupt the protocol and to effectively bring down the entire Tor network. To mitigate this problem, we consider the popular partial synchrony assumption that ensures protocol security even when the network delays are large and unknown initially. We design a new Tor directory protocol that leverages a standard partial-synchronous consensus protocol to solve this problem, while also proving its security. We have implemented a prototype in Rust, demonstrating comparable performance to the current protocol.