International Association
for Cryptologic Research

Collaborative zkSNARKs (Ozdemir and Boneh, USENIX'22) are a multiparty variant of zkSNARKs where multiple provers, each holding a private witness, jointly compute a zkSNARK for their combined witness. A sequence of works has proposed efficient constructions of collaborative zkSNARKs. All of them follow a common design template to emulate a zkSNARK prover in the distributed setting: (i) First, using a generic MPC, the parties jointly compute secret shares of an "extended" prover witness. (ii) Next, given these shares, the parties jointly compute a zkSNARK proof. The latter step involves designing custom semi-honest MPC protocols that avoid non-black-box use of cryptography. To achieve malicious security, prior works adopt state-of-the-art compilers from the MPC literature to transform semi-honest MPC into malicious-secure MPC. In this work, we revisit this design template. - Pitfalls: We demonstrate two pitfalls in the template, which can lead to loss of input privacy. We show that it is possible to compute collaborative proofs on invalid extended witnesses, which in turn can leak the witnesses of honest provers. We also show that using existing malicious security compilers as-is for proof computation is insecure in general. Finally, we discuss mitigation strategies. -Malicious Security for Free: Surprisingly, we show that in the honest-majority setting, given (honestly generated) shares of the extended witness, a semi-honest MPC suffices for collaborative proof generation of several widely used zkSNARKs, even in the presence of a malicious adversary. In other words, we can avoid the overheads of malicious security compilers, enabling faster proof generation. To the best of our knowledge, this presents the first examples of non-trivial computations for which semi-honest MPC protocols achieve malicious security.

Is it possible to prove the deletion of a computer program after having executed it? While this task is clearly impossible using classical information alone, the laws of quantum mechanics may admit a solution to this problem. In this work, we propose a new approach to answer this question, using quantum information. In the interactive settings, we present the first fully-secure solution for blind delegation with certified deletion, assuming post-quantum hardness of the learning with errors (LWE) problem. In the non-interactive settings, we propose a construction of obfuscation with certified deletion, assuming post-quantum iO and one-way functions. Our main technical contribution is a new deletion theorem for subspace coset states [Vidick and Zhang, EUROCRYPT'21, Coladangelo et al., CRYPTO'21], which enables a generic compiler that adds the certified deletion guarantee to a variety of cryptographic primitives. In addition to our main result, this allows us to obtain a host of new primitives, such as functional encryption with certified deletion and secure software leasing for an interesting class of programs. In fact, we are able for the first time to achieve a stronger notion of secure software leasing, where even a dishonest evaluator cannot evaluate the program after returning it.

Zhandry recently defined a new cryptographic object called quantum lightning, which has a number of useful applications, including a strong form of quantum money. Further, they proposed a construction of quantum lightning based on superpositions of low-rank matrices. The scheme is unusual, so it is difficult to base the scheme's security on any widespread computational assumptions. So instead, they proposed a new hardness assumption that, if true, could be used to prove security. In this work, we show that the hardness assumption is in fact false, so the proof of security does not hold. However, we note that the proposal for quantum lightning has not been proven insecure. This work is the first step in analyzing the security of Zhandry's proposal and moving toward a scheme that we can prove to be secure.

The construction of public key quantum money based on standard cryptographic assumptions is a longstanding open question. Here we introduce franchised quantum money, an alternative form of quantum money that is easier to construct. Franchised quantum money retains the features of a useful quantum money scheme, namely unforgeability and local verification: anyone can verify banknotes without communicating with the bank. In franchised quantum money, every user gets a unique secret verification key, and the scheme is secure against counterfeiting and sabotage, a new security notion that appears in the franchised model. Finally, we construct franchised quantum money and prove security assuming one-way functions.