Privacy is a huge concern for cryptocurrencies and blockchains as most of these systems log everything in the clear. This has resulted in several academic and industrial initiatives to address privacy. Starting with the UTXO model of Bitcoin, initial works brought confidentiality and anonymity to payments. Recent works have expanded to support more generalized forms of private computation. Such solutions tend to be highly involved as they rely on advanced cryptographic primitives and creative techniques to handle issues related to dealing with private records (e.g. concurrency and double spending). This situation makes it hard to comprehend the current state-of-the-art, much less build on top of it. To address these challenges, we develop a systematization of knowledge for privacy-preserving solutions in blockchain. To the best of our knowledge, our work is the first of its kind. After motivating design challenges, we devise two systematization frameworks-the first as a stepping stone to the second- and use them to study the state-of-the-art. For our first framework, we study the zero-knowledge proof systems used in surveyed solutions, based on their key features and limitations. Our second is for privacy-preserving solutions; we define several dimensions to categorize the surveyed schemes and, in doing so, identify two major paradigms employed to achieve private computation. We go on to provide insights to guide solutions' adoption and development. Finally, we touch upon challenges related to limited functionality and accommodating new developments.
This dissertation is composed of two main research projects. The first, which was conducted with my adviser Xiaoming Song as a continuation of her work with with her previous student Nathan Anderson-Stahl. In that chapter, we consider a class of general backward stochastic differential equations and backward doubly stochastic differential equations to provide a standard method to prove the existence and uniqueness of the Lp solutions and to obtain the Lp estimates for the solutions. The other project was conducted in collaboration with Josh McGinnis and corresponds to the second chapter in which we provide a physical zero knowledge proof for the popular app game Flow Free. We then show that the methodology can be extended to provide zero knowledge proofs for the related graph problems of the paired many-to-many disjoint covering path problem, the unpaired many-to-many disjoint covering path problem and Hamiltonian cycles.
Yibin Yang, David Heath, Vladimir Kolesnikov, David Devecsery
Recent work has produced interactive Zero Knowledge (ZK) proof systems that can express proofs as arbitrary C programs (Heath et al., 2021, henceforth referred to as ZEE); these programs can be executed by a simulated ZK processor that runs in the 10KHz range. In this work, we demonstrate that such proof systems are amenable to high degrees of parallelism. Our epoch parallelism-based approach allows the prover and verifier to divide the ZK proof into pieces such that each piece can be executed on a different machine. These proof snippets can then be glued together, and the glued parallel proofs are equivalent to the original sequential proof. We implemented and we experimentally evaluate an epoch parallel version of the ZEE proof system. By running the prover and verifier each across 31 2-core machines, we achieve a ZK processor that runs at up to 394KHz. This allowed us to run a benchmark involving the Linux program bzip2, which would have required at least 11 days with the former ZEE system, in only 8.5 hours.
Christopher Molloy, Philippe Charland, Steven H. H. Ding, Benjamin C. M. Fung
Cyber threat intelligence (CTI) has become a critical component of the defense of organizations against the steady surge of cyber attacks. Malware is one of the most challenging problems for CTI, due to its prevalence, the massive number of variants, and the constantly changing threat actor behaviors. Currently, Malpedia has indexed 2,390 unique malware families, while the AVTEST Institute has recorded more than 166 million new unique malware samples in 2021. There exists a vast number of variants per malware family. Consequently, the signature-based representation of patterns and knowledge of legacy systems can no longer be generalized to detect future malware attacks. Machine learning-based solutions can match more variants. However, as a black-box approach, they lack the explainability and maintainability required by incident response teams.There is thus an urgent need for a data-driven system that can abstract a future-proof, human-friendly, systematic, actionable, and dependable knowledge representation from software artifacts from the past for more effective and insightful malware triage. In this paper, we present the first phenotype-based malware decomposition system for quick malware triage that is effective against malware variants. We define phenotypes as directly observable characteristics such as code fragments, constants, functions, and strings. Malware development rarely starts from scratch, and there are many reused components and code fragments. The target under investigation is decomposed into known phenotypes that are mapped to known malware families, malware behaviors, and Advanced Persistent Threat (APT) groups. The implemented system provides visualizable phenotypes through an interactive tree map, helping the cyber analysts to navigate through the decomposition results. We evaluated our system on 200,000 malware samples, 100,000 benign samples, and a malware family with over 27,284 variants. The results indicate our system is scalable, efficient, and effective against zero-day malware and new variants of known families.
Federation Payment Tree, a new Off-chain with zero-knowledge hash time lock commitment setup is proposed in this paper. The security of blockchain is based on consensus protocols that delay when number of concurrent transactions processed in given throughput framework. The scalability of blockchain is the ability to perform support increasing workload transaction. The FP-Tree provides zero knowledge hash lock commitment connect with off-chain protocols by using the payment channel, which enables execution of off-chain protocol that allows interaction between the parties without involving the consensus protocol. It allows to make payment across an authorization path of payment channel. Such a payment tree requires two commitment scheme is Timelock and Fundlock, each party lock fund for a time period. The main challenges we faced in this paper is that the computational power, storage and cryptography. Furthermore, we discussed many attacks on off-chain payment channel that allows a malicious adversary to make fund lose. The FP-Tree supports multi-parti computation (MPC) merging transactions into single hash value in payment tree. We enable the parties to generate single hash value by consumes both less than 0 (log2 N ) and space less than 0 (log2 N ) time combine element over length of single hash. The results were discussed in this paper and efficiency of FP-Tree is well suited for the blockchain technology. We achieved the accuracy of 60.2% in federated payment tree when compared with the proof of work and proof of authority.
Blockchain Technology Applications and Security
IoT and Edge/Fog Computing
Advanced Steganography and Watermarking Techniques
Distributed Ledger Technology is also known as blockchain technology. It brings the characteristics like transparency, decentralization, immutability, and the distributed ledger in one package. The user identity of the public blockchain is anonymous on the network and cannot control the confidentiality and privacy of their data. The Anonymity of a user does not mean privacy. The importance of user and data privacy and confidentiality in blockchain technology is realized and is yet to be addressed by blockchain protocols. Zero-Knowledge-Proof can be the best solution to this problem. It is relatively new and is developing very rapidly. Zero-Knowledge-Proof can provide strong privacy if the security model is well understood and used carefully. Zero-Knowledge-Proof makes sure that no one accesses the secured data except the user. Paper discusses the types and the various applications of the Zero-Knowledge-Proof in the blockchain.
With the rapid increase of the industrial data and the development of the industrial Internet of Things (IIoT) paradigm, the efficiency and the quality of service of the emerging applications have been improved. However, the contradiction between data sharing and privacy preserving is still an obstacle in the IIoT. To this end, in this article, we propose a privacy-preserving and publicly auditable multiparty computation scheme for industrial data sharing and computing, which avoids privacy leakage and computation misbehavior by separating the data ownership, data use, and data verification. Using the blockchain technology, a transparent management platform is provided to recognize and trace the illegal data and computation behavior. Moreover, we integrate the noninteractive zero-knowledge proof in the multiparty interaction mechanism, wherein the verification of data consistency and computation validity is executed publicly on the blockchain. Finally, we implement experiment to evaluate the performance of the computation latency, communication overhead and the influence of encryption parameter, and the numerical results illustrate the efficiency and feasibility of our scheme.
How to achieve secure content distribution and accountability in information-centric networking (ICN) is a crucial problem. Subscribers need to verify whether the data came from a reliable source, rather than from a spoofing adversary. Public key cryptography was introduced to achieve a method of authentication that binds the data packet to its owner. In existing prototypes, PKIs, identity-based signatures (IBSs) and recommendation networks are the common schemes used to ensure the authenticity and availability of public keys. However, CA-based PKIs and KGC-based IBSs have been proven to be weak when it comes to resisting security attacks, with recommendation networks being too complex to deploy. In this respect, we designed a novel distributed authentication model as a secure scheme to support public key cryptography. Our model establishes a decentralized public key infrastructure by combining the smart contracts of blockchain and optimized zero-knowledge proof-verifiable presentations by utilizing the DID project, which realizes the management of public key certificates through blockchain and ensures the authenticity and availability of public keys in decentralized infrastructure. Our scheme fundamentally solves the issues of security and feasibility in existing schemes and provides a more scalable solution with respect to authenticating data sources. An experiment demonstrated that our proposal is 20% faster than the original zero knowledge proof scheme in registration.
Open access
Caching and Content Delivery
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
When trying to fit a deep neural network (DNN) to a $G$-invariant target function with $G$ a group, it only makes sense to constrain the DNN to be $G$-invariant as well. However, there can be many different ways to do this, thus raising the problem of ``$G$-invariant neural architecture design'': What is the optimal $G$-invariant architecture for a given problem? Before we can consider the optimization problem itself, we must understand the search space, the architectures in it, and how they relate to one another. In this paper, we take a first step towards this goal; we prove a theorem that gives a classification of all $G$-invariant single-hidden-layer or ``shallow'' neural network ($G$-SNN) architectures with ReLU activation for any finite orthogonal group $G$, and we prove a second theorem that characterizes the inclusion maps or ``network morphisms'' between the architectures that can be leveraged during neural architecture search (NAS). The proof is based on a correspondence of every $G$-SNN to a signed permutation representation of $G$ acting on the hidden neurons; the classification is equivalently given in terms of the first cohomology classes of $G$, thus admitting a topological interpretation. The $G$-SNN architectures corresponding to nontrivial cohomology classes have, to our knowledge, never been explicitly identified in the literature previously. Using a code implementation, we enumerate the $G$-SNN architectures for some example groups $G$ and visualize their structure. Finally, we prove that architectures corresponding to inequivalent cohomology classes coincide in function space only when their weight matrices are zero, and we discuss the implications of this for NAS.
E-petition has played an important role in health and politics that collects public opinions and requests a superior or an authority to take actions towards a health or political problem. However, this activity exposes the privacy of the signers who participate to express opinions. In this paper, we propose a privacy-preserving fine-grained e-petition system that supports attribute-based identity verification for signers, while protecting their privacy. By considering the target groups of signers in a specific health or political petition, an attribute policy is defined to ensure that only the signers with the attributes that satisfy the attribute policy can sign the petition. The fine-grained petition is better than the traditional e-petitions because it can improve the trustworthiness of the petition results via proactive signer selection. Moreover, the new petition system protects the identities of the signers by using the non-interactive zero-knowledge proof system, such that the signers are anonymous in signing petitions. In addition, the proposed petition system supports the tracing of double-signing, a cheating behavior that an anonymous signer can submit more than one signature in a petition without being detected. Finally, we prove that the proposed petition system achieves the desirable security properties, including anonymity, unforgeability, and traceability, and demonstrate that the system is efficient to be implemented on the mobile devices.
Despite decades of development progress, the current e-voting systems still suffer several challenges especially in terms of security and privacy. Some of the key reasons behind this issue include lack of transparency in the process and inadequate privacy guarantee for the voters. To address these issues, we propose and construct zVote, a blockchain-based e-voting platform that aims to create a transparent and secure system for remote e-voting. With the use of blockchain, the voting result can be verifiable by the public, thereby eliminating the trust in the election authorities. Furthermore, we leverage homomorphic encryptions and zero-knowledge proofs to protect the privacy of users, especially in terms of anonymity and membership privacy, while retaining the correctness and verifiability of the votes. We provide formal definitions and proofs of the construction’s security. Our proof-of-concept implementation demonstrates the feasibility and practicality of zVote.
Zero-knowledge proofs (ZKP) are a widely used technology for privacy protection and data ownership that allows parties to verify the accuracy of a piece of information without sharing the data. In this study, we developed and performance tested two graph-based zero-knowledge proof methods, the Hamilton Cycle Based ZKP Algorithm (ZKPHC) and the Graph Isomorphism Based ZKP Algorithm (ZKPGI), using an open source library. As the graph sizes increased, we measured and compared the running times of these methods. We tested the completeness and robustness of the ZKPHC protocol for different modes. As the graph used grows, the ZKPHC method, which uses encryption at every stage, works much slower than ZKPGI.
We propose an efficient identity authentication protocol based on cancelable biometric and Physical Uncloable Function (PUF) namely BioP-TAP, which realizes the two-way authentication between the user and the server. Specially, the concept of biometric template protection is added to the proposed protocol to better protect user privacy. We use the properties of PUF to generate the cancelable biometric and adds it to the authentication protocol. Then, we design a complete authentication protocol combining the elliptic curve Pedersen commitment and Zero-knowledge proof. Finally, we adopt the method of combining formalization and non-formalization to carry out scientific evaluation from multiple perspectives. And the performance analysis and comparison with existing schemes are employed to evaluate the proposed scheme, so as to ensure the effectiveness and security. The results show that the proposed method is more effective for security than existing methods, and more suitable for the user biometric authentication in a multi-server environment.
Biometric Identification and Security
Physical Unclonable Functions (PUFs) and Hardware Security
The assignment problem is an essential problem in many application fields and frequently used to optimize resource usage. The problem is well understood and various efficient algorithms exist to solve the problem. However, it was unclear what practical performance could be achieved for privacy preserving implementations based on multiparty computation (MPC) by leveraging more efficient solution strategies than MPC based simplex solvers for linear programs. We solve this question by implementing and comparing different optimized MPC algorithms to solve the assignment problem for reasonable problem sizes. Our empirical approach revealed various insights to MPC based optimization and we measured a significant (50x) speedup compared to the known simplex based approach. Furthermore, we also study the overhead introduced by making the results publicly verifiable by means of non-interactive zero-knowledge proofs. By leveraging modern proof systems we also achieve significant speedup for proof and verification times compared to the previously proposed approaches as well as compact proof sizes.
Christian Killer, Moritz Eck, Bruno Rodrigues, Jan von der Assen · 6 authors
Recent years saw an increase in voting systems using public permissionless blockchains. Although public blockchains offer transparency and immutability, permissioned consensus is better suited for voting systems’ requirements, because an initial level of trust in authorities is always required. Hence, a permissioned Distributed Ledger (DL) immutably storing the voting system’s audit trail satisfies demands measurably.ProvotuMN 3.0 is a decentralized and receipt-Free (RF) voting system based on an end-to-end verifiable Re-Encryption Mixnet (RMN). RMNs allow for flexible votes and elections and decouple the ballot structure from the cryptographic voting protocol. Thus, ProvotuMN decentralizes trust (i) through the use of cryptographic shuffles and Non-Interactive Zero-Knowledge Proofs (NIZKP) in an RMN executed among DL nodes, (ii) by employing a distributed key generation for election keys, and (iii) by offering a decentralized re-encryption service assuring RF. Performance evaluations performed indicate that the voting scheme is scalable for large-scale voting.
Sealed-bid auctions are a widely used transaction method in today’s society. The traditional implementation scheme relies too much on third-party platforms, and there are severe problems in the auction protocol’s security and users’ privacy protection. At present, some sealed bid auction schemes based on blockchain technology have been proposed, but these schemes generally do not consider the storage cost of users. We propose a sealed-bid auction protocol based on Ethereum smart contracts that remove third parties in traditional protocols to address these issues. We have significantly reduced the storage cost of users by introducing the Interplanetary File System (IPFS). In particular, we use a commitment mechanism to protect bid privacy and combine it with a zero-knowledge proof algorithm to achieve publicly verifiable bidders, guaranteeing the protocol’s security, privacy, and transaction fairness. The experimental results show that the proposed sealed bid auction protocol can reduce the storage cost of users in Ethereum while ensuring the security of the protocol and the privacy of users’ bids.
The use of Electric Vehicles (EVs) has been gaining traction in recent years due to various reasons. While charging their EVs, users expose their identity and personal details, and an adversary being able to identify and track where users charge their EVs is a potential privacy threat. In this article, we propose a user-empowered privacy-preserving authentication protocol for EV charging based on Decentralized Identifier (DID) and Verifiable Credential (VC) to provide Zero-Knowledge Proof (ZKP)-security. The proposed method gives users full control over their identities and allows them to remain anonymous while charging from any station. Giving control over their identities empowers users. At the same time, by making use of the concept of VC, other parties can verify that a user is legitimate and authenticate the user before providing charging services. Hence, the proposed protocol makes the charging service available in a secure way, while empowering users and preserving their privacy.
Abstract Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O (1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing $$\text{ SNARG } $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mspace/><mml:mtext>SNARG</mml:mtext><mml:mspace/></mml:mrow></mml:math> s, as well as resulting new efficiency features. Our contribution is threefold: (1) We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded “adversaries” in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional “unstructured” PCPs. (2) We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques. (3) Following this methodology, we exhibit several constructions achieving new efficiency features, such as “single-ciphertext preprocessing SNARGs.” We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.
Blockchain technology is one of the most popular information technologies at present, and its security features are realized through various cryptographic tools. Zero-knowledge proofs are such a tool that can increase data security and improve users’ privacy, and zero-knowledge proof schemes constructed with polynomial commitments have advantages in terms of verification time and proof size. Benefiting from the development of blockchain technology, zero-knowledge proof has also ushered in rapid development. This paper analyzes the research status of zero-knowledge proof schemes based on polynomial commitment construction, and introduces the construction and security of polynomial commitments. Finally, blockchain and some other potential commitment schemes that can be used for zero-knowledge proofs and blockchain construction are introduced as future research directions and engineering applications.
Crowdsourcing for Human Intelligence Tasks (HIT) has been widely used to crowdsource human knowledge, such as image annotation for machine learning. We use a public blockchain to play the role of traditional centralized HIT systems, such that the blockchain deals with cryptocurrency payments and acts as a trustworthy judge to resolve disputes between a worker and a requester in a decentralized setting, preventing false-reporting and free-riding. Our approach neither uses expensive cryptographic tools, such as zero-knowledge proofs, nor sends the worker's answers to the blockchain. Compared with prior works, our approach significantly reduces on-chain cost: it only requires O(1) on-chain storage and O(log N ) smart contract computation, where N is the question number of a HIT. Additionally, our approach uses known answers or gold standards to determine the worker's answer quality. To motivate the requester to use honest known answers, the requester cannot learn the worker's answers if the answer quality does not meet the requirement. We further provide formal security definitions for our decentralized HIT and prove security of our construction.
Zero-knowledge blocklists allow cross-platform blocking of users but, counter-intuitively, do not link users identities inter- or intra-platform, or to the fact they were blocked. Unfortunately, existing approaches (Tsang et al. ’10) require that servers do work linear in the size of the blocklist for each verification of a non-membership proof.We design and implement SNARKBLOCK, a new protocol for zero-knowledge blocklisting with server-side verification that is logarithmic in the size of the blocklist. SNARKBLOCK is also the first approach to support ad-hoc, federated blocklisting: websites can mix and match their own blocklists from other blocklists and dynamically choose which identity providers they trust.Our core technical advance, of separate interest, is the HICIAP zero-knowledge proof system, which addresses a common problem in privacy-preserving protocols: using zero-knowledge proofs for repeated but unlinakble interactions. Rerandomzing a Groth16 proof achieves unlinkability without the need to recompute the proof for every interaction. But this technique does not apply to applications where each interaction includes multiple Groth16 proofs over a common hidden input (e.g., the user’s identity). Here, the best known approach is to commit to the hidden input and feed it to each proof, but this creates a persistent identifier, forcing recomputation. HICIAP resolves this problem by aggregating n Groth16 proofs into one $O(\log n) -$sized, $O(\log n) -$verification time proof which also shows that the input proofs share a hidden input. Because HICIAP is zero-knowledge, repeated shows of the same aggregate or an updated aggregate are unlinkable even though the underlying Groth16 proofs are never recomputed.