We initiate the study of non-interactive zero-knowledge (NIZK) arguments for languages in QMA. Our first main result is the following: if Learning With Errors (LWE) is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instance-independent) quantum message from verifier to prover. The instance-dependent phase of our argument system involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our non-interactive argument system satisfies the definition of an AoQK. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover which is successful in our protocol. Finally, we show that any language in QMA has an (interactive) proof of quantum knowledge.
We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is locally consistent with all of the k-qubit local density matrices. The containment of this problem in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of OMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of a good witness can be computed in polynomial time, independently of the witness. Within this framework, we show several advances in zero-knowledge in the quantum setting. We show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a “sigma” protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameter setting.11The full version of this work can be found in https://arxiv.org/abs/1911.07782.
We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. First, we answer a longstanding open question by showing that the Consistency of Local Density Matrices problem is QMA-complete under Karp reductions. We also show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA as a quantum analogue of a sigma protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameters setting.
Our main technique consists in developing locally simulatable proofs for all of QMA: this is an encoding of a QMA witness such that it can be efficiently verified by probing only five qubits and, furthermore, the reduced density matrix of any five-qubit subsystem can be computed in polynomial time and is independent of the witness. This construction follows the techniques of Grilo, Slofstra, and Yuen [FOCS 2019].
We present a new 4-move special honest-verifier zero-knowledge proof of knowledge system for proving that a vector of Pedersen commitments opens to a so-called "one-hot'' vector (i.e., to a vector from the standard orthonormal basis) from Zpn. The need for such proofs arises in the contexts of symmetric private information retrieval (SPIR), end-to-end verifiable voting (E2E), and privacy-preserving data aggregation and analytics, among others. The key insight underlying the new protocol is a simple observation regarding the paucity of roots of polynomials of bounded degree over a finite field. The new protocol is fast and yields succinct proofs: For vectors of length n, the prover evaluates Θ(Θlgn) group operations plus Θ(n) field operations and sends just Θ(Θlgn) group and field elements, while the verifier evaluates one n-base multiexponentiation plus Θ(łlgn) additional group operations and sends just 2(λ+lgn) bits to obtain a soundness error less than 2-λ. (A 5-move variant of the protocol reduces prover upload to just λlgn bits for the same soundness error.) We have implemented both our new protocol and its closest competitors from the literature; in accordance with our analytic results, experiments confirm that the new protocols handily outperform existing protocols for all but the shortest of vectors (roughly, for vectors with more than 16-32 elements).
We present a new efficient two-party secure computation protocol which allows the honest party to catch dishonest behavior (if any) with a publicly-verifiable, non-repudiable proof without sacrificing the honest party's secret. Comparing to the best existing protocol of its kind, ours requires a substantially simpler judge algorithm and is able to process circuit evaluator's input-wires two orders of magnitude faster. Further, we propose an automated, decentralized judge implemented as a blockchain smart-contract. As a killer application of combining our two-party PVC protocol with our decentralized judge, we proposed the concept of financially-secure computation, which can be useful in many practical scenarios where it suffices to consider rational adversaries. We experimentally evaluated our prototype implementation, demonstrated the 2PC protocol is highly efficient and the judge is very affordable to protect users against rational attackers.
Russell W. F. Lai, Giulio Malavolta, Viktoria Ronge
In their celebrated work, Groth and Sahai [EUROCRYPT'08, SICOMP' 12] constructed non-interactive zero-knowledge (NIZK) proofs for general bilinear group arithmetic relations, which spawned the entire subfield of structure-preserving cryptography. This branch of the theory of cryptography focuses on modular design of advanced cryptographic primitives. Although the proof systems of Groth and Sahai are a powerful toolkit, their efficiency hits a barrier when the size of the witness is large, as the proof size is linear in that of the witness. In this work, we revisit the problem of proving knowledge of general bilinear group arithmetic relations in zero-knowledge. Specifically, we construct a succinct zero-knowledge argument for such relations, where the communication complexity is logarithmic in the integer and source group components of the witness. Our argument has public-coin setup and verifier and can therefore be turned non-interactive using the Fiat-Shamir transformation in the random oracle model. For the special case of non-bilinear group arithmetic relations with only integer unknowns, our system can be instantiated in non-bilinear groups. In many applications, our argument system can serve as a drop-in replacement of Groth-Sahai proofs, turning existing advanced primitives in the vast literature of structure-preserving cryptography into practically efficient systems with short proofs.
Zero-knowledge arguments have become practical, and widely used, especially in the world of Blockchain, for example in Zcash. This work revisits zero-knowledge proofs in the discrete logarithm setting. First, we identify and carve out basic techniques (partly being used implicitly before) to optimise proofs in this setting. In particular, the linear combination of protocols is a useful tool to obtain zero-knowledge and/or reduce communication. With these techniques, we are able to devise zero-knowledge variants of the logarithmic communication arguments by Bootle et al. (EUROCRYPT '16) and Bünz et al. (S&P '18) thereby introducing almost no overhead. We then construct a conceptually simple commit-and-prove argument for satisfiability of a set of quadratic equations. Unlike previous work, we are not restricted to rank 1 constraint systems (R1CS). This is, to the best of our knowledge, the first work demonstrating that general quadratic constraints, not just R1CS, are a natural relation in the dlog (or ideal linear commitment) setting. This enables new possibilities for optimisation, as, eg., any degree n2 polynomial f(X) can now be "evaluated" with at most 2n quadratic constraints. Our protocols are modular. We easily construct an efficient, logarithmic size shuffle proof, which can be used in electronic voting. Additionally, we take a closer look at quantitative security measures, eg. the efficiency of an extractor. We formalise short-circuit extraction, which allows us to give tighter bounds on the efficiency of an extractor.
Blockchains are established as the most widely used P2P distributed application for Distributed Ledger Technologies. Nevertheless, their successful existence, especially known due to the cryptocurrency of Bitcoin, gets more and more competitors. One of those competitors is IOTA, which is based on a tangle or a Directed Acyclic Graph architecture. This paper stresses potentials of such architecture,especially in future IoT applications. In particular, few of the most import security issues are analyzed.
In recent years, multi-party computation (MPC) frameworks based on replicated secret sharing schemes (RSSS) have attracted the attention as a method to achieve high efficiency among known MPCs. However, the RSSS-based MPCs are still inefficient for several heavy computations like algebraic operations, as they require a large amount and number of communication proportional to the number of multiplications in the operations (which is not the case with other secret sharing-based MPCs). In this paper, we propose RSSS-based three-party computation protocols for modular exponentiation, which is one of the most popular algebraic operations, on the case where the base is public and the exponent is private. Our proposed schemes are simple and efficient in both of the asymptotic and practical sense. On the asymptotic efficiency, the proposed schemes require O(n)-bit communication and O(1) rounds,where n is the secret-value size, in the best setting, whereas the previous scheme requires O(n2)-bit communication and O(n) rounds. On the practical efficiency, we show the performance of our protocol by experiments on the scenario for distributed signatures, which is useful for secure key management on the distributed environment (e.g., distributed ledgers). As one of the cases, our implementation performs a modular exponentiation on a 3,072-bit discrete-log group and 256-bit exponent with roughly 300ms, which is an acceptable parameter for 128-bit security, even in the WAN setting.
This paper introduces a new capability for group signatures called message-dependent opening . It is intended to weaken the high trust placed on the opener; i.e., no anonymity against the opener is provided by an ordinary group signature scheme. In a group signature scheme with message-dependent opening (GS-MDO), in addition to the opener, we set up an admitter that is not able to extract any user’s identity but admits the opener to open signatures by specifying messages where signatures on the specified messages will be opened by the opener. The opener cannot extract the signer’s identity from any signature whose corresponding message is not specified by the admitter. This paper presents formal definitions of GS-MDO and proposes a generic construction of it from identity-based encryption and adaptive non-interactive zero-knowledge proofs. Moreover, we propose two specific constructions, one in the standard model and one in the random oracle model. Our scheme in the standard model is an instantiation of our generic construction but the message-dependent opening property is bounded. In contrast, our scheme in the random oracle model is not a direct instantiation of our generic construction but is optimized to increase efficiency and achieves the unbounded message-dependent opening property. Furthermore, we also demonstrate that GS-MDO implies identity-based encryption, thus implying that identity-based encryption is essential for designing GS-MDO schemes.
Recent advances in the cryptographic field of "Zero-Knowledge Proofs" have sparked a new wave of research, giving birth to many exciting theoretical approaches in the last few years. Such research has often overlapped with the need for private and scalable solutions of Blockchain-based communities, resulting in the first practical implementations of such systems. Many of these innovative constructions have developed in parallel, using different terminologies and evolving into a fragmented ecosystem, calling for their consolidation into the more stable domain of "Verifiable Computation". In this master thesis I propose a unifying Verifiable Computation model for the simplification and efficient comparison of all cryptographic proof systems. I take advantage of this model to analyse innovative technologies (Homomorphic Authenticators, Verifiable Delay Functions) which developed into their own specialised domains, and I attempt to make them more accessible for newcomers to the field. Furthermore, I expand on the future of Verifiable Computation, Universal proof compilers and "Proofs of All", by approaching the state-of-the-art zk-STARK construction from a more accessible and informal design perspective.
A multi signature scheme allows a group of signers to produce a joint signature on a common message, which is more compact than a collection of distinct signatures from all signers. Given this signature and the list of signers' public keys, a verifier is able to check if every signer in the group participated in signing. Recently, a multisignature scheme with public key aggregation has drawn a lot of attention due to their applications into the blockchain technology. Such multisignatures provide not only a compact signature, but also a compact aggregated public key, that is both the signature size and the public key size used to verify the correctness of the signature are independent from the number of signers. This is useful for a blockchain because of its duplication over a distributed network, and thus it is required to be as compact as possible. In this paper, we introduce a new multisignature scheme with such a feature. Our scheme is proven secure under the Decisional Diffie-Hellman assumption. In addition, in the presence of rogue key attacks, the security of our scheme is proven in the plain public key model.
We study the relationship between problems solvable by quantum algorithms in polynomial time and those for which zero-knowledge proofs exist. In prior work, Aaronson [arxiv:quant-ph/0111102] showed an oracle separation between BQP and SZK, i.e. an oracle $A$ such that $\mathrm{SZK}^A \not\subseteq \mathrm{BQP}^A$. In this paper we give a simple extension of Aaronson's result to non-interactive zero-knowledge proofs with perfect security. This class, NIPZK, is the most restrictive zero-knowledge class. We show that even for this class we can construct an $A$ with $\mathrm{NIPZK}^A \not\subseteq \mathrm{BQP}^A$.
We study the relationship between problems solvable by quantum algorithms in\npolynomial time and those for which zero-knowledge proofs exist. In prior work,\nAaronson [arxiv:quant-ph/0111102] showed an oracle separation between BQP and\nSZK, i.e. an oracle $A$ such that $\\mathrm{SZK}^A \\not\\subseteq\n\\mathrm{BQP}^A$. In this paper we give a simple extension of Aaronson's result\nto non-interactive zero-knowledge proofs with perfect security. This class,\nNIPZK, is the most restrictive zero-knowledge class. We show that even for this\nclass we can construct an $A$ with $\\mathrm{NIPZK}^A \\not\\subseteq\n\\mathrm{BQP}^A$.\n
A zero-knowledge proof is a fundamental cryptographic primitive that enables the verification of statements without revealing unnecessary information. Zero-knowledge proofs are a key component of many cryptographic protocols and, often, one of their main efficiency bottlenecks. In recent years there have been great advances in improving the efficiency of zero-knowledge proofs, bring them closer to wide deployability. In this thesis we make another step towards the construction of computationally-efficient zero-knowledge proofs. Specifically, we construct efficient zero-knowledge proofs for the satisfiability of arithmetic circuits for which the computational cost of the prover is only a constant factor more expensive than direct evaluation of the circuit. We also construct efficient zero-knowledge proofs to check the correct execution of (Tiny)RAM programs. In this case the computational cost for the prover is a superconstant factor larger than executing the program directly. Our proofs also support efficient verification and small proof sizes. For security, they rely on symmetric primitives and could potentially withstand attacks from quantum computers. On a different research direction, we look at group signatures, a fundamental primitive which relies on zero-knowledge proofs. A group signature enables users to sign anonymously on behalf of a group of users. In case of dispute a Manager can identify the author of a signature and potentially banish the user from the group. In this thesis we address the fundamental question of defining the security of fully dynamic group signatures, for which the users can join and leave at any time. Differently from other restricted settings, this case has been largely overlooked in the past. Our security model is general, does not implicitly assume existing design paradigms and captures the security of existing models for more restricted settings.
In this paper, we premeditate the problem of designing a model of information propagation with solving the bifurcation problem of the blockchain system. We define a new diffusion mode with spreading information through the designated seed nodes in the network for the whole system which selects the nodes based on a specific problem. Therefore, we derive a novel influence time minimization (ITM) problem which is that how to choose a group of seed nodes as the source of information dissemination process so that the time required for the entire network to be infected is the smallest. We prove that the problem is NP-hard. A greedy-based algorithm is also proposed. We further propose a provable approximation guarantee for the solution of the algorithm based on the analysis of the monotone submodular function. Experiment results show that the new propagation mode can significantly reduce the propagation time in Bitcoin network compared with the traditional method, which further illustrate that greedy-based algorithm can provide a solution with better performance for ITM problem. Moreover, we find the new program has certain practical significance for improving not only the speed of information propagation but operating efficiency of Bitcoin network.
Jack Doerner, Yashvanth Kondi, Eysa Lee, Abhi Shelat
Cryptocurrency applications have spurred a resurgence of interest in the computation of ECDSA signatures using threshold protocols---that is, protocols in which the signing key is secret-shared among n parties, of which any subset of size t must interact in order to compute a signature. Among the resulting works to date, that of Doerner et al. requires the most natural assumptions while also achieving the best practical signing speed. It is, however, limited to the setting in which the threshold is two. We propose an extension of their scheme to arbitrary thresholds, and prove it secure against a malicious adversary corrupting up to one party less than the threshold under only the Computational Diffie-Hellman assumption in the Random Oracle model, an assumption strictly weaker than those under which ECDSA is proven. Whereas the best current schemes for threshold-two ECDSA signing use a Diffie-Hellman Key Exchange to calculate each signature's nonce, a direct adaptation of this technique to a larger threshold t would incur a round count linear in t; thus we abandon it in favor of a new mechanism that yields a protocol requiring log(t)+6 rounds in total. We design a new consistency check, similar in spirit to that of Doerner et al., but suitable for an arbitrary number of participants, and we optimize the underlying two-party multiplication protocol on which our scheme is based, reducing its concrete communication and computation costs. We implement our scheme and evaluate it among groups of up to 256 of co-located and 128 geographically-distributed parties, and among small groups of embedded devices. We find that in the LAN setting, our scheme outperforms all prior works by orders of magnitude, and that it is efficient enough for use even on smartphones or hardware tokens. In the WAN setting we find that, despite its logarithmic round count, our protocol outperforms the best constant-round protocols in realistic scenarios.
The development of quantum computers has urged the cryptographic community to prepare cryptographic primitives for the eventual arrival of the post‐quantum world. To this end, the authors study the witness indistinguishability (WI) and witness hiding (WH) of proof systems against quantum adversaries. They give formal definitions of quantum WI (QWI) and quantum WH (QWH), present proof systems satisfying these definitions, and specify a condition under which QWI implies QWH. Regarding the non‐interactive proof systems, they prove that, even if a common reference string is used to generate polynomially many non‐interactive proofs, the QWI is still preserved, while quantum zero‐knowledge has no such beneficial property. To show the strength of QWI, they present two applications of them. First, they prove that the construction proposed by Feige et al . that transforms any non‐interactive bounded zero‐knowledge proof system to a general one is also feasible against quantum adversaries. Second, they construct a quantum‐secure signature scheme in the CRS model, which is existentially unforgeable against quantum adversaries and remains secure even if a common random string is used to sign polynomially many messages.
S. Sharmila Deva Selvi, Arinjita Paul, C. Pandu Rangan, Siva Dirisala · 5 authors
The blockchain technology and a vast amount of cryptocurrency related activities have generated an unprecedented level of interest among the public. However, even at the entry level, cryptocurrency users need to deal with the complex task of key management. In this paper, we propose a simple way to manage a user's private key, under a reasonable assumption that the user has two devices at his disposal (say a laptop and a mobile phone). We refer to our strategy as key splitting. Since these cryptographic keys are used for generating digital signatures, we should take a closer look at the signature schemes that would perform best under key splitting. At the operational level, scalability is one of the main challenges faced by the users and developers. While there are fundamental issues like consensus that challenge scalability, we focus on the computational efficiency in a block formation. Aggregation of signatures is one of the effective solutions to this problem. To this end, we observe that none of the existing signature schemes work well for BOTH key splitting and aggregation. The current popular schemes such as the ones used in Bitcoin or Schnorr's scheme implemented over Elliptic curves are neither suitable for aggregation nor can their keys be split in a convenient and meaningful way. A detailed theoretical and empirical analysis shows that the BLS short signature scheme is best suited for achieving both key splitting and aggregation.
Eli Ben‐Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space U is δ-far in relative Hamming distance from a linear code V - this is the worst-case assumption - then most elements of U are almost-δ-far from V - this is the average case. However, this result was known to hold only below the "double Johnson" function of the relative distance δ_V of the code V, i.e., only when δ < 1-(1-δ_V)^(1/4). First, we increase the soundness-bound to the "one-and-a-half Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worst-case distance δ smaller than 1-(1-δ_V)^(1/3). This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes. To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point z outside the box D on which codewords are evaluated, and asks the prover for the value at z of the interpolating polynomial of a random element of U. Intuitively, the answer provided by the prover "forces" it to choose one codeword from a list of "pretenders" that are close to U. We call this technique Domain Extending for Eliminating Pretenders (DEEP). The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately δ for all δ < 1-(1-δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from V is approximately δ for all δ. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes. Finally, we use the DEEP technique to devise two new protocols: - An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. The soundness of the protocol improves upon that of the FRI protocol of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. - An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant < 1/8 to a constant arbitrarily close to 1.
Zero-knowledge proofs is a type of non-black box security technique and it is stated by the means of quadratic residuosity problem in this paper. We have used quadratic residuosity problem (QRP) for zero-knowledge proofs security system for the comparative analysis of this technique in comparison with discrete logarithm problem in cryptography. The upper bound of QRP with a prime modulus algorithm for quadratic residuosity problem is growing faster in comparison with discrete logarithm problem used by Henry. After that covariance between two different algorithms for different problems are calculated and obtained result is positive, which means random variables used for both functions are growing in same direction which reflect the fact, they are similar in behavior. Both functions are growing in same direction and our functional valued curve converge with Henry (Discrete Logarithm) functional valued curve at a point.