Folding schemes are an exciting new primitive, transforming the task of performing multiple zero-knowledge proofs of knowledge for a relation into performing just one zero-knowledge proof, for the same relation, and a number of cheap inclusion-proofs. Recently, folding schemes have been used to amortize the cost associated with proving different statements to multiple distinct verifiers, which has various applications. We observe that for these uses, leaking information about the statements folded together can be problematic, yet this happens with previous constructions. Towards resolving this issue, we give a natural definition of privacy preserving folding schemes, and what security they should offer. To construct privacy preserving folding schemes, we first define statement hiders, a primitive which might be of independent interest. In a nutshell, a statement hider hides an instance of a relation as a new instance in the same relation. The new instance is in the relation if and only if the initial instance is. With this building block, we can utilize existing folding schemes to construct a privacy preserving folding scheme, by first hiding each of the statements. Folding schemes allow verifying that a statement was folded into another statement, while statement hiders allow verifying that a statement was hidden as another statement.
Verifiable Delay Functions (VDFs) introduced by Boneh et al. (CRYPTO'18) are functions that require a prescribed number of sequential steps T to evaluate, yet their output can be verified in time much faster than T. Since their introduction, VDFs have gained a lot of attention due to their applications in blockchain protocols, randomness beacons, timestamping and deniability. This thesis explores the theory and applications of VDFs, focusing on enhancing their soundness, efficiency and practicality. The only practical VDFs known to date are based on repeated squaring in hidden order groups. Consider the function VDF(x,T)=x^(2^T). The iterated squaring assumption states that, for a random group element x, the result of VDF cannot be computed significantly faster than performing T sequential squarings if the group order is unknown. To make the result verifiable a prover can compute a proof of exponentiation (PoE) \pi. Given \pi, the output of VDF can be verified in time much less than T. We first present new constructions of statistically sound proofs of exponentiation, which are an important building block in the construction of SNARKs (Succinct Non-Interactive Argument of Knowledge). Statistical soundness means that the proofs remain secure against computationally unbounded adversaries, in particular, it remains secure even when the group order is known. We thereby address limitations in previous PoE protocols which either required (non-standard) hardness assumptions or a lot of parallel repetitions. Our construction significantly reduces the proof size of statistically sound PoEs that allow for a structured exponent, which leads to better efficiency of SNARKs and other applications. Secondly, we introduce improved batching techniques for PoEs, which allow multiple proofs to be aggregated and verified with minimal overhead. These protocols optimize communication and computation complexity in large-scale blockchain environments and enable scalable remote benchmarking of parallel computation resources. We then construct VDFs with enhanced properties such as zero-knowledge and watermarkability. It was shown by Arun, Bonneau and Clark (ASIACRYPT'22) that these features enable new cryptographic primitives called short-lived proofs and signatures. The validity of such proofs and signatures expires after a predefined amount of time T, i.e., they are deniable after time T. Our constructions improve upon the constructions by Arun, Bonneau and Clark in several dimensions (faster forging times, arguably weaker assumptions). Finally, we apply PoEs in the realm of primality testing, providing cryptographically sound proofs of non-primality for large Proth numbers. This work gives a surprising application of VDFs in the area of computational number theory. Together, our contributions advance both the theoretical foundations and the real-world usability of VDFs in general and in particular of PoEs, making them more adaptable and secure for current and emerging cryptographic applications.
The correctness of a computation can be efficiently verified in a privacy-preserving manner without re-execution using zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs). With short transcript sizes and fast verification times, zkSNARKs enable the potential deployment of computationally intensive algorithms—such as machine learning models—on the blockchain, making them efficiently verifiable through short proofs. However, the prover time for matrix computations in these settings often fails to scale efficiently with increasing model complexity and data size. We are the first to systematically address zkSNARKs for general matrix computations with practical prover efficiency. We achieve an $O(N + nM)$ prover time, asymptotically faster than the unverified matrix computation, for computations involving $M$ matrix operations on $n \times n$ matrices with $N$ total non-zero entries. Starting with a single dense matrix multiplication, we propose zkMatrix, a special-purpose zkSNARK for verifying committed $n \times n$ matrix multiplication through their projections onto random vectors. Among zkSNARKs with $O(\log n)$ transcript size and verifier time, zkMatrix is the first to achieve $O(n^2)$ prover time and $O(n^2)$ RAM usage. Batching multiple proofs together reduces the prover time for each additional multiplication to $O(n)$ group operations. Next, we design zkSNARKs for sparse matrix multiplication with $N$ non-zero entries. zkSmart reduces the prover time from $O(n^2)$ to $O(N + n)$, relying on an $O(N + n)$-prover vector-matrix-vector product argument, achieved by improving Bulletproofs. Moreover, \zksmart formulates verifiable computation represented as a matrix circuit of $M$ nodes, each denoting a matrix operation. Sparse matrix multiplication translates the matrix circuit satisfiability (Mat-Circ-SAT) problem into the high-dimensional rank-1 constraint system (HD-R1CS), a matrix-circuit version of the rank-1 constraint system (R1CS), traditionally used for arithmetic circuits. Using zkSmart, we achieve $O(N + nM)$ prover time for general matrix computations. To reduce the cost of committing to intermediate variable matrices in zkSmart, we introduce Evalyn, which generates proofs using a pre-order tree traversal on the abstract syntax tree (AST) of a matrix expression. Evalyn ensures output and input consistency in serial matrix computations by linking randomness for zkSNARKs between parent and child nodes, eliminating the need to commit to the nodes and significantly improving prover efficiency. Our prover for R1CS outperforms state-of-the-art general-purpose zkSNARKs. As a foundational component of our framework, we optimize Bulletproofs to construct the fastest known inner product argument (IPA). Additionally, we propose a zero-knowledge transformation that commits to transcript elements with only logarithmic overhead—while maintaining compatibility with post-quantum secure, non-homomorphic commitment schemes. We apply our framework to zero-knowledge machine learning (zkML), providing zkSNARKs for neural networks. We translate floating-point truncations and non-linear activation functions into linear algebra equations that can be verified by our framework. We utilize our framework to generate efficient proofs for the attention layer in large language models (LLMs). After resolving all these challenges, we have thoroughly addressed the design of efficient zkSNARKs for matrix computations.
As blockchain technology continues to evolve, the pursuit of privacy has become a significant challenge. Although the transparency and immutability of blockchain are essential features, they can unintentionally expose sensitive information. This paper investigates the potential of Zero-Knowledge Proofs (ZKPs) and Secure Multi-Party Computation (SMPC) as innovative solutions to address these privacy concerns. ZKPs facilitate the verification of information without disclosing the underlying data, thereby enhancing privacy in transactions and identity verification processes. Meanwhile, SMPC enables collaborative computations while preserving the confidentiality of inputs, which is vital for industries such as finance and healthcare. Despite their potential, these technologies encounter challenges related to complexity, scalability, and regulatory compliance. This study offers a thorough analysis of ZKPs and SMPC, their applications, and the ethical implications involved, providing valuable insights into their role in creating a secure and privacy-conscious blockchain ecosystem.
With the demand of cryptocurrencies, threshold ECDSA recently regained popularity. So far, several methods have been proposed to construct threshold ECDSA, including the usage of OT and homomorphic encryptions (HE). Due to the mismatch between the plaintext space and the signature space, HE-based threshold ECDSA always requires zero-knowledge range proofs, such as Paillier and Joye-Libert (JL) encryptions. However, the overhead of range proofs constitutes a major portion of the total cost.
The hardness of lattice problems offers one of the most promising security foundations for quantum-safe cryptography. Basic schemes for public key encryption and digital signatures are already close to standardization at NIST and several other standardization bodies, and the research frontier has moved on to building primitives with more advanced privacy features. At the core of many such primitives are zero-knowledge proofs. In recent years, zero-knowledge proofs for (and using) lattice relations have seen a dramatic jump in efficiency and they currently provide arguably the shortest, and most computationally efficient, quantum-safe proofs for many scenarios. The main difficulty in using these proofs by non-experts (and experts!) is that they have a lot of moving parts and a lot of internal parameters depend on the particular instance that one is trying to prove.
Abstract In an Instance-Hiding Interactive Proof (IHIP) (Beaver et al., in: Menezes and Vanstone (eds) Advances in cryptology—CRYPTO 1990, proceedings, lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), Springer, pp 326–338, 1990), an efficient verifier with a private input x interacts with an unbounded prover to determine whether x is contained in a language $$\mathcal {L}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>L</mml:mi> </mml:math> . In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties and may be seen as a generalization of the influential concept of randomized encodings (Ishai and Kushilevitz, in: Proceedings 41st annual symposium on foundations of computer science, pp 294–304, 2000; Applebaum et al., in: 45th annual IEEE symposium on foundations of computer science, pp 166–175, 2004; Agrawal et al., in: Halldórsson, Iwama, Kobayashi, Speckmann (eds) Automata, languages, and programming, Springer, Berlin, Heidelberg, pp 1–13, 2015) and as a counterpart to zero-knowledge proofs (Goldwasser et al., in: Symposium on the theory of computing, 1985). We investigate the properties and power of such instance-hiding proofs and show the following: Any language with an IHIP is contained in $${\mathsf {NP/poly}}\cap {\mathsf {coNP/poly}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>NP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> <mml:mo>∩</mml:mo> <mml:mrow> <mml:mi>coNP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> </mml:mrow> </mml:math> . If an average-case hard language has a constant-round IHIP, then infinitely often non-uniform one-way functions exist. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof. IHIP’s are closed under composition with any efficiently computable function. We further study a stronger version of IHIP (that we call Simulatable IHIP) where the view of the honest prover can be efficiently simulated. For these, we obtain stronger versions of some of the above: Any language with a Simulatable IHIP is contained in $${\textsf{AM}}\cap {\textsf{coAM}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>AM</mml:mi> <mml:mo>∩</mml:mo> <mml:mi>coAM</mml:mi> </mml:mrow> </mml:math> . If a worst-case hard language has a Simulatable IHIP, then explicit uniform one-way functions exist.
Open access
2 source records
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
Janak Dhokrat, Namita Pulgam, Tabassum Maktum, Vanita Mane
In digital landscape of today’s ongoing world, the imperative for enhanced security in cloud-based data processing is paramount. This paper introduces an innovative framework that seamlessly integrates Homomorphic Encryption and Zero-Knowledge Proofs (ZKPs) to bolster data privacy and confidentiality. This paper explores the technical intricacies, real-world applications, and potential implications of this fusion framework. Homomorphic Encryption empowers computations on encrypted data without compromising privacy, while Zero-Knowledge Proofs offer a mechanism to verify computations without exposing sensitive details. The effectiveness and adaptability of the proposed framework is demonstrated through meticulous analysis and practical deployment in safeguarding cloud-based data processing. The proposed framework marks a significant stride towards creating an environment where data security is unequivocally prioritized.
Valeh Farzaliyev, Calvin Pärn, Heleen Saarse, Jan Willemson
Abstract This paper studies several building blocks needed for electronic voting in order to prepare for the post-quantum era. In particular, we present lattice-based constructions for a generic zero-knowledge (ZK) proof of ballot correctness, a ZK proof of ballot correctness applicable for the homomorphic tallying scenario, and a ZK proof to achieve cast-as-intended verification during the vote casting period. We implement and benchmark our ballot correctness proofs, giving concrete estimations comparing the performance of homomorphic tallying and mix-net based e-voting systems in case of our lattice-based constructions.
Attribute-Based Encryption (ABE) is a promising solution for access control in cloud services. However, the heavy decryption overhead hinders its widespread adoption. A general approach to address this issue is to outsource decryption to decryption cloud service(DCS). Existing schemes have utilized various methods to enable users to verify outsourced results; however, they lack an effective mechanism to achieve exemptibility which enables the honest DCS to escape from wrong claims. And it is impractical to assume that the DCS will provide free services. In this paper, we propose a blockchain-based payable outsourced decryption ABE scheme that achieves both verifiability and exemptibility without adding redundant information to ABE ciphertext. We use zero-knowledge proof to verify outsourced results on blockchain and introduce an optional single-round challenge game under optimistic assumption to address the high cost of proof generation. Moreover, our system achieves fairness and decentralized outsourcing to protect the interests of all parties. Finally, we implement and evaluate our scheme on Ethereum to demonstrate its feasibility and efficiency, the gas usage in attribute numbers from 5 to 60 is 11$\times$ to 140$\times$ in the happy case and 4$\times$ to 55$\times$ in the challenge case lower than the scheme of Ge et al. (TDSC'23).
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
We introduce two models of space-bounded quantum interactive proof systems, QIPL and QIP_{U}L. The QIP_{U}L model, a space-bounded variant of quantum interactive proofs (QIP) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, QIPL allows logarithmically many pinching intermediate measurements per verifier action, making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995). We characterize the computational power of QIPL and QIP_{U}L. When the message number m is polynomially bounded, QIP_{U}L ⊊ QIPL unless P = NP: - QIPL^HC, a subclass of QIPL defined by a high-concentration condition on yes instances, exactly characterizes NP. - QIP_{U}L is contained in P and contains SAC¹ ∪ BQL, where SAC¹ denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits. However, this distinction vanishes when m is constant. Our results further indicate that (pinching) intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where BQL = BQ_{U}L. We also introduce space-bounded unitary quantum statistical zero-knowledge (QSZK_{U}L), a specific form of QIP_{U}L proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (QSZK) defined by Watrous (SICOMP 2009). We prove that QSZK_{U}L = BQL, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.
YOSO MPC (Gentry et al., Crypto 2021) is a new MPC framework where each participant can speak at most once. This models an adaptive adversary’s ability to watch the network and corrupt or destroy parties it deems significant based on their communication. By using private channels to anonymous receivers (e.g. by encrypting to a public key whose owner is unknown), the communication complexity of YOSO MPC can scale sublinearly with the total number N of available parties, even when the adversary’s corruption threshold is linear in N (e.g. just under N/2). It was previously an open problem whether YOSO MPC can achieve guaranteed output delivery in a constant number of rounds without relying on trusted setup. In this work, we show that this can indeed be accomplished. We demonstrate three different approaches: the first two (which we call YaOSO and YOSO-GLS) use two and three rounds of communication, respectively. Our third approach (which we call YOSO-LHSS) uses O(d) rounds, where d is the multiplicative depth of the circuit being evaluated; however, it can be used to bootstrap any constant-round YOSO protocol that requires setup, by generating that setup within YOSO-LHSS. Though YOSO-LHSS requires more rounds than our first two approaches, it may be more practical, since the zero knowledge proofs it employs are more efficient to instantiate. As a contribution of independent interest, we introduce a verifiable state propagation UC functionality, which allows parties to send private message which are verifiably derived in the “correct” way (according to the protocol in question) to anonymous receivers. This is a natural functionality to build YOSO protocols on top of.
Zeiger is a pencil puzzle consisting of a rectangular grid, with each cell having an arrow pointing in horizontal or vertical direction. Some cells also contain a positive integer. The objective of this puzzle is to fill a positive integer into every unnumbered cell such that the integer in each cell is equal to the number of different integers in all cells along the direction an arrow in that cell points to. In this paper, we prove that deciding solvability of a given Zeiger puzzle is NP-complete via a reduction from the not-all-equal positive 3SAT (NAE3SAT+) problem. We also construct a card-based physical zero-knowledge proof protocol for Zeiger, which enables a prover to physically show a verifier the existence of the puzzle's solution without revealing it.
Zero-Knowledge Proofs (ZKPs) are cryptographic tools that enables one party, known as the prover, to prove to another party, the verifier, that a certain statement is true without revealing any information beyond the validity of the statement itself. We introduce the Neutrosophic One-Round Zero-Knowledge Proof protocol (N-1-R) ZKP, which is an extension of the One-Round (1-R) ZKP in the realm of Neutrosophic numbers. The N-1-R ZKP is the first Neutrosophic ZK protocol.
Abstract Sumplete is a logic puzzle generated by ChatGPT in March 2023. The puzzle consists of a rectangular grid, with each cell containing an integer. Each row and column also has an integer called target value assigned to it. The objective of this puzzle is to cross out some numbers in the grid such that the sum of uncrossed numbers in each row and column is equal to the corresponding target value. In this paper, we prove that Sumplete is NP-complete. We also propose a physical zero-knowledge proof protocol for the puzzle using physical cards.
Abstract A zero-knowledge proof is a cryptographic primitive that enables a prover to convince a verifier the validity of a mathematical statement (an NP statement) without revealing any secret inputs to the verifier. A special case, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK) is particularly designed for arithmetic circuit proof systems which have important applications in blockchain privacy. The major computations in this type of zkSNARK proofs with post-quantum security are polynomial evaluations and Lagrange interpolations over finite fields. Given a sequence over a finite field, in the field of coding and sequences research, we understand that there are two representations of the sequence, one is a univariate polynomial and the other, a multivariate polynomial. This is exactly what is done in those zero-knowledge proof systems to transform the proof of a R1CS relation to evaluate uni/multi variate polynomials at some random points in the finite field. In this paper, we present a comparative analysis on how to convert a rank 1 constrained satisfiability (R1CS) system (more general than a circuit system) into a polynomial equality and provide analysis on the concrete complexities of provers, proof sizes and verifiers. We use two concrete zkSNARK schemes, i.e., Polaris, univariate polynomial encodings and Spartan, multivariate polynomial encodings, as examples to show our analysis. Secondly, we propose to select interpolating sets as subfields instead of affine spaces of a large field for Lagrange interpolation. This new method has improved the performance of R1CS encodings largely. We comment that post-quantum secure zkSNARKs yield post-quantum digital signatures with security only depending on symmetric-key schemes. Some open problems are proposed at the end of the paper.
Instant Runoff Voting (IRV) is one example of ranked-choice voting. It provides many known benefits when used in elections, such as minimising vote splitting, ensuring few votes are wasted, and providing resistance to strategic voting. However, the voting and tallying procedures for IRV are much more complicated than those of plurality and are both error-prone and tedious. Many automated systems have been proposed to simplify these procedures in IRV. Some of these also employ cryptographic techniques to protect the secrecy of ballots and enable verification of the tally. Nearly all of these cryptographic systems require a set of trustworthy tallying authorities (TAs) to perform the decryption of votes and/or running of mix servers, which adds significant complexity to the implementation and election management. We address this issue by proposing Camel: an E2E verifiable solution for IRV that requires no TAs. Camel employs a novel representation and a universally verifiable shifting procedure for ballots that facilitate the elimination of candidates as required in an IRV election. We combine these with a homomorphic encryption scheme and zero-knowledge proofs to protect the secrecy of the ballots and enable any party to verify the well-formedness of the ballots and the correctness of the tally in an IRV election. We examine the security of Camel and prove it maintains ballot secrecy by limiting the learned information (namely the tally) against a set of colluding voters.
The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge (CZK) proofs for all languages in NP. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of zero knowledge. Specifically, we prove that the following are equivalent: - A one-way function exists. - NP ⊆ CZK and NP is hard in the worst case. - CZK is hard in the worst case and the problem GapMCSP of approximating circuit complexity is in CZK. The characterization above also holds for statistical and computational zero-knowledge argument systems. We further extend this characterization to a proof system with knowledge complexity O(logn). In particular, we show that the existence of a one-way function is characterized by the worst-case hardness of CZK if GapMCSP has a proof system with knowledge complexity O(logn). We complement this result by showing that NP admits an interactive proof system with knowledge complexity ω(logn) under the existence of an exponentially hard auxiliary-input one-way function (which is a weaker primitive than an exponentially hard one-way function). We also characterize the existence of a robustly-often nonuniformly computable one-way function by the nondeterministic hardness of CZK under the weak assumption that PSPACE ⊈AM. We present two applications of our results. First, we simplify the proof of the recent characterization of a one-way function by NP-hardness of a meta-computational problem and the worst-case hardness of NP given by Hirahara (STOC’23). Second, we show that if NP has a laconic zero-knowledge argument system, then there exists a public-key encryption scheme whose security can be based on the worst-case hardness of NP. This improves previous results which assume the existence of an indistinguishable obfuscation.
Nir Bitansky, Chethan Kamath, Omer Paneth, Ron D. Rothblum · 5 authors
Batch proofs are proof systems that convince a verifier that x1,…,xt ∈ L, for some NP language L, with communication that is much shorter than sending the t witnesses. In the case of statistical soundness (where the cheating prover is unbounded but the honest prover is efficient given the witnesses), interactive batch proofs are known for UP, the class of unique-witness NP languages. In the case of computational soundness (where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of NP, assuming standard lattice or group assumptions. We exhibit the first negative results regarding the existence of batch proofs and arguments: - Statistically sound batch proofs for L imply that L has a statistically witness indistinguishable (SWI) proof, with inverse polynomial SWI error, and a non-uniform honest prover. The implication is unconditional for obtaining honest-verifier SWI or for obtaining full-fledged SWI from public-coin protocols, whereas for private-coin protocols full-fledged SWI is obtained assuming one-way functions. This poses a barrier for achieving batch proofs beyond UP (where witness indistinguishability is trivial). In particular, assuming that NP does not have SWI proofs, batch proofs for all of NP do not exist. - Computationally sound batch proofs (a.k.a batch arguments or BARGs) for NP, together with one-way functions, imply statistical zero-knowledge (SZK) arguments for NP with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive BARGs from one-way functions would yield constant-round SZK arguments from one-way functions. This would be surprising as SZK arguments are currently only known assuming constant-round statistically-hiding commitments. We further prove new positive implications of non-interactive batch arguments to non-interactive zero knowledge arguments (with explicit uniform prover and verifier): - Non-interactive BARGs for NP, together with one-way functions, imply non-interactive computational zero-knowledge arguments for NP. Assuming also dual-mode commitments, the zero knowledge can be made statistical. Both our negative and positive results stem from a new framework showing how to transform a batch protocol for a language L into an SWI protocol for L.
We put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption (with subexponential modulus to noise ratio). We provide a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A notable feature of our construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions, we do not rely on a correlation intractability argument nor do we utilize fully homomorphic encryption techniques. Our solution provides a new methodology that adds to the diversity of techniques for solving this fundamental problem.
In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not secure under concurrent composition, and/or (c) utilize non-standard assumptions of different types in their proofs of security. In this paper, we describe a simple three-round multiparty protocol for Schnorr signatures that is secure for any number of corrupted parties; i.e., in the setting of a dishonest majority. The protocol is fully simulatable, secure under concurrent composition, and proven secure in the standard model or random-oracle model (depending on the instantiations of the commitment and zero-knowledge primitives). The protocol realizes an ideal Schnorr signing functionality with perfect security in the ideal commitment and zero-knowledge hybrid model (and thus the only assumptions needed are for realizing these functionalities). In our presentation, we do not assume that all parties begin with the message to be signed, the identities of the participating parties and a unique common session identifier, since this is often not the case in practice. Rather, the parties achieve consensus on these parameters as the protocol progresses.
The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.
Xi Lin, Heyang Cao, Feng-Hao Liu, Zhedong Wang · 5 authors
Abstract Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation and anonymous payment protocol. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. To tackle this issue, this work seeks to enhance the efficiency and compactness of lattice-based zk-SNARKs, including proof length and common reference string (CRS) length. In this paper, we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings. Compared with previous works, our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes. Particularly, the proof length of our scheme is around $$23.3\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>23.3</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al. (in: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212–234, 2021), and the CRS length is $$3.6\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3.6</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> smaller. Our constructions follow the framework of Gennaro et al. (in: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556–573, 2018), and adapt it to the ring setting by slightly modifying the knowledge assumptions. We develop concretely small constructions by using module-switching and key-switching procedures in a novel way.