The problem of revocation in anonymous authentication systems is subtle and has motivated a lot of work. One of the preferable solutions consists in maintaining either a whitelist LWof non-revoked users or a blacklist LBof revoked users, and then requiring users to additionally prove, when authenticating themselves, that they are in LW(membership proof) or that they are not in LB(non-membership proof). Of course, these additional proofs must not break the anonymity properties of the system, so they must be zero-knowledge proofs, revealing nothing about the identity of the users. In this paper, we focus on the RSA-based setting, and we consider the case of non-membership proofs to blacklists L = LB. The existing solutions for this setting rely on the use of universal dynamic accumulators; the underlying zero-knowledge proofs are bit complicated, and thus their efficiency; although being independent from the size of the blacklist L, seems to be improvable. Peng and Bao already tried to propose simpler and more efficient zero-knowledge proofs for this setting, but we prove in this paper that their protocol is not secure. We fix the problem by designing a new protocol, and formally proving its security properties. We then compare the efficiency of the new zero-knowledge non-membership protocol with that of the protocol, when they are integrated with anonymous authentication systems based on RSA (notably, the IBM product Idemix for anonymous credentials). We discuss for which values of the size k of the blacklist L, one protocol is preferable to the other one, and we propose different ways to combine and implement the two protocols.
User, content, and device names as a security primitive have been an attractive approach especially in the context of Information-Centric Networking (ICN) architectures. We leverage Hierarchical Identity Based Encryption (HIBE) to build (content) name-based security mechanisms used for securely distributing content. In contrast to similar approaches, in our system each user maintains his own Private Key Generator used for generating the master secret key and the public system parameters required by the HIBE algorithm. This way our system does not suffer from the key escrow problem, which is inherent in many similar solutions. In order to disseminate the system parameters of a content owner in a fully distributed way, we use blockchains, a distributed, community managed, global list of transactions.
Alexander Chepurnoy, Mario Larangeira, Alexander Ojiganov
Bitcoin is the first successful decentralized global digital cash system. Usefulness of the mining process requiring a lot of computational resources to be wasted, though, remains disputable. One of possible alternatives for useful Proof-of-Work schemes, Permacoin, is using non-interactive proofs of a static dataset retrievability thus providing a mechanism to store a huge dataset being spread across miners collectively.
In this paper we present a new consensus protocol for Bitcoin-like peer-to-peer systems, where the right to generate a block is given to the party which provides non-interactive proofs of retrievability for the past state snapshots. This Proof-of-Work scheme has better resistance to specialized hardware than Bitcoin and Permacoin. Unlike blockchain systems being used today, a network using the protocol of ours is safe if majority of nodes are rational in terms of storing full blocks. By using that we also show that one useful application of our protocol is the construction of a prunable blockchain system without a security loss.
We have proved that zero-knowledge proofs technique using integer factorization problem has big-oh O(τ1/4)for factoring integers algorithm given by Pollard's rho in comparison with Henry for discrete logarithm problem that is τ+τ/lgτ. Also, we have positively presented covariance between our result and Henry which clearly implies the input variables used for both functions tend to show similar behavior.
Bitcoin mining presents a significant economic incentive for efficient hashing and broadcast of data, both parameters stemming from the Proofs of Work used to advance the network. This incentive has led to the development of Bitcoin specific application specific integrated circuits and centralized mining pools, undermining the decentralized motivations behind Bitcoin's design. In addition, the imminent block reward halving threatens the profitability of mining at any scale. Some work has been done in formal models for miner profitability, but existing models do not account for conditions such as the pricing of off-peak power and diverse investment strategies regarding sunken costs. There is also a lack of formal study of how the profit model changes as mining scales from the individual to the industrial level. Given the lack of analysis of these conditions, there are alternative models for profitable or net zero mining that operate at smaller, and therefore more desirable, scale.
Jeril Kuriakose, Pushpendra Singh Sisodia, V. Amruth, Dhvani Shah · 5 authors
Cryptography and complexity theory have gained a lot of importance because of zero-knowledge proofs. The motive behind zero-knowledge proofs are to provide an obfuscation to the verifier, so that the verifier will not understand the information sent by the prover. Zero-knowledge proofs are normally used to verify a prover's theorem to a verifier, in such a way that the verifier will not be able to discover any supplementary evidence other than the proof given to him. An enigmatic conception was formalized, that lead to the formation zero-knowledge proof systems. In this paper, we have reviewed different zero-knowledge argument / proof techniques. We have also reviewed the proof system implications in the presence of malicious prover and malicious verifier. Examples related to zero-knowledge argument systems are also given.
Stanisław Jarecki, Aggelos Kiayias, Hugo Krawczyk, Jiayu Xu
PPSS is a central primitive introduced by Bagherzandi et al. [2] which allows a user to store a secret among n servers such that the user can later reconstruct the secret with the sole possession of a single password by contacting t + 1 (t <; n) servers. At the same time, an attacker breaking into t of these servers - and controlling all communication channels - learns nothing about the secret (or the password). Thus, PPSS schemes are ideal for on-line storing of valuable secrets when retrieval solely relies on a memorizable password. We show the most efficient Password-Protected Secret Sharing (PPSS) to date (and its implied Threshold-PAKE scheme), which is optimal in round communication as in Jarecki et al. [10] but which improves computation and communication complexity over that scheme requiring a single per-server exponentiation for the client and a single exponentiation for the server. As with the schemes from [10] and Camenisch et al. [4] we do not require secure channels or PKI other than in the initialization stage. We prove the security of our PPSS scheme in the Universally Composable (UC) model. For this we present a UC definition of PPSS that relaxes the UC formalism of [4] in a way that enables more efficient PPSS schemes (by dispensing with the need to extract the user's password in the simulation) and present a UC-based definition of Oblivious PRF (OPRF) that is more general than the (Verifiable) OPRF definition from [10] and is also crucial for enabling our performance optimization.
Bitcoin is the first decentralized peer-to-peer (P2P) electronic currency. It was created in November 2008 by Satoshi Nakamoto. Nakamoto released the first implementation of the protocol in an open source client software and the genesis of bitcoins began on January 9th 2009. The Bitcoin protocol is based on clever ideas which solve a form of the Byzantine Generals Problem and sets the foundation for Decentralized Trust Protocols. Still in its infancy, the currency and the protocol have the potential to disrupt the international financial system and other sectors where business is based on trusted third parties. The security of the bitcoin protocol relies on strong cryptography and one way hashing algorithms.
Francisco Martín-Fernández, Pino Caballero‐Gil, Cándido Caballero‐Gil
This paper describes the design and analysis of a new scheme for the authenticated exchange of confidential information in insecure environments within the Internet of Things, which allows a receiver of a message to authenticate the sender and compute a secret key shared with it. The proposal is based on the concept of a non-interactive zero-knowledge proof, so that in a single communication, relevant data may be inferred to verify the legitimacy of the sender. Besides, the new scheme uses the idea under the Diffie-Hellman protocol for the establishment of a shared secret key. The proposal has been fully developed for platforms built on the Android Open Source Project, so it can be used in any device or sensor with this operating system. This work provides a performance study of the implementation and a comparison between its promising results and others obtained with similar schemes.
Bitcoin [24] is a fully decentralized electronic cash system. The generation of the proof-of-work in Bitcoin requires large amount of computing resources. However, this huge amount of energy is wasted as one cannot make something useful out of it. In this paper, we propose a scheme called Retricoin which replaces the heavy computational proof-of-work of Bitcoin by proofs of retrievability that have practical benefits. To guarantee the availability of an important but large file, we distribute the segments of the file among the users in the Bitcoin network. Every user who wants to mine Bitcoins must store a considerable portion of this file and prove her storage to other peers in the network using proofs of retrievability. The file can be constructed at any point of time from the users storing their respective segments untampered. Retricoin is more efficient than the existing Permacoin scheme [23] in terms of storage overhead and network bandwidth required to broadcast the proof to the Bitcoin network. The verification time in our scheme is comparable to that of Permacoin and reasonable for all practical purposes. We also design an algorithm to let the miners in a group (or pool) mine collectively.
The paper examines decentralized cryptocurrency protocols that are based on the use of internal tokens as identity tools. An analysis of security problems with popular Proof-of-stake consensus protocols is provided. A new protocol, Interactive Proof-of-stake, is proposed. The main ideas of the protocol are to reduce a number of variables a miner can iterate over to a minimum and also to bring a communication into block generation. The protocol is checked against known attacks. It is shown that Interactive Proof-of-stake is more secure than current pure Proof-of-stake protocols.
We propose Blind Password Registration (BPR), a new class of cryptographic protocols that is instrumental for secure registration of client passwords at remote servers with additional protection against unwitting password disclosures on the server side that may occur due to the lack of the state-of-the-art password protection mechanisms implemented by the server or due to common server-compromise attacks. The dictionary attack resistance property of BPR protocols guarantees that the only information available to the server during and after the execution of the protocol cannot be used to reveal the client password without performing an offline dictionary attack on a password verifier (e.g. salted hash value) that is stored by the server at the end of the protocol. In particular, at no point in time the server is supposed to work with plain passwords. Our BPR model allows servers to enforce password policies and the requirement on the client to obey them during the execution of the BPR protocol is covered by the policy compliance property.We construct an efficient BPR protocol in the standard model for ASCII-based password policies using some techniques underlying the recently introduced Zero-Knowledge Password Policy Checks (ZKPPC). However, we do not rely on the full power of costly ZKPPC proofs and in fact show that BPR protocols can be modelled and realised simpler and significantly faster (as supported by our implementation) without using them as a building block. Our BPR protocol can directly be used to replace ZKPPC-based registration procedure for existing VPAKE protocols.
Distributed consensus (aka Byzantine agreement [Pease, Shostak & Lamport, 1980]) is one of the fundamental problems in fault-tolerant distributed computing and cryptographic protocols. It requires correct participants (parties) to reach agreement on initially held values despite the arbitrary behavior of some of them, with the additional requirement (known as Validity) that if all the correct participants start off with the same value, then that must be the decision value. The problem has been studied extensively in both the unconditional setting (where no assumptions are made about the computational power of the adversary) and the cryptographic setting, and efficient (i.e., polynomial-time) solutions exist tolerating the optimal number of misbehaving parties and running in the optimal number of rounds, on networks with pairwise authenticated channels. In many interesting scenarios, however, such as "peer-to-peer" networks, where parties come and go as they please and there are no prior relations among them, such infrastructure (pairwise authenticated channels, public-key infrastructure) is unavailable, thus raising the question whether anything "interesting" can be achieved. In this talk we answer this question in the affirmative, presenting two new probabilistic consensus protocols based on "proofs of work" (POWs, aka "moderately hard functions," "cryptographic puzzles" [Dwork & Naor, 1992]), the technology underlying Bitcoin, the first and most popular decentralized cryptocurrency to date. (In Bitcoin, POWs are implemented using the SHA-256 cryptographic hash function, by finding preimages that produce values in a given smaller domain.) In more detail, we first extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two fundamental properties of its "blockchain" approach which we call "common prefix" and "chain quality." The consensus protocols can then be built as applications on top of the backbone protocol, with the Agreement and Validity properties following from common prefix and chain quality, respectively. The first protocol works assuming the adversary's hashing power is bounded by 1/3 of the network's total hashing power. The second consensus protocol is more elaborate, relies on the notion of robust transaction ledgers, which capture the essence of Bitcoin's operation as a cryptocurrency, and works assuming the adversary's hashing power is strictly less than 1/2.
In this paper we investigate the concept of cancelable biometrics and propose a new scheme for user authorisation providing anonymity based on privacy-preserving computations on sets. We define a problem called (t;n) -Threshold Subset Problem and apply it to a biometric-based security system. Our solution implements biometric template protection based on one-way transformations and Bloom filters. Users authentication data is stored in form of a whitelist and the authorisation process is based on a zero-knowledge proof approach. Using oblivious polynomial evaluation (OPE) a legitimate user is able to recreate a secret polynomial and answer the challenge send by a verifier. We assume that biometric data can be acquired and digitized to the form of a vector representation.
Proof-of-work is a central concept in modern cryptocurrencies and denial-ofservice protection tools, but the requirement for fast verification so far has made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on memory-intensive computations in order to remedy the disparity between architectures have resulted in slow or broken schemes. In this paper we solve this open problem and show how to construct an asymmetric proof-of-work (PoW) based on a computationally-hard problem, which requires a great deal of memory to generate a proof (called a ”memory-hardness” feature) but is instant to verify. Our primary proposal, Equihash, is a PoW based on the generalized birthday problem and enhanced Wagner’s algorithm for it. We introduce the new technique of algorithm binding to prevent cost amortization and demonstrate that possible parallel implementations are constrained by memory bandwidth. Our scheme has tunable and steep time-space tradeoffs, which impose large computational penalties if less memory is used. Our solution is practical and ready to deploy: a reference implementation of a proof-of-work requiring 700 MB of RAM runs in 15 seconds on a 2.1 GHz CPU, increases the computations by a factor of 1000 if memory is halved, and presents a proof of just 120 bytes long.
Blockchains and Byzantine Fault Tolerance form the basis of decentralized currencies and ledgers such as Bitcoin, Ripple, ZeroCash, and Ethereum. A large slate of literature has focused on the currency aspects (e.g. anonymity, independence from central banks, etc.). We argue that, as-far-as Distributed Payment Transactions Networks (PTNs) are concerned, there are other, possibly more interesting, properties. This paper provides a systematic review of both traditional PTNs and their analogues in decentralized ledgers and associates different technological features to the corresponding business and financial requirements. We provide a conceptual classification of the key properties (value creation, payment promise, transaction fulfillment, and value preservation). We map existing (distributed) PTNs into the classification showing different alternatives are possible. Furthermore, the ideas behind distributed ledgers can be extended beyond payments and contracts. We illustrate the idea of derivatives-contracts-as-programs that are marked to market (or an account that is margined) automatically by computations run on, and whose ownership transitions are recorded, in a distributed payment network.