Sanjam Garg

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.

We present a publicly-detectable watermarking scheme for LMs: the detection algorithm contains no secret information, and it is executable by anyone. We embed a publicly-verifiable cryptographic signature into LM output using rejection sampling and prove that this produces unforgeable and distortion-free (i.e., undetectable without access to the public key) text output. We make use of error-correction to overcome periods of low entropy, a barrier for all prior watermarking schemes. We implement our scheme and find that our formal claims are met in practice.