Zero-knowledge proof (ZKP) is a fundamental cryptographic primitive that allows a prover to convince a verifier of the validity of a statement without leaking any further information. As an efficient variant of ZKP, noninteractive zero-knowledge proof (NIZKP) adopting the Fiat-Shamir heuristic is essential to a wide spectrum of applications, such as federated learning, blockchain, and social networks. However, the heuristic is typically built upon the random oracle model that makes ideal assumptions about hash functions, which does not hold in reality and thus undermines the security of the protocol. Here, we present a quantum solution to the problem. Instead of resorting to a random oracle model, we implement a quantum randomness service. This service generates random numbers certified by the loophole-free Bell test and delivers them with postquantum cryptography (PQC) authentication. By employing this service, we conceive and implement NIZKP of the three-coloring problem. By bridging together three prominent research themes, quantum nonlocality, PQC, and ZKP, we anticipate this work to inspire more innovative applications that combine quantum information science and the cryptography field.
Zero-knowledge (ZK) proofs with an optimal memory footprint have attracted a lot of attention, because such protocols can easily prove very large computation with a small memory requirement. Such ZK protocol only needs O(M) memory for both parties, where M is the memory required to verify the statement in the clear. In this paper, we propose several new constant-round ZK protocols in this setting, which improve the concrete efficiency and, at the same time, enable sublinear amortized communication for circuits with some notion of relaxed uniformity. In the circuit-based model, where the computation is represented as a circuit over a field, our ZK protocol achieves a communication complexity of 1 field element per non-linear gate for any field size while keeping the computation very cheap. We implemented our protocol, which shows extremely high efficiency and affordability. Compared to the previous best-known implementation, we achieve 6x--7x improvement in computation and 3x--7x improvement in communication. When running on intro-level AWS instances, our protocol only needs one US dollar to prove one trillion AND gates (or 2.5 US dollars for one trillion multiplication gates over a 61-bit field). In the setting where part of the computation can be represented as a set of polynomials with a "degree-separated" format, we can achieve communication sublinear to the polynomial size: the communication only depends on the total number of distinct variables in all the polynomials and the highest degree of all polynomials, independent of the number of multiplications to compute all polynomials. Using the improved ZK protocol, we can prove matrix multiplication with communication proportional to the input size, rather than the number of multiplications. Proving the multiplication of two 1024 x 1024 matrices, our implementation, with one thread and 1 GB of memory, only needs 10 seconds and communicates 25 MB.
Aiming at the problems of large ciphertext size and low efficiency in the current secure multi-party computation (SMC) protocol based on fully homomorphic encryption (FHE), the paper proves that the fully homomorphic encryption scheme that supports multi-bit encryption proposed by Chen Li et al. satisfies the key homomorphism. Based on this scheme and threshold decryption, a three-round, interactive, leveled, secure multi-party computation protocol under the Common Random String (CRS) model is designed. The protocol is proved to be safe under the semi-honest model and the semi-malicious model. From the non-interactive zero-knowledge proof, it can be concluded that the protocol is also safe under the malicious model. Its security can be attributed to the Decisional Learning With Errors (DLWE) and a variant of this problem (some-are-errorless LWE). Compared with the existing secure multi-party computation protocol based on fully homomorphic encryption under the CRS model, the ciphertext size of this protocol is smaller, the efficiency is higher, the storage overhead is smaller, and the overall performance is better than the existing protocol.
Hongjian Yin, E Chen, Yan Zhu, Chengwei Zhao · 6 authors
In this article, we address the problem of secure sensitive data sharing for the specified recipients in Blockchain Internet of Things (BIoT). To do it, we present a cryptographic solution to meet the requirements of decentralization and convenience through key management and programmable ciphertext. First, we design a new ciphertext-policy decentralized-key attribute-based encryption (CP-DK-ABE) scheme. After the master secret key is shared into all full nodes in the form of threshold secret sharing, a decentralized multiparty computation protocol is used to generate the userâs private key in an interactive way. Meanwhile, the attribute subkeys associated with the private key can be reconstructed by obtaining a fragment from each of full nodes, so as to achieve the cooperative management of attribute key through all of full nodes. Furthermore, following the blockchainâs script system, we introduce five new opcodes to represent ciphertext in the programmable format. Such a mechanism provides flexible capability to represent the logical relationship of the access control policy among attribute subciphers in the CP-DK-ABE ciphertext by the scripting language. As a result, the processes of encryption and decryption are implemented entirely by the script interpreter on the blockchain node, thereby greatly improving the convenience of programming in BIoT devices. In addition, we prove that the proposed CP-DK-ABE scheme is key private and semantically secure for a limited number of corrupted full nodes under the decisional linear and bilinear DiffieâHellman assumption, respectively.
In known constructions of classical zero-knowledge protocols for NP, either of zero-knowledge or soundness holds only against computationally bounded adversaries. Indeed, achieving both statistical zero-knowledge and statistical soundness at the same time with classical verifier is impossible for NP unless the polynomial-time hierarchy collapses, and it is also believed to be impossible even with a quantum verifier. In this work, we introduce a novel compromise, which we call the certified everlasting zero-knowledge proof for QMA. It is a computational zero-knowledge proof for QMA, but the verifier issues a classical certificate that shows that the verifier has deleted its quantum information. If the certificate is valid, even unbounded malicious verifier can no longer learn anything beyond the validity of the statement. We construct a certified everlasting zero-knowledge proof for QMA. For the construction, we introduce a new quantum cryptographic primitive, which we call commitment with statistical binding and certified everlasting hiding, where the hiding property becomes statistical once the receiver has issued a valid certificate that shows that the receiver has deleted the committed information. We construct commitment with statistical binding and certified everlasting hiding from quantum encryption with certified deletion by Broadbent and Islam [TCC 2020] (in a black box way), and then combine it with the quantum sigma-protocol for QMA by Broadbent and Grilo [FOCS 2020] to construct the certified everlasting zero-knowledge proof for QMA. Our constructions are secure in the quantum random oracle model. Commitment with statistical binding and certified everlasting hiding itself is of independent interest, and there will be many other useful applications beyond zero-knowledge.
Quantum communication has shown astonishingly fast development taking the advantage of quantum computation power that is being developed by technology giants like IBM, Google. The security issues and communication gaps caused by these quantum computers must be curled by the quantum computing methods. There are situations where the security of data is of less concern than knowing the fact âwhether the data is tempered or notâ. The Fingerprinting technique provides such knowledge by creating fingerprints of such important data and keeping the record of the temperament of data. Quantum Fingerprinting (QF) follows a procedure of creation of fingerprints of data and uses a referee which tells whether the fingerprint strings match or not. In a dilemmatic situation of fingerprinting, compromising either with security or speed, the paper focuses on achieving the removal of the referee and adding some security. This paper uses the power of Zero-Knowledge Proof (ZKP) to improve security as well as removes the use of referees in QF. The Zero Knowledge Proof is a protocol by which one party can prove to another party that they know the value âXâ, without conveying any information apart from the fact that they are deemed to know âXâ. Thus, embedding the curse of Zero-Knowledge Protocol to quantum fingerprinting gives Quantum Cursed Fingerprinting (QCF) the power of security and removal of the referee to match the fingerprints.
Random algorithms have a unique place in complexity theory as a model of computation that ispotentially more powerful than ânormalâ algorithms, and is also practical. However, it is still notclear how much more power randomness adds. The primary goal in studying random algorithmsis derandomization â some method to simulate random algorithms without actually using random-ness. While full derandomization is quite difficult, we show some weak derandomization results âone using advice, and one using multi-pseudodeterminism. We show that improving these resultswould have major implications. Finally, we show new containments and oracle separations betweentraditional random classes and zero-knowledge proofs.
Ulrich Haböck, Alberto Garoffolo, Daniele Di Benedetto
This document describes Darlin, a succinct zero-knowledge argument of knowledge based on the Marlin SNARK (Chiesa et al., Eurocrypt 2020) and the `dlog' polynomial commitment scheme from Bootle et al. EUROCRYPT 2016. Darlin addresses recursive proofs by integrating the amortization technique from Halo (IACR eprint 2019/099) for the non-succinct parts of the dlog verifier, and we adapt their strategy for bivariate circuit encoding polynomials to aggregate Marlin's inner sumchecks across the nodes the recursive scheme. We estimate the performance impact of inner sumcheck aggregation by about 30% in a tree-like scheme of in-degree 2, and beyond when applied to linear recursion.
This perspectives article surveys the most promising privacy-preserving cryptographic technologies including secure multiparty computation, zero-knowledge proofs and fully homomorphic encryption, and their various real-world applications.
Sri Aravinda Krishnan Thyagarajan, Giulio Malavolta
Payment Channel Networks (PCNs) have given a huge boost to the scalability of blockchain-based cryptocurrencies: Beyond improving the transaction rate, PCNs enabled cheap cross-currency payments and atomic swaps. However, current PCNs proposals either heavily rely on special scripting features of the underlying blockchain (e.g. Hash Time Lock Contracts) or are tailored to a handful of digital signature schemes, such as Schnorr or ECDSA signatures. This leaves us in an unsatisfactory situation where many currencies that are being actively developed and use different signature schemes cannot enjoy the benefits of a PCN.In this work, we investigate whether we can construct PCNs assuming the minimal ability of a blockchain to verify a digital signature, for any signature scheme. In answering this question in the affirmative, we introduce the notion of lockable signatures, which constitutes the cornerstone of our PCN protocols. Our approach is generic and the PCN protocol is compatible with any digital signature scheme, thus inheriting all favorable properties of the underlying scheme that are not offered by Schnorr/ECDSA (e.g. aggregatable signatures or post-quantum security).While the usage of generic cryptographic machinery makes our generic protocol impractical, we view it as an important feasibility result as it may serve as the basis for constructing optimized protocols for specific signature schemes. To substantiate this claim, we design a highly efficient PCN protocol for the special case of Boneh-Lynn-Shacham (BLS) signatures. BLS signatures enjoy many unique features that make it a viable candidate for a blockchain, e.g. short, unique, and aggregatable signatures. Yet, prior to our work, no PCN was known to be compatible with it (without requiring an advanced scripting language). The cost of our PCN is dominated by a handful of calls to the BLS algorithms. Our concrete evaluation of these basic operations shows that users with commodity hardware can process payments with minimal overhead.
Efficient zero-knowledge (ZK) proofs for arbitrary boolean or arithmetic circuits have recently attracted much attention. Existing solutions suffer from either significant prover overhead (i.e., high memory usage) or relatively high communication complexity (at least Îș bits per gate, for computational security parameter Îș). In this paper, we propose a new protocol for constant-round interactive ZK proofs that simultaneously allows for an efficient prover with asymptotically optimal memory usage and significantly lower communication compared to protocols with similar memory efficiency. Specifically:âąThe prover in our ZK protocol has linear running time and, perhaps more importantly, memory usage linear in the memory needed to evaluate the circuit non-cryptographically. This allows our proof system to scale easily to very large circuits.âąfor statistical security parameter Ï = 40, our ZK protocol communicates roughly 9 bits/gate for boolean circuits and 2â4 field elements/gate for arithmetic circuits over large fields.Using 5 threads, 400 MB of memory, and a 200 Mbps network to evaluate a circuit with hundreds of billions of gates, our implementation (Ï = 40, Îș = 128) runs at a rate of 0.45 ÎŒs/gate in the boolean case, and 1.6 ÎŒs/gate for an arithmetic circuit over a 61-bit field.We also present an improved subfield Vector Oblivious Linear Evaluation (sVOLE) protocol with malicious security that is of independent interest.
Without the requirement of trusted third parties (TTPs), Blockchain builds an environment where mutual trust among valid members is established. Nevertheless, the associated transparency property caused a hazard to real-world applications because every on-chain information is exposed to the public. That implies those applications involving sensitive data or personal information, which require security and privacy protection, are not suitable to be implemented in Blockchain, directly. Fully homomorphic encryption (FHE) schemes have been treated as one of the end-to-end solutions to data security and privacy protection problems. In this article, we examine the possibility (or cost) of embedding the ideal lattice-based FHE into the Ethereum Blockchain for building up a new trustworthy framework with security and privacy protection capability. Due to the limitations of current Blockchain, the execution of FHE is conducted off-chain; at the same time, on-chain members can call FHE-based functions to directly compute the ciphertext domain operations after their Smart Contracts have been deployed to the Blockchain. To illustrate and benchmark the examining results of our framework, an FHE and Blockchain-based Vickrey auction system is also developed, in which the online bidding prices are kept in secret. Simultaneously, the determination of the winner and the transferring of payments are conducted autonomously by Smart Contracts.
Non-interactive zero-knowledge (NIZK) proofs for chosen-ciphertext security are generally considered to give an impractical construction. An interesting recent work by Seo, Abdalla, Lee, and Park (Information Sciences, July 2019) proposed an efficient semi-generic conversion method for achieving chosen-ciphertext security based on NIZK proofs in the random oracle model. The recent work by Seo et al. demonstrated that the semi-generic conversion method transforms a one-way (OW)-secure key encapsulation mechanism (KEM) into a chosen-ciphertext secure KEM while preserving tight security reduction. This paper shows that the security analysis of the semi-generic conversion method has a flaw, which comes from the OW security condition of the underlying KEM. Without changing the conversion method, this paper presents a revised security proof under the changed conditions that (1) the underlying KEM must be chosen-plaintext secure in terms of indistinguishability and (2) an NIZK proof derived from the underlying KEM via the FiatâShamir transform must have the properties of zero-knowledge and simulation soundness. This work extended the security proof strategy to the case of identity-based KEM (IBKEM) and also revise the security proof for IBKEM of previous method by Seo et al. Finally, this work gives a corrected security proof by applying the new proofs to several existing (IB)KEMs.
Bitcoin, as the first and the most adopted cryptocurrency, offers many features one of which is contingent payment, that is, the owner of money can programmatically describe the condition upon which his/her money is spent. The condition is determined using a set of instructions written in the Bitcoin scripting language. Unfortunately, this scripting language is not sophisticated enough to create complex conditions or smart contracts in general. Many admirable efforts have been made to build a smart contract infrastructure on top of the Bitcoin platform. In this paper, given the inherent limitations of the Bitcoin scripting language, we critically analyze the practical effectiveness of these methods. Afterwards, we formally define what a smart contract is and introduce seven requirements that if are satisfied, can make creation of smart contracts for Bitcoin possible. Based on the introduced requirements, we examine the ability of the current methods that use secure Multi-party Computation (MPC) to create smart contracts for Bitcoin and show where they fall short. We additionally compare their pros and cons and give clues on how a comprehensive smart contract platform can be possibly built for Bitcoin.
We propose three constructions of classically verifiable non-interactive proofs (CV-NIP) and non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models.
- We construct an information theoretically sound CV-NIP for QMA in the secret parameter model where a trusted party generates a quantum proving key and classical verification key and gives them to the corresponding parties while keeping it secret from the other party. Alternatively, we can think of the protocol as one in a model where the verifier sends an instance-independent quantum message to the prover as preprocessing.
- We construct a CV-NIZK for QMA in the secret parameter model. It is information theoretically sound and zero-knowledge.
- Assuming the quantum hardness of the leaning with errors problem, we construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This model is the same as one considered in the recent work by Coladangelo, Vidick, and Zhang (CRYPTO '20). Our construction has the so-called dual-mode property, which means that there are two computationally indistinguishable modes of generating CRS, and we have information theoretical soundness in one mode and information theoretical zero-knowledge property in the other. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically. To the best of our knowledge, ours is the first dual-mode NIZK for QMA in any kind of model.
We propose three constructions of classically verifiable non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models. - We construct a CV-NIZK for QMA in the quantum secret parameter model where a trusted setup sends a quantum proving key to the prover and a classical verification key to the verifier. It is information theoretically sound and zero-knowledge. - Assuming the quantum hardness of the learning with errors problem, we construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This model is the same as one considered in the recent work by Coladangelo, Vidick, and Zhang (CRYPTO '20). Our construction has the so-called dual-mode property, which means that there are two computationally indistinguishable modes of generating CRS, and we have information theoretical soundness in one mode and information theoretical zero-knowledge property in the other. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically. To the best of our knowledge, ours is the first dual-mode NIZK for QMA in any kind of model. - We construct a CV-NIZK for QMA with quantum preprocessing in the quantum random oracle model. This quantum preprocessing is the one where the verifier sends a random Pauli-basis states to the prover. Our construction uses the Fiat-Shamir transformation. The quantum preprocessing can be replaced with the setup that distributes Bell pairs among the prover and the verifier, and therefore we solve the open problem by Broadbent and Grilo (FOCS '20) about the possibility of NIZK for QMA in the shared Bell pair model via the Fiat-Shamir transformation.
This paper considers the problem of expanding a language class that can be proven by a non-interactive zero-knowledge proof system (NIZK) in a black-box manner in the common reference string model. Namely, given NIZKs for two languages,L0andL1, can we construct an NIZK forL0vL1in a black-box manner? NIZKs for disjunctive languages have a large number of applications, such as electronic voting. Therefore, such a black-box construction may enable the efficient constructions of such applications. However, Abe et al. (PKC 2020) showed that this is impossible if the two given NIZKs are simulation-sound. In this paper, we prove that it is also impossible if the two given NIZKs are constructed by the commit-and-prove methodology that is typically used in many cryptographic protocols, including NIZKs. This result suggests that if we want to augment the capability of NIZKs in terms of the languages they can prove, we should rely on certain properties or structures of the underlying NIZKs, such as algebraic structures.