A secure anonymous authentication scheme was proposed based on elliptic curve and zero-knowledge proof,which adopts a bidirectional anonymous authentication algorithm to preserve users’ privacy during the certification process.In the case of a high density traffic scenario,a message aggregation technology was proposed to realize fast authentication by the assistant of RSU,and to avoid the loss of massive messages unauthenticated promptly.The simulation and analytical results show that the proposed scheme yields a much better performance than previously reported counterparts with lower communication overhead,message loss rate and message delay.
Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek
Abstract—Bitcoin is a decentralized digital currency, intro-duced in 2008, that has recently gained noticeable popularity. Its main features are: (a) it lacks a central authority that controls the transactions, (b) the list of transactions is publicly available, and (c) its syntax allows more advanced transactions than simply transferring the money. The goal of this paper is to show how these properties of Bitcoin can be used in the area of secure multiparty computation protocols (MPCs). Firstly, we show that the Bitcoin system provides an attractive way to construct a version of “timed commitments”, where the committer has to reveal his secret within a certain time frame, or to pay a fine. This, in turn, can be used to obtain fairness in some multiparty protocols. Secondly, we introduce a concept of multiparty protocols that work “directly on Bitcoin”. Recall that the standard definition of the MPCs guarantees only that the protocol “emulates the trusted third party”. Hence ensuring that the inputs are correct, and the outcome is respected is beyond the scope of the definition. Our observation is that the Bitcoin system can be used to go beyond the standard “emulation-based” definition, by constructing protocols that link their inputs and the outputs with the real Bitcoin transactions. As an instantiation of this idea we construct protocols for secure multiparty lotteries using the Bitcoin currency, without relying on a trusted authority (one of these protocols uses the Bitcoin-based timed commitments mentioned above). Our protocols guarantee fairness for the honest parties no matter how the loser behaves. For example: if one party interrupts the protocol then her money is transferred to the honest participants. Our protocols are practical (to demonstrate it we performed their transactions in the actual Bitcoin system), and can be used in real life as a replacement for the online gambling sites. We think that this paradigm can have also other applications. We discuss some of them. Keywords—bitcoin; multiparty; lottery; I.
Arthur Gervais, Ghassan Karame, Vedran Čapkun, Srđjan Čapkun
Bitcoin has achieved large-scale acceptance and popularity by promising its users a fully \ndecentralized and low-cost virtual currency system. However, recent incidents and observations \nare revealing the true limits of decentralization in the Bitcoin system. In this article, we \nshow that the vital operations and decisions that Bitcoin is currently undertaking are not \ndecentralized. More specifically, we show that a limited set of entities currently control the \nservices, decision making, mining, and the incident resolution processes in Bitcoin. We also \nshow that third-party entities can unilaterally decide to “devalue” any specific set of Bitcoin \naddresses pertaining to any entity participating in the system. Finally, we explore possible \navenues to enhance the decentralization in the Bitcoin system.
Man Ho Au, Willy Susilo, Yi Mu, Sherman S. M. Chow
Dynamick-times anonymous authentication (k-TAA) schemes allow members of a group to be authenticated anonymously by application providers for a bounded number of times, where application providers can independently and dynamically grant or revoke access right to members in their own group. In this paper, we construct a dynamick-TAA scheme with space and time complexities ofO(log(k)) and a variant, in which the authentication protocol only requires constant time and space complexities at the cost ofO(k) -sized public key. We also describe some tradeoff issues between different system characteristics. We detail all the zero-knowledge proof-of-knowledge protocols involved and show that our construction is secure in the random oracle model under theq-strong Diffie-Hellman assumption andq-decisional Diffie-Hellman inversion assumption. We provide a proof-of-concept implementation, experiment on its performance, and show that our scheme is practical.
Chengdong Meng, Zhengyong Zhang, Rong Hu, Yongxiang Yang
DAA (Direct Anonymous Attestation) schemes are generally employed with the hardware of TPM to realize anonymous authentication. Basically, DAA schemes are based on group signatures. We propose a new DAA scheme based on a short group signature without encryption which departs from the traditional sign-encrypt-prove paradigm, only adopts an anonymous signature and non-interactive zero knowledge(NIZK) proofs. Compared to other DAA schemes at present, our scheme is approximately the most efficient and computational cost-saving with shorter signature length and easier signature generation. Our scheme also satisfies anonymity, trace ability and non-frame ability requirements.
Bitcoin is a decentralized payment system that relies on Proof-of-Work (PoW) to verify payments. Nowadays, Bitcoin is increasingly used in a number of fast payment scenarios, where the time between the exchange of currency and goods is short (in the order of few seconds). While the Bitcoin payment verification scheme is designed to prevent double-spending, our results show that the system requires tens of minutes to verify a transaction and is therefore inappropriate for fast payments. An example of this use of Bitcoin was recently reported in the media: Bitcoins were used as a form of \emph{fast} payment in a local fast-food restaurant. Until now, the security of fast Bitcoin payments has not been studied. In this paper, we analyze the security of using Bitcoin for fast payments. We show that, unless appropriate detection techniques are integrated in the current Bitcoin implementation, double-spending attacks on fast payments succeed with overwhelming probability and can be mounted at low cost. We further show that the measures recommended by Bitcoin developers for the use of Bitcoin in fast payments are not always effective in detecting double-spending; we show that if those recommendations are integrated in future Bitcoin implementations, double-spending attacks on Bitcoin will still be possible. Finally, we propose and implement a modification to the existing Bitcoin implementation that ensures the detection of double-spending attacks against fast payments.
Malware and botnets are one of the most serious threats to today's Internet security. In this paper, we characterise the so-called "Miner Botnet". It received major media attention after massive distributed denial of service attacks against a wide range of German and Russian websites, mainly during August and September 2011. We use our insights on this botnet to outline current botnet-related money-making concepts and to show that multiple activities of this botnet are actually centred on the virtual anonymised currency Bitcoin, thus justifying the name. Furthermore, we provide a binary-level analysis of the malware's design and components to illustrate the modularity of the previously mentioned concepts. We give an overview of the structure of the command-and-control protocol as well as of the botnet's architecture. Both centralised as well as distributed infrastructure aspects realised through peer-to-peer are present to run the botnet, the latter for increasing its resiliency. Finally, we provide the results of our ongoing tracking efforts that started in September 2011, focusing on the development of the botnet's size and geographic distribution. In addition we point out the challenge that is generally connected with size measurements of botnets due to the reachability of individual nodes and the persistence of IP addresses over time.
Mark Vinkovits, Erion Elmasllari, Claudio Pastrone
Ubiquitous systems and the Internet of Things (IoT) are on the rise. However, there are issues from businesses and users which hinder the wide-spread application of such systems. In the FP7 EU project ebbits, which deals with integrating IoT into business systems, we collected real-world requirements from participants. From these we designed a complete anonymous network solution including addressing, discovery, authentication and reputation management. Our authentication system relies on Non Interactive Zero Knowledge Proofs augmented for fine granulated access right decisions and accounting. Anonymous reputation is created using reputation tickets, which are obtained through public votings. A reputation ticket is an unforgeable evidence of trustworthiness held by the provider and presented to a consumer on request. Discovery also has to specially be designed for anonymous environments else they leak information about the identity. We provide an attribute based discovery mechanism built with Bloom-filters. Our concept protects privacy but still enables discovery based on partial matches.
Abstract. In TCC 2007, Adida and Wikström proposed a novel approach to shuffle, called a public shuffle, in which a shuffler can perform shuffle publicly without needing information kept secret. Their scheme uses an encrypted permutation matrix to shuffle ciphertexts publicly. This approach significantly reduces the cost of constructing a mix-net to verifiable joint decryption. Though their method is successful in making shuffle to be a public operation, their scheme still requires that some trusted parties should choose a permutation to be encrypted and construct zero-knowledge proofs on the well-formedness of this permutation. In this paper, we propose a method to construct a public shuffle without relying on permutations and randomizers generated privately: Given an n-tuple of ciphertext (c1,..., cn), our shuffle algorithm computes fi(c1,..., cn) for i = 1,..., ℓ where each fi(x1,..., xn) is a symmetric polynomial in x1,..., xn. Depending on the symmetric polynomials we use, we propose two concrete constructions. One is to use ring homomorphic encryption with constant ciphertext complexity and the other is to use simple ElGamal encryption with linear ciphertext complexity in the number of senders. Both constructions are free of zero-knowledge proofs and publicly verifiable.
To enhance user privacy, anonymous credential systems allow the user to convince a verifier of the possession of a certificate issued by the issuing authority anonymously. The typical application is the privacy-enhancing electronic ID (eID). Although a previously proposed system achieves the constant complexity in the number of finite-set attributes of the user, it requires the use of RSA. In this paper, we propose a pairing-based anonymous credential system excluding RSA that achieves the constant complexity. The key idea of our proposal is the adoption of a pairing-based accumulator that outputs a constant-size value from a large set of input values. Using zero-knowledge proofs of pairing-based certificates and accumulators, any AND and OR relation can be proved with the constant complexity in the number of finite-set attributes. We implement the proposed system using the fast pairing library, compare the efficiency with the conventional systems, and show the practicality in a mobile eID application.
Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, Daniele Venturi
The Fiat-Shamir transform is a well studied paradigm for removing interaction from publiccoin protocols. We investigate whether the resulting non-interactive zero-knowledge (NIZK) proof systems also exhibit non-malleability properties that have up to now only been studied for NIZK proof systems in the common reference string model: first, we formally define simulation soundness and a weak form of simulation extraction in the random oracle model (ROM). Second, we show that in the ROM the Fiat-Shamir transform meets these properties under lenient conditions. A consequence of our result is that, in the ROM, we obtain truly efficient non malleable NIZK proof systems essentially for free. Our definitions are sufficient for instantiating the Naor-Yung paradigm for CCA2-secure encryption, as well as a generic construction for signature schemes from hard relations and simulation-extractable NIZK proof systems. These two constructions are interesting as the former preserves both the leakage resilience and key-dependent message security of the underlying CPA-secure encryption scheme, while the latter lifts the leakage resilience of the hard relation to the leakage resilience of the resulting signature scheme.
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
Malleability for cryptography is not necessarily an opportunity for attack, but in many cases a potentially useful feature that can be exploited. In this work, we examine notions of malleability for non-interactive zero-knowledge (NIZK) proofs. We start by defining a malleable proof system, and then consider ways to meaningfully control the malleability of the proof system, as in many settings we would like to guarantee that only certain types of transformations can be performed. We also define notions for the cases in which we do not necessarily want a user to know that a proof has been obtained by applying a particular transformation; these are analogous to function/circuit privacy for encryption. As our motivating application, we consider a shorter proof for verifiable shuffles. Our controlled-malleable proofs allow us for the first time to use one compact proof to prove the correctness of an entire multi-step shuffle. Each authority takes as input a set of encrypted votes and a controlled-malleable NIZK proof that these are a shuffle of the original encrypted votes submitted by the voters; it then permutes and re-randomizes these votes and updates the proof by exploiting its controlled malleability. As another application, we generically use controlled-malleable proofs to realize a strong notion of encryption security. Finally, we examine malleability in existing proof systems and observe that Groth-Sahai proofs are malleable. We then go beyond this observation by characterizing all the ways in which they are malleable, and use them to efficiently instantiate our generic constructions from above; this means we can instantiate our proofs and all their applications using only the Decision Linear (DLIN) assumption. Work done as an intern at Microsoft Research Redmond
Bitcoin is a decentralized payment system that is basedonProof-of-Work. Bitcoiniscurrentlygaining popularity as a digital currency; several businesses are starting to accept Bitcoin transactions. An examplecaseofthegrowinguseofBitcoinwasrecently reported in the media; here, Bitcoins were used as a form of fast payment in a local fast-food restaurant. In this paper, we analyze the security of using Bitcoin for fast payments, where the time between the exchange of currency and goods is short (i.e., in the order of few seconds). We focus on doublespending attacks on fast payments and demonstrate that these attacks can be mounted at low cost on currently deployed versions of Bitcoin. We further showthatthemeasuresrecommendedbyBitcoindevelopersfortheuseofBitcoininfasttransactionsare not always effective in resisting double-spending; we show that if those recommendations are integrated in future Bitcoin implementations, double-spending attacks on Bitcoin will still be possible. Finally, we leverage on our findings and propose a lightweight countermeasurethatenablesthedetectionofdoublespending attacks in fast transactions. 1
Anonymous credential systems allow users to obtain certified credentials (a driving license, a student card, etc.) from organizations and then later to prove the possession of one (or more) credential(s) to another party, while minimizing the information given to the latter. While current constructions use zero-knowledge proofs of knowledge of a signature or blinding mechanisms, we keep in this paper a new approach, based on aggregate signature schemes.
Vote validity proof and verification is an efficiency bottleneck and privacy drawback in homomorphic e-voting. The existing vote validity proof technique is inefficient and only achieves honest-verifier zero knowledge. In this paper, an efficient proof and verification technique is proposed to guarantee vote validity in homomorphic e-voting. The new proof technique is mainly based on hash function operations that only need a very small number of costly public key cryptographic operations. It can handle untrusted verifiers and achieve stronger zero knowledge privacy. As a result, the efficiency and privacy of homomorphic e-voting applications will be significantly improved.