Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness tradeoff: supporting fewer instructions results in smaller processor circuits (which improves performance), but may result in more program execution steps because non-supported instruction must be emulated over multiple processor steps (diminishing performance).

We propose SublonK --- a new succinct non-interactive argument of knowledge (SNARK). SublonK is the first SNARK that achieves both a constant proof size and prover runtime that grows only with the size of the ``active part'' of the executed circuit (i.e., *sub-linear* in the size of the entire circuit) while being *black-box in cryptography*. For instance, consider circuits encoding conditional execution, where only a fraction of the circuit is exercised by the input. For such circuits, the prover runtime in SublonK grows only with the exercised execution path. Our new construction builds on PlonK [Gabizon-Williamson-Ciobotaru, EPRINT'19], a popular state-of-the-art practical zkSNARK, and preserves all its great features --- constant size proofs, constant time proof verification, a circuit-independent universal setup, and support for custom gates and lookup gates. Our techniques are useful for a wide range of applications that involve a circuit executing k steps, where at each step, a (possibly different) s-sized segment is executed from a choice of n segments. Our prover cost for such circuits is O(ks(log (ks) + log(n))). Finally, we show that our improvements are not purely asymptotic. Specifically, we demonstrate the concrete efficiency of SublonK using zkRollups as an example application. Based on our implementation, for parameter choices derived from rollup contracts on Ethereum, n =8, k = 128, s= 2^{16}, the SublonK prover is approximately 4.8x faster than the PlonK prover, and proofs in SublonK are 2.4KB and can be verified in under 50ms.

Multiparty garbling is the most popular approach for constant-round secure multiparty computation (MPC). Despite being the focus of significant research effort, instantiating prior approaches to multiparty garbling results in constant-round MPC that can not realistically accommodate large numbers of parties. In this work we present the first global-scale multiparty garbling protocol. The per-party communication complexity of our protocol decreases as the number of parties participating in the protocol increases - for the first time matching the asymptotic communication complexity of non-constant round MPC protocols. Our protocol achieves malicious security in the honest-majority setting and relies on the hardness of the Learning Party with Noise assumption.

How can a model owner prove they trained their model according to the correct specification? More importantly, how can they do so while preserving the privacy of the underlying dataset and the final model? We study this problem and formulate the notion of zero-knowledge proof of training (zkPoT), which formalizes rigorous security guarantees that should be achieved by a privacy-preserving proof of training. While it is theoretically possible to design zkPoT for any model using generic zero-knowledge proof systems, this approach results in extremely unpractical proof generation times. Towards designing a practical solution, we propose the idea of combining techniques from MPC-in-the-head and zkSNARKs literature to strike an appropriate trade-off between proof size and proof computation time. We instantiate this idea and propose a concretely efficient, novel zkPoT protocol for logistic regression.

Abstract Set membership proofs are an invaluable part of privacy preserving systems. These proofs allow a prover to demonstrate knowledge of a witness w corresponding to a secret element x of a public set, such that they jointly satisfy a given NP relation, i.e. ℛ(w, x) = 1 and x is a member of a public set {x 1, . . . , x𝓁}. This allows the identity of the prover to remain hidden, eg. ring signatures and confidential transactions in cryptocurrencies. In this work, we develop a new technique for efficiently adding logarithmic-sized set membership proofs to any MPC-in-the-head based zero-knowledge protocol (Ishai et al. [STOC’07]). We integrate our technique into an open source implementation of the state-of-the-art, post quantum secure zero-knowledge protocol of Katz et al. [CCS’18].We find that using our techniques to construct ring signatures results in signatures (based only on symmetric key primitives) that are between 5 and 10 times smaller than state-of-the-art techniques based on the same assumptions. We also show that our techniques can be used to efficiently construct post-quantum secure RingCT from only symmetric key primitives.

Byzantine agreement (BA), the task of n parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in BA protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is Õ(1) bits per party, but some parties must send Ω(n) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating Õ(√n).

Breach in password databases has been a frequent phenomena in the software industry. Often these breaches go undetected for years. Sometimes, even the companies involved are not aware of the breach. Even after they are detected, publicizing such attacks might not always be in the best interest of the companies. This calls for a strong breach detection mechanism. Juels et al. (in ACM-CCS 2013) suggest a method called ‘Honeywords’, for detecting password database breaches. Their idea is to generate multiple fake passwords, called honeywords and store them along with the real password. Any login attempt with honeywords is identified as a compromise of the password database, since legitimate users are not expected to know the honeywords corresponding to their passwords. The key components of their idea are (i) generation of honeywords, (ii) typo-safety measures for preventing false alarms, (iii) alarm policy upon detection, and (iv) testing robustness of the system against various attacks. In this work, we analyze the limitations of existing honeyword generation techniques. We propose a new attack model called ‘Multiple System Intersection attack considering Input’. We show that the ‘Paired Distance Protocol’ proposed by Chakraborty et al., is not secure in this attack model. We also propose new and more practical honeyword generation techniques and call them the ‘evolving-password model’, the ‘user-profile model’, and the ‘append-secret model’. These techniques achieve ‘approximate flatness’, implying that the honeywords generated using these techniques are indistinguishable from passwords with high probability. Our proposed techniques overcome most of the risks and limitations associated with existing techniques. We prove flatness of our ‘evolving-password model’ technique through experimental analysis. We provide a comparison of our proposed models with the existing ones under various attack models to justify our claims.