Blockchain technology has been gaining great interest from a variety of sectors including healthcare, supply chain, and cryptocurrencies. However, Blockchain suffers from a limited ability to scale (i.e., low throughput and high latency). Several solutions have been proposed to tackle this. In particular, sharding has proved to be one of the most promising solutions to Blockchain's scalability issue. Sharding can be divided into two major categories: (1) Sharding-based Proof-of-Work (PoW) Blockchain protocols, and (2) Sharding-based Proof-of-Stake (PoS) Blockchain protocols. The two categories achieve good performances (i.e., good throughput with a reasonable latency), but raise security issues. This article focuses on the second category. In this paper, we start by introducing the key components of sharding-based PoS Blockchain protocols. We then briefly introduce two consensus mechanisms, namely PoS and practical Byzantine Fault Tolerance (pBFT), and discuss their use and limitations in the context of sharding-based Blockchain protocols. Next, we provide a probabilistic model to analyze the security of these protocols. More specifically, we compute the probability of committing a faulty block and measure the security by computing the number of years to fail. We achieve a number of years to fail of approximately 4000 in a network of 4000 nodes, 10 shards, and a shard resiliency of 33%.
In 1982, Chaum [21] pioneered the anonymous e-cash which finds many applications in e-commerce. In 1993, Brands [8--10] and Ferguson [30, 31] published on single-term offline anonymous ecash which were the first practical e-cash. Their constructions used blind signatures and were inefficient to implement multi-spendable e-cash. In 1995, Camenisch, Hohenberger, and Lysyanskaya [12] gave the first compact 2 -spendable e-cash, using zero-knowledge-proof techniques. They left an open problem of the simultaneous attainment of O(1)-unit wallet size and efficient coin tracing. The latter property is needed to revoke bad coins from over-spenders. In this paper, we solve [12]'s open problem, and thus enable the first practical compact e-cash. We use a new technique whose security reduces to a new intractability assumption: the Decisional Harmonically-Tipped Diffie-Hellman (DHTDH) Assumption.
Abstract. There is a broad literature on distributed card games over communications networks, collectively known as mental poker. Likein any distributed protocol, avoiding the need for a Trusted Third Party (TTP) in mental poker is highly desirable, because really trusted TTPs are not always available and seldom free. This paper deals with the player dropout problem in mental poker without a TTP. A solution based on zero-knowledge proofs is proposed. While staying TTP-free, our proposal allows the game to continue after player dropout.
Abstract. In undeniable signature schemes, zero-knowledgeness and non-transferability have been identified so far. In this paper, by separating these two notions, we show the first 3-move confirmation and disavowal protocols for Chaum’s undeniable signature scheme which is secure against active and concurrent attacks. Our main observation is that while the signer has one public key and one secret key, there exist two witnesses in the confirmation and disavowal proofs of Chaum’s scheme.
Efficient general secure multiparty computation (MPC) protocols were previously proposed, and the combination with the efficient auction circuits achieves the efficient sealed-bid auctions with the full privacy and correctness. However, the combination requires that each bidder submits ciphertexts of bits representing his bid, and their zero-knowledge proofs. This cost amounts to about 80.multi-exponentiations in usual case that the bid size is 20 bits (i.e. about 1,000,000 bid prices). This paper proposes sealed-bid auction protocols based on the efficient MPC protocols, where a bidder can submit only a single ciphertext. The bidder's cost is a few multi-exponentiations, and thus the proposed protocols are suitable for mobile bidders. A novel technique for the realization is a bit-slicing conversion by multiple servers, where a single ciphertext for a bid is securely converted into ciphertexts of bits representing the bid.
A publicly verifiable secret sharing scheme is more applicable than a verifiable secret sharing because of the property that the validity of the shares distributed by the dealer can be verified by any party. In this paper, we construct a non-interactive and informationtheoretic publicly verifiable secret sharing by a computationally binding and unconditionally hiding commitment scheme and zero-knowledge proof of knowledge.
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting.<br /> <br />We propose new techniques for building <em>quantum</em> zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK.<br /> <br />As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks.<br /> <br />Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, <em>non-oblivious verifier</em> QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.
Wanzong Peng, Tongliang Lu, Wenju Peng, Zhongpan Wang
File sharing, being the foundation of the Internet, has traditionally relied on a centralized service architecture resulting in significant maintenance costs. Moreover, due to the lack of an effective file management system, instances of sensitive information going out of control and loss of confidentiality in file sharing have occurred frequently. In order to address the difficulty of tamper detection and the lack of supervision in the entire process of file transfer in the current Internet environment, this paper designs a blockchain-based system architecture for secure sharing of electronic documents. An efficient blockchain model is used in our framework, and with the help of distributed storage system and asymmetric encryption technology, file sharing can be controlled, reliable and traceable in the transfer process. Referring to existing consensus mechanisms, e.g., Delegated Proof of Stake (DPoS) and Practical Byzantine Fault Tolerance (PBFT), we propose a new consensus for efficient and secure file sharing. Our experimental results show that our framework can maintain a higher throughput than existing schemes.
We present the first constant-round non-malleable commitment scheme and the first constant-round non-malleable zero-knowledge argument system, as defined by Dolev, Dwork and Naor (1991). Previous constructions either used a non-constant number of rounds, or were only secure under stronger setup assumptions. An example of such an assumption is the shared random string model where we assume all parties have access to a reference string that was chosen uniformly at random by a trusted dealer. We obtain these results by defining an adequate notion of non-malleable coin-tossing, and presenting a constant-round protocol that satisfies it. This protocol allows us to transform protocols that are non-malleable in (a modified notion of) the shared random string model into protocols that are non-malleable in the plain model (without any trusted dealer or setup assumptions). Observing that known constructions of a non-interactive non-malleable zero-knowledge argument systems in the shared random string model (De Santis et. al., 2001) are in fact non-malleable in the modified model, and combining them with our coin-tossing protocol we obtain the results mentioned above. The techniques we use are different from those used in previous constructions of non-malleable protocols. In particular our protocol uses diagonalization and a non-black-box proof of security (in a sense similar to Barak's zero-knowledge argument (2001)).
Cynthia Dwork, Moni Naor, Omer Reingold, Larry Stockmeyer
We prove that three apparently unrelated fundamental problems in distributed computing, cryptography, and complexity theory, are essentially the same problem. These three problems and brief descriptions of them follow. (1) The selective decommitment problem. An adversary is given commitments to a collection of messages, and the adversary can ask for some subset of the commitments to be opened. The question is whether seeing the decommitments to these open plaintexts allows the adversary to learn something unexpected about the plaintexts that are unopened. (2) The power of 3-round weak zero-knowledge arguments. The question is what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument. In particular, is there a language outside of BPP that has a 3-round public-coin weak zero-knowledge argument? (3) The Fiat-Shamir methodology. This is a method for converting a 3-round public-coin argument (viewed as an identification scheme) to a 1-round signature scheme. The method requires what we call a "magic function" that the signer applies to the first-round message of the argument to obtain a second-round message (queries from the verifier). An open question here is whether every 3-round public-coin argument for a language outside of BPP has a magic function.It follows easily from definitions that if a 3-round public-coin argument system is zero-knowledge in the standard (fairly strong) sense, then it has no magic function. We define a weakening of zero-knowledge such that zero-knowledge ⇒ no-magic-function still holds. For this weakened form of zero-knowledge, we give a partial converse: informally, if a 3-round public-coin argument system is not weakly zero-knowledge, then some form of magic is possible for this argument system. We obtain our definition of weak zero-knowledge by a sequence of weakenings of the standard definition, forming a hierarchy. Intermediate forms of zero-knowledge in this hierarchy are reasonable ones, and they may be useful in applications. Finally, we relate the selective decommitment problem to public-coin proof systems and arguments at an intermediate level of the hierarchy, and obtain several positive security results for selective decommitment.
Elections around the world have become a major international concern since the inception of modern democracy. It is a fact that the success of any democracy depends largely on its electoral process. In conducting a free and credible election, the process must be transparent to be adjudged credible. The electioneering process begins with the compilation of a voter register; this register contains the details of every eligible voter as stipulated by law or guild lines that guilds the electoral process. As part of what makes up, the guidelines are age restrictions for every intended voter. It is forbidding by law in most countries for a child to register as a voter, but this is not so in reality in most countries, especially in a developing nation. Because the age restriction is not obeyed, this has resulted in the incidences of underage voters and disputed election outcomes. This work provides an efficient and effective solution for the above concerns, using multiple digital solutions. The model will be integrating a deep learning Convolutional Neural Network (CNN), an Interplanetary File System (IPFS), and an Ethereum Smart Contract Blockchain. The role of the CNN is to detect any underage individual who intends to register as a voter. The CNN is built with a pretrained dataset, and it was trained with an age classifier that grouped the age on the images on the data set into eight distinct groups. This age grouping will help the age predictive algorithm estimate and place every image on the camera in a unique age group. This will only produce a binary result, which is "eligible to voter or not eligible to vote." This outcome is based on the preset threshold cut-off on the age group. The Interplanetary File System (IPFS) will provide a large storage capacity that will allow for off-chain data storage and still provide the model with all the functionalities and benefits of the blockchain. It also provides a hashing function that will assign and identify every registered voter with a unique cryptographic Identity. This ID will prevent the storage of the same information into the database, in so doing, eliminating multiple voting. Finally, the blockchain will provide a voting platform where the model will be implemented. It will allow every registered voter with a unique ID to create an account and vote on the blockchain. The adapted CNN was tested and evaluated and shows 85.9% performance accuracy, and when compared against two other age predictive models, it recorded an increase of 1.2%. In comparison, the complete digital solution model recorded 95.3% in performance. We believe this model will perform even better when subjected to further research work.
Open access
Science, Technology, and Education in Latin America
We show how to efficiently transform any public coin honest verifier zero knowledge proof system into a proof system that is concurrent zero-knowledge with respect to any (possibly cheating) verifier via black box simulation. By efficient we mean that our transformation incurs only an additive overhead (both in terms of the number of rounds and the computational and communication complexity of each round), and the additive term is close to optimal (for black box simulation): only &amp;omega;(log n) additional rounds, and &amp;omega;(log n) additional public key operations for each round of the original protocol, where n is a security parameter, and &amp;omega;(log n) can be any superlogarithmic function of n independent of the complexity of the original protocol. The transformation preserves (up to negligible additive terms) the soundness and completeness error probabilities, and the new proof system is proved secure based on the Decisional Diffie-Hellman (DDH) assumption, in the standard model of computation, i.e., no random oracles, shared random strings, or public key infrastructure is assumed. We prove our main result...
Abstract. We introduce the notion of a dynamic accumulator. Anaccumulator scheme allows one to hash a large set of inputs into one short value, such that there is a short proof that a given input was incorporated into this value. A dynamic accumulator allows one to dynamically add and delete a value, such that the cost of an add or delete is independent of the number of accumulated values. We provide a construction of a dynamic accumulator and an efficient zero-knowledge proof of knowledge of an accumulated value. We prove their security under the strong RSA assumption. We then show that our construction of dynamic accumulators enables efficient revocation of anonymous credentials, and membership revocation for recent group signature and identity escrow schemes.
Canetti and Fischlin have recently proposed the security notion <em>universal composability</em> for commitment schemes and provided two examples. This new notion is very strong. It guarantees that security is maintained even when an unbounded number of copies of the scheme are running concurrently, also it guarantees non-malleability, resilience to selective decommitment, and security against adaptive adversaries. Both of their schemes uses Theta(k) bits to commit to one bit and can be based on the existence of trapdoor commitments and non-malleable encryption.<br /> <br />We present new universally composable commitment schemes based on the Paillier cryptosystem and the Okamoto-Uchiyama cryptosystem. The schemes are efficient: to commit to k bits, they use a constant number of modular exponentiations and communicates O(k) bits. Furthermore the scheme can be instantiated in either perfectly hiding or perfectly binding versions. These are the first schemes to show that constant expansion factor, perfect hiding, and perfect binding can be obtained for universally composable commitments.<br /> <br />We also show how the schemes can be applied to do efficient zero-knowledge proofs of knowledge that are universally composable.