Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given value. We give physical algorithms to realize zero-knowledge proofs for these games which allow a player to show that he knows a solution without revealing it. These interactive proofs can be realized with simple office material as they only rely on cards and envelopes. Moreover, we formalize our algorithms and prove their security.
Broadbent Anne, Zhengfeng Ji, Song Fang, Watrous John
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.
Bitcoin, a decentralized cryptocurrency, has attracted a lot of attention from academia, financial service industry and enthusiasts. The trade-off between transaction confirmation throughput and centralization of hash power do not allow Bitcoin to perform at the same level as modern payment systems. Block Advertisement Protocol is proposed as a step to resolve this issue. The protocol allows block mining and block relaying to happen in parallel. The protocol dictates a miner to advertise the block it is going to mine allowing other miners to collect all the transactions in advance. When a block in mined, only header is relayed since most of data about the block is already known to all miners.
Kaylash Chaudhary, Ansgar Fehnker, Jaco van de Pol, Mariëlle Stoelinga
Bitcoin is a popular digital currency for online payments, realized as a decentralized peer-to-peer electronic cash system. Bitcoin keeps a ledger of all transactions; the majority of the participants decides on the correct ledger. Since there is no trusted third party to guard against double spending, and inspired by its popularity, we would like to investigate the correctness of the Bitcoin protocol. Double spending is an important threat to electronic payment systems. Double spending would happen if one user could force a majority to believe that a ledger without his previous payment is the correct one. We are interested in the probability of success of such a double spending attack, which is linked to the computational power of the attacker. This paper examines the Bitcoin protocol and provides its formalization as an UPPAAL model. The model will be used to show how double spending can be done if the parties in the Bitcoin protocol behave maliciously, and with what probability double spending occurs.
The Bitcoin system is an anonymous, decentralized crypto-currency. There are some deanonymizating techniques to cluster Bitcoin addresses and to map them to users' identifications in the two research directions of Analysis of Transaction Chain (ATC) and Analysis of Bitcoin Protocol and Network (ABPN). Nowadays, there are also some anonymization methods such as coin-mixing and transaction remote release (TRR) to cover the relationship between Bitcoin address and the user. This paper studies anonymization and de-anonymization technologies and proposes some directions for further research.
To strengthen the anonymity of Bitcoin, several centralized coin-mixing providers (mixers) such as BitcoinFog.com, BitLaundry.com, and Blockchain.info assist users to mix Bitcoins through CoinJoin transactions with multiple inputs and multiple outputs to uncover the relationship between them. However, these mixers know the output address of each user, such that they cannot provide true anonymity. This paper proposes a centralized coin-mixing algorithm based on an elliptic curve blind signature scheme (denoted as Blind-Mixing) that obstructs mixers from linking an input address with an output address. Comparisons among three blind signature based algorithms, Blind-Mixing, BlindCoin, and RSA Coin-Mixing, are conducted. It is determined that BlindCoin may be deanonymized because of its use of a public log. In RSA Coin-Mixing, a user's Bitcoins may be falsely claimed by another. In addition, the blind signature scheme of Blind-Mixing executes 10.5 times faster than that of RSA Coin-Mixing.
Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, Robbert van Renesse
Cryptocurrencies, based on and led by Bitcoin, have shown promise as infrastructure for pseudonymous online payments, cheap remittance, trustless digital asset exchange, and smart contracts. However, Bitcoin-derived blockchain protocols have inherent scalability limits that trade-off between throughput and latency and withhold the realization of this potential. This paper presents Bitcoin-NG, a new blockchain protocol designed to scale. Based on Bitcoin's blockchain protocol, Bitcoin-NG is Byzantine fault tolerant, is robust to extreme churn, and shares the same trust model obviating qualitative changes to the ecosystem. In addition to Bitcoin-NG, we introduce several novel metrics of interest in quantifying the security and efficiency of Bitcoin-like blockchain protocols. We implement Bitcoin-NG and perform large-scale experiments at 15% the size of the operational Bitcoin system, using unchanged clients of both protocols. These experiments demonstrate that Bitcoin-NG scales optimally, with bandwidth limited only by the capacity of the individual nodes and latency limited only by the propagation time of the network.
The anonymity of the Bitcoin system has some shortcomings. Analysis of Transaction Chain (ATC) and Analysis of Bitcoin Protocol and Network (ABPN) are two important methods of deanonymizing bitcoin transactions. Nowadays, there are some anonymization methods to combat ATC but there has been little research into ways to counter ABPN. This paper proposes a new anonymization technology called Transaction Remote Release (TRR). Inspired by The Onion Router (TOR), TRR is able to render several typical attacking methods of ABPN ineffective. Furthermore, the performance of encryption and decryption of TRR is good and the growth rate of the cipher is very limited. Hence, TRR is suited for practical applications.
Open access
2 source records
cs.CR
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
This Request For Comment (RFC) is a proposal for a new protocol to use money over the Internet. Features like a distributed architecture, a published cryptographic algorithm, a minimal authority responsibility, the absence of fees will make this protocol a perfect tool for citizens in today's digital World. An implementation has validated the main principles and we entering now a testing phase (v0.1). Depending of the results, a released date for the 1.0 revision will to decided to allow anybody to send or to receive money to/from anyone, in any currency, with a regular and personal smart-phone. A distributed hash table (DHT) is used to store all transactions, public keys and certificates redundantly on several nodes. The all system may replace coins, banknotes and classical checks in the future. We also argue that the Bitcoin technology does not satisfy the requirements for a digital mean of payment. This proposal is expected to be reviewed and commented by the Internet Engineering Task Force.
A homomorphic public key crypto-scheme based on the Boolean Satisfiability Problem is proposed. The public key is a SAT formula satisfied by the private key. Probabilistic encryption generates functions implied to be false by the public key XOR the message bits. A zero-knowledge proof is used to provide signatures.
Bitcoin is a decentralized crypto-currency, and an accompanying protocol, created in 2008. Bitcoin nodes continuously generate and propagate blocks---collections of newly approved transactions that are added to Bitcoin's ledger. Block creation requires nodes to invest computational resources, but also carries a reward in the form of bitcoins that are paid to the creator. While the protocol requires nodes to quickly distribute newly created blocks, strong nodes can in fact gain higher payoffs by withholding blocks they create and selectively postponing their publication. The existence of such selfish mining attacks was first reported by Eyal and Sirer, who have demonstrated a specific deviation from the standard protocol (a strategy that we name SM1). In this paper we extend the underlying model for selfish mining attacks, and provide an algorithm to find $ε$-optimal policies for attackers within the model, as well as tight upper bounds on the revenue of optimal policies. As a consequence, we are able to provide lower bounds on the computational power an attacker needs in order to benefit from selfish mining. We find that the profit threshold -- the minimal fraction of resources required for a profitable attack -- is strictly lower than the one induced by the SM1 scheme. Indeed, the policies given by our algorithm dominate SM1, by better regulating attack-withdrawals. Using our algorithm, we show that Eyal and Sirer's suggested countermeasure to selfish mining is slightly less effective than previously conjectured. Next, we gain insight into selfish mining in the presence of communication delays, and show that, under a model that accounts for delays, the profit threshold vanishes, and even small attackers have incentive to occasionally deviate from the protocol. We conclude with observations regarding the combined power of selfish mining and double spending attacks.
We survey recent results on the mathematical stability of Bitcoin protocol. Profitability and probability of a double spend are estimated in closed form with classical special functions. The stability of Bitcoin mining rules is analyzed and several theorems are proved using martingale and combinatorics techniques. In particular, the empirical observation of the stability of the Bitcoin protocol is proved. This survey article on the mathematics of Bitcoin is published by the Newsletter of the European Mathematical Society, vol.115, 2020, p.31-37. Continuation of arXiv:1601.05254 (EMS Newsletter, 100, 2016 p.32).
A peer-to-peer network, enabling different parties to jointly store and run computations on data while keeping the data completely private. Enigma's computational model is based on a highly optimized version of secure multi-party computation, guaranteed by a verifiable secret-sharing scheme. For storage, we use a modified distributed hashtable for holding secret-shared data. An external blockchain is utilized as the controller of the network, manages access control, identities and serves as a tamper-proof log of events. Security deposits and fees incentivize operation, correctness and fairness of the system. Similar to Bitcoin, Enigma removes the need for a trusted third party, enabling autonomous control of personal data. For the first time, users are able to share their data with cryptographic guarantees regarding their privacy.
This paper describes the process of remaining anonymous online and its concurrent operational security that has to be performed. It focusses particularly on remaining anonymous while purchasing online goods, resulting in anonymously bought items. Different aspects of the operational security process as well as anonymously funding with cryptocurrencies are described. Eventually it is shown how to anonymously purchase items and services from the hidden web, as well as the delivery. It is shown that, while becoming increasingly difficult, it is still possible to make anonymous purchases. Our presented work combines existing best-practices and deliberately avoids untested novel approaches when possible.
Current cryptocurrencies, starting with Bitcoin, build a decentralized blockchain-based transaction ledger, maintained through proofs-of-work that also serve to generate a monetary supply. Such decentralization has benefits, such as independence from national political control, but also significant limitations in terms of computational costs and scalability. We introduce RSCoin, a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authorities, or mintettes, to prevent double-spending. While monetary policy is centralized, RSCoin still provides strong transparency and auditability guarantees. We demonstrate, both theoretically and experimentally, the benefits of a modest degree of centralization, such as the elimination of wasteful hashing and a scalable system for avoiding doublespending attacks.
Johannes Göbel, Paul Keeler, A. E. Krzesinski, Peter Taylor
In the context of the `selfish-mine' strategy proposed by Eyal and Sirer, we study the effect of propagation delay on the evolution of the Bitcoin blockchain. First, we use a simplified Markov model that tracks the contrasting states of belief about the blockchain of a small pool of miners and the `rest of the community' to establish that the use of block-hiding strategies, such as selfish-mine, causes the rate of production of orphan blocks to increase. Then we use a spatial Poisson process model to study values of Eyal and Sirer's parameter $γ$, which denotes the proportion of the honest community that mine on a previously-secret block released by the pool in response to the mining of a block by the honest community. Finally, we use discrete-event simulation to study the behaviour of a network of Bitcoin miners, a proportion of which is colluding in using the selfish-mine strategy, under the assumption that there is a propagation delay in the communication of information between miners.
Trusted timestamping is a process for proving that certain information existed at a given point in time. This paper presents a trusted timestamping concept and its implementation in form of a web-based service that uses the decentralized Bitcoin block chain to store anonymous, tamper-proof timestamps for digital content. The service allows users to hash files, such as text, photos or videos, and store the created hashes in the Bitcoin block chain. Users can then retrieve and verify the timestamps that have been committed to the block chain. The non-commercial service enables anyone, e.g., researchers, authors, journalists, students, or artists, to prove that they were in possession of certain information at a given point in time. Common use cases include proving that a contract has been signed, a photo taken, a video recorded, or a task completed prior to a certain date. All procedures maintain complete privacy of the user's data.
Open access
2 source records
Advanced Steganography and Watermarking Techniques
The ability to assess the reputation of a member in a web community is a need addressed in many different ways according to the many different stages in which the nature of communities has evolved over time. In the case of reputation of goods/services suppliers, the solutions available to prevent the feedback abuse are generally reliable but centralized under the control of few big Internet companies. In this paper we show how a decentralized and distributed feedback management system can be built on top of the Bitcoin blockchain
Bitcoins have recently become an increasingly popular cryptocurrency through which users trade electronically and more anonymously than via traditional electronic transfers. Bitcoin's design keeps all transactions in a public ledger. The sender and receiver for each transaction are identified only by cryptographic public-key ids. This leads to a common misconception that it inherently provides anonymous use. While Bitcoin's presumed anonymity offers new avenues for commerce, several recent studies raise user-privacy concerns. We explore the level of anonymity in the Bitcoin system. Our approach is two-fold: (i) We annotate the public transaction graph by linking bitcoin public keys to "real" people - either definitively or statistically. (ii) We run the annotated graph through our graph-analysis framework to find and summarize activity of both known and unknown users.
Sidecoin is a mechanism that allows a snapshot to be taken of Bitcoin's blockchain. We compile a list of Bitcoin's unspent transaction outputs, then use these outputs and their corresponding balances to bootstrap a new blockchain. This allows the preservation of Bitcoin's economic state in the context of a new blockchain, which may provide new features and technical innovations.
ECDSA has become a popular choice as lightweight alternative to RSA and classic DL based signature algorithms in recent years. As standardized, the signature produced by ECDSA for a pair of a message and a key is not deterministic. This work shows how this non-deterministic choice can be exploited by an attacker to leak private information through the signature without any side channels, an attack first discovered by Young and Yung for classic DL-based cryptosystems in 1997, and how this attack affects the application of ECDSA in the Bitcoin protocol.
Kourosh Davarpanah, Dan Kaufman, Ophelie Pubellier
NeuCoin is a decentralized peer-to-peer cryptocurrency derived from Sunny\nKing's Peercoin, which itself was derived from Satoshi Nakamoto's Bitcoin. As\nwith Peercoin, proof-of-stake replaces proof-of-work as NeuCoin's security\nmodel, effectively replacing the operating costs of Bitcoin miners\n(electricity, computers) with the capital costs of holding the currency.\nProof-of-stake also avoids proof-of-work's inherent tendency towards\ncentralization resulting from competition for coinbase rewards among miners\nbased on lowest cost electricity and hash power.\n NeuCoin increases security relative to Peercoin and other existing\nproof-of-stake currencies in numerous ways, including: (1) incentivizing nodes\nto continuously stake coins over time through substantially higher mining\nrewards and lower minimum stake age; (2) abandoning the use of coin age in the\nmining formula; (3) causing the stake modifier parameter to change over time\nfor each stake; and (4) utilizing a client that punishes nodes that attempt to\nmine on multiple branches with duplicate stakes.\n This paper demonstrates how NeuCoin's proof-of-stake implementation addresses\nall commonly raised "nothing at stake" objections to generic proof-of-stake\nsystems. It also reviews many of the flaws of proof-of-work designs to\nhighlight the potential for an alternate cryptocurrency that solves these\nflaws.\n
Gareth W. Peters, Efstathios Panayi, Ariane Chapelle
The internet era has generated a requirement for low cost, anonymous and rapidly verifiable transactions to be used for online barter, and fast settling money have emerged as a consequence. For the most part, e-money has fulfilled this role, but the last few years have seen two new types of money emerge. Centralised virtual currencies, usually for the purpose of transacting in social and gaming economies, and crypto-currencies, which aim to eliminate the need for financial intermediaries by offering direct peer-to-peer online payments. We describe the historical context which led to the development of these currencies and some modern and recent trends in their uptake, in terms of both usage in the real economy and as investment products. As these currencies are purely digital constructs, with no government or local authority backing, we then discuss them in the context of monetary theory, in order to determine how they may be have value under each. Finally, we provide an overview of the state of regulatory readiness in terms of dealing with transactions in these currencies in various regions of the world.
PGP is built upon a Distributed Web of Trust in which the trustworthiness of a user is established by others who can vouch through a digital signature for that particular identity. Preventing its wholesale adoption are a number of inherent weaknesses to include (but not limited to) the following: 1) Trust Relationships are built on a subjective honor system, 2) Only first degree relationships can be fully trusted, 3) Levels of trust are difficult to quantify with actual values, and 4) Issues with the Web of Trust itself (Certification and Endorsement). Although the security that PGP provides is proven to be reliable, it has largely failed to garner large scale adoption. In this paper, we propose several novel contributions to address the aforementioned issues with PGP and associated Web of Trust. To address the subjectivity of the Web of Trust, we provide a new certificate format based on Bitcoin which allows a user to verify a PGP certificate using Bitcoin identity-verification transactions - forming first degree trust relationships that are tied to actual values (i.e., number of Bitcoins transferred during transaction). Secondly, we present the design of a novel Distributed PGP key server that leverages the Bitcoin transaction blockchain to store and retrieve Bitcoin-Based PGP certificates. Lastly, we provide a web prototype application that demonstrates several of these capabilities in an actual environment.