Zero-knowledge proof is a critical cryptographic primitive. Its most practical type, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK), has been deployed in various privacy-preserving applications such as cryptocurrencies and verifiable machine learning. Unfortunately, zkSNARK like Groth16 has a high overhead on its proof generation step, which consists of several time-consuming operations, including large-scale matrix-vector multiplication (MUL), number-theoretic transform (NTT), and multi-scalar multiplication (MSM). Therefore, this paper presents cuZK, an efficient GPU implementation of zkSNARK with the following three techniques to achieve high performance. First, we propose a new parallel MSM algorithm. This MSM algorithm achieves nearly perfect linear speedup over the Pippenger algorithm, a well-known serial MSM algorithm. Second, we parallelize the MUL operation. Along with our self-designed MSM scheme and well-studied NTT scheme, cuZK achieves the parallelization of all operations in the proof generation step. Third, cuZK reduces the latency overhead caused by CPU-GPU data transfer by 1) reducing redundant data transfer and 2) overlapping data transfer and device computation. The evaluation results show that our MSM module provides over 2.08x (up to 2.94x) speedup versus the state-of-the-art GPU implementation. cuZK achieves over 2.65x (up to 4.86x) speedup on standard benchmarks and 2.18Ă speedup on a GPU-accelerated cryptocurrency application, Filecoin.
Xin Liu, Weitong Chen, Naixue Xiong, Dan Luo · 6 authors
Private set intersection (PSI) is a valuable technique with various practical applications, including secure matching of communication packets in the Internet of Things. However, most of the currently available two-party PSI protocols are based on the oblivious transfer (OT) protocol, which is computationally expensive and results in significant communication overhead. In this paper, we propose a new coding method to design a two-party PSI protocol under the semi-honest model. We analyze possible malicious attacks and then develop a PSI protocol under the malicious model using the Paillier cryptosystem, cut-and-choose, zero-knowledge proof, and other cryptographic tools. By adopting the real/ideal model paradigm, we prove the protocolâs security under the malicious model, which is more efficient compared to the existing related schemes.
Threshold signature can solve the problems of high cost and network congestion during the execution of smart contracts. However, the information transmitted in public links is vulnerable to eavesdropping, tampering and other network attacks, it is essential to ensure the confidentiality and integrity during data transmission. However, traditional threshold signcryption is not suitable for blockchain setting and cannot withstand the quantum computing attacks. In view of these reasons, one lattice-based threshold signcryption for blockchain oracle data transmission (BCODT-LTSC) is devised in this article. BCODT-LTSC satisfies the existential unforgeability, confidentiality and threshold characteristic; it has very low computation cost and is suitable for the application in blockchain scenario.
We describe Shamir's secret sharing scheme and explain how it can be used for secure and redundant cryptocurrency storage. We include samples of individual and group assignments that can be used in an upper-division cryptology class for students who are familiar with modular arithmetic. It takes about one class to cover Shamir's secret sharing, but additional time can be spent on the described coding project about splitting mnemonic Bitcoin seeds into shares. We also provide references for topics of further study that can you use for student research projects.
Ismail Afia, Hisham S. Galal, Riham AlTawy, Amr Youssef
In second-hand vehicle markets, blockchains are being proposed as means to provide verification of vehicle history, a.k.a. vehicle passport (VP). However, given that confidentiality of VPs often contradicts public verification, blockchains are not used to their full potential in the proposed frameworks. Specifically, although blockchain smart contracts offer a decentralized mechanism for untrusted parties to fairly exchange digital assets without the need for a trusted third party, VP exchange is always carried off-chain. In this work, we investigate the problem of âfair exchangeâ of confidential VPs over public blockchains where its plain information must be verified against its publicly committed value. We propose a zero-knowledge proof, called Consistent Commitment Encryption (CCE), that enables the public verification of the consistency between ElGamal encryption of a given VP and its Pedersen commitment. We employ our CCE to build vPass, a decentralized vehicle passport framework that enables second-hand vehicle buyers to purchase vehicle history information from designated service providers and get it verified and delivered on-chain while preserving its confidentiality. The security of CCE relies on the intractability of the discrete logarithm problem in elliptic curve groups and it has no trusted setup. We formally prove that CCE is sound, complete, and witness indistinguishable proof of knowledge, and report on comparisons with other generic proof systems. Moreover, we show that vPass provides fair exchange and confidentiality of the vehicle history, and compare it to existing VP systems. Finally, we provide a proof of concept implementation on Ethereum and report the system performance metrics.
Xin Liu, Xiaomeng Liu, Naixue Xiong, Dan Luo · 6 authors
With the rapid development of cloud computing and other modern technologies, collaborative computing between data is increasing, and privacy protection and secure multi-party computation are also attracting more attention. The emergence of cloud computing provides new options for data holders to perform complex computing problems and to store images; however, data privacy issues cannot be ignored. If a graphic is encrypted and stored in the cloud, the cloud server will perform confidential similar matching when the user searches. At present, most research on searchable encryption is focused on text search, with few schemes researched on how to finish the graphic search. To solve this problem, this paper proposes a secure search protocol based on graph shape under the semi-honest model. Using the cut-choose method and zero-knowledge proof, further designs of the anti-malicious attack graphic similarity judgment system (AAJS) based on the Paillier encryption algorithm, can achieve the secure search and matching of the graph while resisting malicious adversary attacks. The proposed protocolâs security is proved by the real/ideal model paradigm. This paper conducts performance analysis and experimental simulation on the existing scheme and the experiments demonstrate that the system achieves high execution efficiency.
In this paper, we propose a physical protocol to verify the first nonzero term of a sequence using a deck of cards. The protocol lets a prover show the value of the first nonzero term of a given sequence to a verifier without revealing which term it is. Our protocol uses $Î(1)$ shuffles, which is asymptotically lower than that of an existing protocol of Fukusawa and Manabe which uses $Î(n)$ shuffles, where $n$ is the length of the sequence. We also apply our protocol to construct zero-knowledge proof protocols for three well-known logic puzzles: ABC End View, Goishi Hiroi, and Toichika. These protocols enables a prover to physically show that he/she know solutions of the puzzles without revealing them.
Abstract Fair exchange is a challenging problem for two mutually distrusting players. It is widely known that fair exchange is impossible without a trusted third party (TTP). However, relying on a single TTP can cause a single-point failure. An intuitive idea is to adopt multiple TTPs to distribute trust. This paper constructs a two-party optimistic fair exchange (OFE) protocol using decentralized ciphertext-policy attribute-based encryption (CP-ABE), achieving decentralized TTPs. This is achievable because decentralized CP-ABE ciphertext supports a nested access control policy. A nested access control policy fits perfectly in a fair exchange protocol which contains multiple roles (i.e. players and TTPs). Further, we apply non-interactive zero knowledge proofs to prove the well-formedness of ciphertexts, so as to enforce players to follow the protocol specification honestly. Consequently, we construct an OFE protocol in which each playerâs operations are publicly verifiable without revealing secret information. Also, we obtain decentralized TTPs with optimism (i.e. the TTPs are involved only when arbitration is required), autonomy (i.e. the TTPs do not need to interact with each other), statelessness (i.e. the TTPs do not need to store data for the exchange protocol) and verifiability (i.e. the TTPs are publicly verifiable). Compared with previous work, our protocol assumes only a public communication channel and each partyâs operations are publicly verifiable. Besides, it achieves a favorable $O(n)$ verification complexity in the normal case, where $n$ is the number of TTPs. Finally, we present a proof-of-concept implementation to demonstrate the feasibility.
Abstract A â1-out-of-nâ oblivious transfer (OT) protocol involves two participants: a sender, who provides a set of items as input, and a receiver. The protocol guarantees that the receiver gets exactly one of the items of the input set, while the sender is unable to determine which. Priced OT (POT) protocols further allow each item of the input set to be assigned a price in such a way that, after a proper execution of the protocol, the receiver gets the requested item if and only if the corresponding sum of money has been paid. In this paper, we present a construction which takes a â1-out-of-nâ OT protocol and transform it into a POT one. Moreover, the resulting system is unlinkable in the sense that the sender is unable to determine whether two executions of the protocol were run by the same receiver or not. When compared to existing unlinkable POT protocols, our construction offers a lower conceptual complexity as it does not involve the use of zero-knowledge proofs.
In this paper, we propose a practically efficient model for securely computing rank-based statistics, e.g., median, percentiles and quartiles, over distributed datasets in the malicious setting without leaking individual data privacy. Based on the binary search technique of Aggarwal et al. (EUROCRYPT \textquotesingle 04), we respectively present an interactive protocol and a non-interactive protocol, involving at most $\log ||R||$ rounds, where $||R||$ is the range size of the dataset elements. Besides, we introduce a series of optimisation techniques to reduce the round complexity. Our computing model is modular and can be instantiated with either homomorphic encryption or secret-sharing schemes. Compared to the state-of-the-art solutions, it provides stronger security and privacy while maintaining high efficiency and accuracy. Unlike differential-privacy-based solutions, it does not suffer a trade-off between accuracy and privacy. On the other hand, it only involves $O(N \log ||R||)$ time complexity, which is far more efficient than those bitwise-comparison-based solutions with $O(N^2\log ||R||)$ time complexity, where $N$ is the dataset size. Finally, we provide a UC-secure instantiation with the threshold Paillier cryptosystem and $ÎŁ$-protocol zero-knowledge proofs of knowledge.
Abstract Decomposition puzzles are pencil-and-paper logic puzzles that involve partitioning a rectangular grid into several regions to satisfy certain rules. In this paper, we construct a generic card-based protocol called printing protocol , which can be used to physically verify solutions of decompositon puzzles. We apply the printing protocol to develop card-based zero-knowledge proof protocols for two such puzzles: Five Cells and Meadows. These protocols allow a prover to physically show that he/she knows solutions of the puzzles without revealing them.
Graham Cormode, Marcel DallâAgnol, Tom Gur, Christopher W. Hickey
Streaming interactive proofs (SIPs) enable a space-bounded algorithm with one-pass access to a massive stream of data to verify a computation that requires large space, by communicating with a powerful but untrusted prover. This work initiates the study of zero-knowledge proofs for data streams. We define the notion of zero-knowledge in the streaming setting and construct zero-knowledge SIPs for the two main algorithmic building blocks in the streaming interactive proofs literature: the sumcheck and polynomial evaluation protocols. To the best of our knowledge all known streaming interactive proofs are based on either of these tools, and indeed, this allows us to obtain zero-knowledge SIPs for central streaming problems such as index, point and range queries, median, frequency moments, and inner product. Our protocols are efficient in terms of time and space, as well as communication: the verifier algorithm's space complexity is $\mathrm{polylog}(n)$ and, after a non-interactive setup that uses a random string of near-linear length, the remaining parameters are $n^{o(1)}$. En route, we develop an algorithmic toolkit for designing zero-knowledge data stream protocols, consisting of an algebraic streaming commitment protocol and a temporal commitment protocol.Our analyses rely on delicate algebraic and information-theoretic arguments and reductions from average-case communication complexity.
Xin Liu, Xiaofen Tu, Dan Luo, Gang Xu · 6 authors
In recent years, with the development of information security, secure multi-party computation has gradually become a research hotspot in the field of privacy protection. The intersection and union computation of graphs is an important branch of secure computing geometry. At present, the intersection and union of graphs are almost designed under the semi-honest model, and few solutions are proposed under the malicious model. However, the solution under the malicious model is more secure and has important theoretical and practical significance. In this paper, the possible malicious behaviors of computing the intersection and union of graphs are analyzed. Using the Lifted-ElGamal threshold cryptosystem and zero-knowledge proof method, the secure multi-party computation algorithm of graphsâ intersection and union under the malicious model is designed. The real/ideal model paradigm is used to prove the security of the algorithm, the efficiency of the algorithm is analyzed in detail, and the feasibility is verified through experiment.