Privacy-preserving data mining has been an active research area in recent years due to privacy concerns in many distributed data mining settings. Protocols for privacy-preserving data mining have considered semi-honest, malicious, and covert adversarial models in cryptographic settings, whereby an adversary is assumed to follow, arbitrarily deviate from the protocol, or behaving somewhere in between these two, respectively. Semi-honest model provides weak security requiring small amount of computation, on the other hand, malicious and covert models provide strong security requiring expensive computations like homomorphic encryptions. However, game theory allows us to design protocols where parties are neither honest nor malicious but are instead viewed as rational and are assumed (only) to act in their self-interest. In this paper, we build efficient and secure two-party set-intersection protocol in game-theoretic setting using cryptographic primitives. Our construction allow to avoid the use of expensive tools like homomorphic encryption and zero knowledge proof. We also show that our protocol satisfies computational versions of strict Nash equilibrium and stability with respect to trembles. Povzetek: Predstavljen je protokol med dvema stranema na osnovi Nashevega ravnoteÂja.
The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001). An alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlinâs transformation can be applied to any so called 3-round âFiat-Shamir proof of knowledgeâ â and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to
In cloud storage service, clients upload their data together with authentication information to cloud storage server. To ensure the availability and integrity of clients' stored data, cloud server(CS) must prove to a verifier that he is actually storing all of the client's data unchanged. And, enabling public auditability for cloud storage is of critical importance to users with constrained computing resources, who can resort to a third party auditor (TPA) to check the integrity of outsourced data. However, most of the existing proofs of retrievability schemes or proof of data possession schemes do not consider data privacy problem. Zero knowledge privacy requires TPA or the adversary can not deduce any information of the file data from auditing system. In this paper, after giving a new construction of a recently proposed cryptographic primitive named aggregatable signature based broadcast (ASBB) encryption scheme, we present an efficient public auditing scheme with zero knowledge privacy. The new scheme is as efficient as the scheme presented by Shacham and Waters without considering privacy and is secure in the random oracle model.
In the standard definition of a commitment scheme, the sender commits to a message and immediately sends the commitment to the recipient interested in it. However the sender may not always know at the time of commitment who will become interested in it. Further, when the interested party does emerge, it could be critical to establish when the commitment was made. Employing a proof of work protocol at commitment time will later allow anyone to carbon date when the commitment was made, approximately, without trusting any external parties. We present CommitCoin, an instantiation of this approach that harnesses the existing computational power of the Bitcoin peer-to-peer network; a network used to mint and trade digital cash.
In a world that relies heavily on technology, privacy is sought by many. Privacy, among other things, is especially desired when making an online payment. This motivates the use of electronic cash, a form of electronic payment system based on the paper cash system used daily. The most successful and widely used of these services is Bitcoin â a decentralized peer-to-peer electronic cash system. This paper provides a broad introduction to Bitcoin, while analyzing its construction and investigating some of its perks and flaws. It can be seen that, when compared to paper cash and electronic cash, Bitcoin is in a class of its own.
In 2009, a curious new virtual currency called Bitcoin made its first appearance on the Internet. While it remains a ânicheâ currency relative to other major denominations like the U.S. dollar, Bitcoin has experienced significant growth since its inception. The total number of Bitcoins in circulation is about 12.5 million, with a recent market price of about $500 each. Today, Bitcoinâs total market capitalization is about $6 billion, and in the past it has been as high as $13 billion. The average number of Bitcoin transactions per day has averaged over 60,000 since January 2014, reflecting between $20 million and $100 million worth of transactions per day. The numbers show that in the five years since its first appearance, Bitcoin has grown tremendously in popular knowledge and usage. Although it is clear that Bitcoin can be used to purchase goods and services, and can be given an explicit dollar value, questions remain about the economic and legal status of Bitcoin and other virtual currencies that have emerged in its wake. Members of the Bitcoin developer and user community believe âBitcoin is an innovative payment network and new kind of money.â Others, like the U.S. Internal Revenue Service, take the position that Bitcoin is a type of commodity or property. Whether Bitcoin is a new form of virtual money or simply an electronic commodity requires an investigation into what constitutes money, and an assessment of whether Bitcoin comfortably fits into the parameters of what we consider to be money. This paper finds that, at this stage in its development, Bitcoin is not money and more closely resembles a commodity or property. This paper begins by giving a brief overview of Bitcoin and how it operates. It then describes two major theories of money â the conventional and constitutional theories â that differ in their accounts of how money emerges within a society or political grouping. The paper assesses how well Bitcoin fits under each theory by assessing Bitcoinâs economic properties and implementation. It then turns to the impact of the Bitcoin on the two theories of money, finding it likely does not support the conventional creation story of money and instead lends credence to the constitutional theory.
A peer-to-peer crypto-currency design derived from Satoshi Nakamotoâs Bitcoin. Proof-of-stake replaces proof-of-work to provide most of the network security. Under this hybrid design proof-of-work mainly provides initial minting and is largely non-essential in the long run. Security level of the network is not dependent on energy consumption in the long term thus providing an energyefficient and more cost-competitive peer-to-peer crypto-currency. Proof-of-stake is based on coin age and generated by each node via a hashing scheme bearing similarity to Bitcoinâs but over limited search space. Block chain history and transaction settlement are further protected by a centrally broadcasted checkpoint mechanism.
In 1601, Elizabeth I and her government devalued the Irish coin from nine ounces fine to three ounces fine of silver in order to finance the high cost of the Nine Years War in Ireland. 1 This unilateral move by the English government, combined with the failure to remove the old sterling from circulation, caused catastrophic problems throughout Ireland. 2 In addition to rapid inflation in common foodstuffs, the people in Ireland would only accept the new coin at its reduced intrinsic value rather than face value. 3 Further, merchants refused to accept the devalued coin in commercial transactions leading to a shortage of vital goods from England. 4
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
Simon Barber, Xavier Boyen, Elaine Shi, Ersin Uzun
Abstract. Bitcoin is a distributed digital currency which has attracted a substan-tial number of users. We perform an in-depth investigation to understand what made Bitcoin so successful, while decades of research on cryptographic e-cash has not lead to a large-scale deployment. We ask also how Bitcoin could become a good candidate for a long-lived stable currency. In doing so, we identify several issues and attacks of Bitcoin, and propose suitable techniques to address them. 1
Abstract. Bitcoin is quickly emerging as a popular digital payment system. However, in spite of its reliance on pseudonyms, Bitcoin raises a number of privacy concerns due to the fact that all of the transactions that take place are publicly announced in the system. In this paper, we investigate the privacy guarantees of Bitcoin in the setting where Bitcoin is used as a primary currency for the daily transactions of individuals. More specifically, we evaluate the privacy that is provided by Bitcoin (i) by analyzing the genuine Bitcoin system and (ii) through a simulator that faithfully mimics the operation of Bitcoin in the context where Bitcoin is used for all transactions within a university. In this setting, our results show that the profiles of almost 40 % of the users can be, to a large extent, recovered even when users adopt privacy measures recommended by Bitcoin. To the best of our knowledge, this is the first work that comprehensively analyzes, and evaluates the privacy implications of Bitcoin. As a by-product, we have designed and implemented the first simulator of Bitcoin; our simulator can be used to model the interaction between Bitcoin users in generic settings. 1
Abstract. The Bitcoin scheme is a rare example of a large scale global payment system in which all the transactions are publicly accessible (but in an anonymous way). We downloaded the full history of this scheme, and analyzed many statistical properties of its associated transaction graph. In this paper we answer for the first time a variety of interesting questions about the typical behavior of users, how they acquire and how they spend their bitcoins, the balance of bitcoins they keep in their accounts, and how they move bitcoins between their various accounts in order to better protect their privacy. In addition, we isolated all the large transactions in the system, and discovered that almost all of them are closely related to a single large transaction that took place in November 2010, even though the associated users apparently tried to hide this fact with many strange looking long chains and fork-merge structures in the transaction graph.
Bitcoin is a digital, decentralized, partially anonymous currency, not backed by any government or other legal entity, and not redeemable for gold or other commodity. It relies on peer-to-peer networking and cryptography to maintain its integrity. Compared to most currencies or online payment services, such as PayPal, bitcoins are highly liquid, have low transaction costs, and can be used to make micropayments. This new currency could also hold the key to allowing organizations such as Wikileaks, hated by governments, to receive donations and conduct business anonymously. Although the Bitcoin economy is flourishing, Bitcoin users are anxious about Bitcoin's legal status. This Article examines a few relevant legal issues, such as the recent conviction of the Liberty Dollar creator, the Stamp Payments Act, and the Federal Securities Acts.
Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar
Many large decentralized systems rely on information propagation to ensure their proper function. We examine a common scenario in which only participants that are aware of the information can compete for some reward, and thus informed participants have an incentive not to propagate information to others. One recent example in which such tension arises is the 2009 DARPA Network Challenge (finding red balloons). We focus on another prominent example: Bitcoin, a decentralized electronic currency system. Bitcoin represents a radical new approach to monetary systems. It has been getting a large amount of public attention over the last year, both in policy discussions and in the popular press. Its cryptographic fundamentals have largely held up even as its usage has become increasingly widespread. We find, however, that it exhibits a fundamental problem of a different nature, based on how its incentives are structured. We propose a modification to the protocol that can eliminate this problem. Bitcoin relies on a peer-to-peer network to track transactions that are performed with the currency. For this purpose, every transaction a node learns about should be transmitted to its neighbors in the network. The current implemented protocol provides an incentive to nodes to not broadcast transactions they are aware of. Our solution is to augment the protocol with a scheme that rewards information propagation. Since clones are easy to create in the Bitcoin system, an important feature of our scheme is Sybil-proofness. We show that our proposed scheme succeeds in setting the correct incentives, that it is Sybil-proof, and that it requires only a small payment overhead, all this is achieved with iterated elimination of dominated strategies. We complement this result by showing that there are no reward schemes in which information propagation and no self-cloning is a dominant strategy.
⢠Electronic financial transactions and payment systems have traditionally relied on third party institutions, such as banks or credit card companies, to ensure secure transfers between parties. Users of such systems must trust that third party institutions will be honest and follow through with their claims. Trust-based systems are difficult to establish in the digital realm without a governing body regulating and securing transfers. Systems using this model have many downfalls that make them risky and undesirable for Internet use. With the requirement of all transactions being completely digital, how can we transfer funds securely without a trusted third party?
⢠All types of currencies share many common problems such as stability, control, and inflation. As time passes, the relative value of a currency usually decreases (meaning that prices increase). If this happens too quickly, it can cause major problems if prices increase beyond the means of the populace who uses the currency. Another problem is stability because the currency should not be subject to dramatic exchange rate fluctuations under the influence of a single individual or party. Control over a currency, or lack thereof, is also important. Typical fiat currencies depend on a mint and the promise that the mint will continue its operations. If the mint were to close indefinitely, the currency would likely die out in a relatively short period of time. Therefore, the mint has some level of control over the currency.
⢠Bitcoin is a digital currency introduced in 2009, based on a self-published paper by Satoshi Nakamoto[1]. Bitcoin enables payments that are based on proof, rather than trust, in a manner that is similar to cash. A seller given a cash payment can inspect the currency and, with a good degree of confidence, assert whether the payment is valid or invalid. Bitcoins works using a similar concept that make coins and coin ownership easy to verify. An important difference between this virtual currency and typical fiat currency is that Bitcoin's validity can be verified.
⢠During this workshop we showed attendees the verification process as well as the algorithms and technologies that make verification possible. The audience learned about online money transaction, then analyzed standard techniques and form comparisons between them. The workshop then proceeded to discuss the history and purpose of Bitcoins along with an overview of its concepts and terminologies.
⢠The workshop continues to compare Bitcoins with other transaction techniques discussed and talk about the pros and the cons. We also go though the problems that Bitcoin will be able to solve and what new problems it will introduce.
⢠Attendees will learn the details of Bitcoins and its implementations. From Asymmetric cryptography algorithms to hashing and digital signatures to proof of work, the audience will be walked though all the technologies that make Bitcoin possible.
⢠The workshop will take attendees through actual Bitcoin transactions and the details of the transaction process as it will allow them to see how the Bitcoin system overcome problems such as double spending. The audience was also taught about Bitcoin generation and how Bitcoins are generated out of thin air. For context, we covered how much coins are worth and how people are already profiting from services other than mining. The details of Bitcoin blocks and chains were demystified in a manner that was detailed but simple to understand.
⢠The Bitcoin network was one of the main focuses - how a distributed and completely public network can maintain the anonymity of its users. It was discussed in detail about how transactions are validated through the network and about the transaction databases that is on the distributed network. The audience learned how the distributed database handles failures, delay, and is able to work effectively with only a subset of the entire database. The audience learned concepts such as merkle trees and how they help the Bitcoin network to maintain the database. We answer questions such as how Bitcoins control the expansion of its own currency when the Bitcoin network may double in size in a short period of time. The many interesting characteristics of the network were unveiled during this engaging demonstration.
⢠Attacks and malicious hosts are constantly a threat to modern day electronic transactional systems and this also applies to Bitcoin. We mapped out the architectural features that make Bitcoin naturally resilient to many common attacks, as well as the features that make it vulnerable. We discussed possible attacks on the Bitcoin network as well as attack mitigation and ways in which end users can protect themselves.
⢠Another interesting issue is anonymity. Bitcoin is regarded as being anonymous by many people, yet Bitcoins can be traced from the original miner all the way to the current owner. A Bitcoin address itself is just a number and cannot identify anyone. However if a person manages to collect enough information about the owner of that address (perhaps through forums) then the owner can be exposed.
⢠To conclude, in this workshop we explored everything from cryptographic algorithms to the massive peer-to-peer network. We took a security perspective for an in-depth exploration of Bitcoin attacks and attack mitigation. We ended our workshop with a look at how Bitcoin might change the e-commerce landscape, followed by an open discussion.
Anonymity in Bitcoin, a peer-to-peer electronic currency system, is a complicated issue. Within the system, users are identified by public-keys only. An attacker wishing to de-anonymize its users will attempt to construct the one-to-many mapping between users and public-keys and associate information external to the system with the users. Bitcoin tries to prevent this attack by storing the mapping of a user to his or her public-keys on that user's node only and by allowing each user to generate as many public-keys as required. In this chapter we consider the topological structure of two networks derived from Bitcoin's public transaction history. We show that the two networks have a non-trivial topological structure, provide complementary views of the Bitcoin system and have implications for anonymity. We combine these structures with external information and techniques such as context discovery and flow analysis to investigate an alleged theft of Bitcoins, which, at the time of the theft, had a market value of approximately half a million U.S. dollars.
Paulo NovĂĄis, Francisco Andrade, JosĂŠ Machado, JosĂŠ Neves
Inter-systemic contracting may be based upon autonomous intelligent behaviour. Autonomy is an important advantage of software agents. Yet, it brings along several issues concerning the legal consideration (e.g. legal personality/attribution) and the legal consequences of software agentâs behaviour. The intervention of software agents in corporate bodies and the consideration of its roles must also be referred. All this intends interactions based on contracts and relations of trust, at an individual, at a community and at a systemic level. In this regard, it does make sense to speak of the relation between good faith and trust in inter-systemic contracting. And at the systemic level there is a need to focus on special protocols intended to enhance trust in electronic commerce. Chapter 12 proposes smart contracts as a way of enhancing trust and of achieving enforcement in electronic contracting.