Financial Cryptography and Data Security

In this paper, we compute hundreds of Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS private keys by carrying out cryptanalytic attacks against digital signatures contained in public blockchains and Internet-wide scans. The ECDSA signature algorithm requires the generation of a per-message secret nonce. If this nonce is not generated uniformly at random, an attacker can potentially exploit this bias to compute the long-term signing key. We use a lattice-based algorithm for solving the hidden number problem to efficiently compute private ECDSA keys that were used with biased signature nonces due to multiple apparent implementation vulnerabilities.

We present the a provably secure proof-of-stake protocol called Snow White. The primary application of Snow White is to be used as a “green” consensus alternative for a decentralized cryptocurrency system with open enrollement. We break down the task of designing Snow White into the following core challenges: 1. identify a core “permissioned” consensus protocol suitable for proof-of-stake; specifically the core consensus protocol should offer robustness in an Internet-scale, heterogeneous deployment; 2. propose a robust committee re-election mechanism such that as stake switches hands in the cryptocurrency system, the consensus committee can evolve in a timely manner and always reflect the most recent stake distribution; and 3. relying on the formal security of the underlying consensus protocol, prove the full end-to-end protocol to be secure—more specifically, we show that any consensus protocol satisfying the desired robustness properties can be used to construct proofs-of-stake consensus, as long as money does not switch hands too quickly. Snow White was publicly released in September 2016. It provides the first formal, end-to-end proof of a proof-of-stake system in a truly decentralized, open-participation network, where nodes can join at any time (not necessarily at the creation of the system). We also give the first formal treatment of a well-known issue called “costless simulation” in our paper, proving both upper- and lower-bounds that characterize exactly what setup assumptions are needed to defend against costless simulation attacks. We refer the reader to our detailed chronological notes on a detailed comparison of Snow White and other prior and concurrent works, as well as how subsequent works (including Ethereum’s proof-of-stake design) have since extended and improved our ideas.

Proof-of-stake (PoS) is a promising approach for designing efficient blockchains, where block proposers are randomly chosen with probability proportional to their stake. A primary concern in PoS systems is the “rich getting richer” effect, whereby wealthier nodes are more likely to get elected, and hence reap the block reward, making them even wealthier. In this paper, we introduce the notion of equitability, which quantifies how much a proposer can amplify her stake compared to her initial investment. Even with everyone following protocol (i.e., honest behavior), we show that existing methods of allocating block rewards lead to poor equitability, as does initializing systems with small stake pools and/or large rewards relative to the stake pool. We identify a geometric reward function, which we prove is maximally equitable over all choices of reward functions under honest behavior and bound the deviation for strategic actions; the proofs involve the study of optimization problems and stochastic dominances of Pólya urn processes. These results allow us to provide a systematic framework to choose the parameters of a practical incentive system for PoS cryptocurrencies.

We present a new resource exhaustion attack affecting several chain-based proof-of-stake cryptocurrencies, and in particular Qtum, a top 30 cryptocurrency by market capitalization ($300M as of Sep ’18). In brief, these cryptocurrencies do not adequately validate the proof-of-stake before allocating resources to data received from peers. An attacker can exploit this vulnerability, even without any stake at all, simply by connecting to a victim and sending malformed blocks, which the victim stores on disk or in RAM, eventually leading to a crash. We demonstrate and benchmark the attack through experiments attacking our own node on the Qtum main network; in our experiment we are able to fill the victim’s RAM at a rate of 2MB per second, or the disk at a rate of 6MB per second. We have begun a responsible disclosure of this vulnerability to appropriate development teams. Our disclosure includes a Docker-based reproducibility kit using the Python-based test framework. This problem has gone unnoticed for several years. Although the attack can be mitigated, this appears to require giving up optimizations enjoyed by proof-of-work cryptocurrencies, underscoring the difficulty in implementing and deploying chain-based proof-of-stake.

Interest in cryptocurrencies has skyrocketed since their introduction a decade ago, with hundreds of billions of dollars now invested across a landscape of thousands of different cryptocurrencies. While there is significant diversity, there is also a significant number of scams as people seek to exploit the current popularity. In this paper, we seek to identify the extent of innovation in the cryptocurrency landscape using the open-source repositories associated with each one. Among other findings, we observe that while many cryptocurrencies are largely unchanged copies of Bitcoin, the use of Ethereum as a platform has enabled the deployment of cryptocurrencies with more diverse functionalities.

Temporary blockchain forks are part of the regular consensus process in permissionless blockchains such as Bitcoin. As forks can be caused by numerous factors such as latency and miner behavior, their analysis provides insights into these factors, which are otherwise unknown. In this paper we provide an empirical analysis of the announcement and propagation of blocks that led to forks of the Bitcoin blockchain. By analyzing the time differences in the publication of competing blocks, we show that the block propagation delay between miners can be of similar order as the block propagation delay of the average Bitcoin peer. Furthermore, we show that the probability of a block to become part of the main chain increases roughly linearly in the time the block has been published before the competing block. Additionally, we show that the observed frequency of short block intervals between two consecutive blocks mined by the same miner after a fork is conspicuously large. While selfish mining can be a cause for this observation, other causes are also possible. Finally, we show that not only the time difference of the publication of competing blocks but also their propagation speeds vary greatly.

We propose and compare two approaches to identify smart contracts as token systems by analyzing their public bytecode. The first approach symbolically executes the code in order to detect token systems by their characteristic behavior of updating internal accounts. The second approach serves as a comparison base and exploits the common interface of ERC-20 , the most popular token standard. We present quantitative results for the Ethereum blockchain, and validate the effectiveness of both approaches using a set of curated token systems as ground truth. We observe 100% recall for the second approach. Recall rates of 89% (with well explainable missed detections) indicate that the first approach may also be able to identify “hidden” or undocumented token systems that intentionally do not implement the standard. One possible application of the proposed methods is to facilitate regulators’ tasks of monitoring and policing the use of token systems and their underlying platforms.

The blockchain and cryptocurrency space has experienced tremendous growth in the past few years. Covered by popular media, the phenomenon of startups launching Initial Coin Offerings (ICOs) to raise funds led to hundreds of virtual tokens being distributed and traded on blockchains and exchanges. The trade of tokens among participants of the network yields token networks, whose structure provides valuable insights into the current state and usage of blockchain-based decentralized trading systems. In this paper, we present a descriptive measurement study to quantitatively characterize those networks. Based on the first 6.3 million blocks of the Ethereum blockchain, we provide an overview on more than 64,000 ERC20 token networks and analyze the top 1,000 from a graph perspective. Our results show that even though the entire network of token transfers has been claimed to follow a power-law in its degree distribution, many individual token networks do not: they are frequently dominated by a single hub and spoke pattern. Furthermore, we generally observe very small clustering coefficients and mostly disassortative networks. When considering initial token recipients and path distances to exchanges, we see that a large part of the activity is directed towards these central instances, but many owners never transfer their tokens at all. In conclusion, we believe that our findings about the structure of token distributions on the Ethereum platform may benefit the design of future decentralized asset trade systems and can support and influence regulatory measures.

The cascade effect attacks (PETS’ 18) on the untraceability of Monero are circumvented by two approaches. The first one is to increase the minimum ring size of each input, from 3 (version 0.9.0) to 7 in the latest update (version 0.12.0). The second approach is introducing the ring confidential transactions with enhanced privacy guarantee. However, so far, no formal analysis has been conducted on the level of anonymity provided by the new countermeasures in Monero. In addition, since Monero is only an example of leading CryptoNote-style blockchains, the actual privacy guarantee provided by other similar blockchains in the wild remains unknown.In this paper, we propose a more sophisticated statistical analysis on CryptoNote-style cryptocurrencies. In particular, we introduce a new attack on the transaction untraceability called closed set attack. We prove that our attack is optimal assuming that no additional information is given. In other words, in terms of the result, $$\textit{closed set}$$ attack is equivalent to brute-force attack, which exhausts all possible input choices and removes those that are impossible given the constraints imposed by the mixins of each transaction.To verify the impact of our attack in reality, we conduct experiments on the top 3 CryptoNote-style cryptocurrencies, namely, Monero, Bytecoin and DigitalNote, according to their market capitalization. Since the computational cost of performing $$\textit{closed set}$$ attack is prohibitively expensive, we propose an efficient algorithm, called clustering algorithm, to (approximately) implement our attack. By combining our clustering method with the cascade attack, we are able to identify the real coin being spent in $$70.52\%$$ Monero inputs, $$74.25\%$$ Bytecoin inputs, and in $$91.56\%$$ DigitalNote inputs.In addition, we provide a theoretical analysis on the identified $$\textit{closed set}$$ attack, i.e., if every input in a CryptoNote-style blockchain has 3 mixins, and all mixins are sampled uniformly from all existing coins, the success rate of this attack is very small (about $$2^{-19}$$ ). Given that $$\textit{closed set}$$ attack is equivalent to the best possible statistical attack, our findings provide two key insights. First, the current system configuration of Monero is secure against statistical attacks, as the minimum number of mixin is 6. Second, we identify a new factor in improving anonymity, that is, the number of unspent keys. Our analysis indicates that the number of mixins in an input does not need to be very large, if the percentage of unspent keys is high.

Monero is a privacy-centric cryptocurrency that makes payments untraceable by adding decoys to every real input spent in a transaction. Two studies from 2017 found methods to distinguish decoys from real inputs, which enabled traceability for a majority of transactions. Since then, a number protocol changes have been introduced, but their effectiveness has not yet been reassessed. Furthermore, little is known about traceability of Monero transactions across hard fork chains. We formalize a new method for tracing Monero transactions, which is based on analyzing currency hard forks. We use that method to perform a (passive) traceability analysis on data from the Monero, MoneroV and Monero Original blockchains and find that only a small amount of inputs are traceable. We then use the results to estimate the effectiveness of known heuristics for recent transactions and find that they do not significantly outperform random guessing. Our findings suggest that Monero is currently mostly immune to known passive attack vectors and resistant to tracking and tracing methods applied to other cryptocurrencies.

Fiat currency implemented as a blockchain can enable multiple benefits such as reduced cost compared to expensive handling of cash and better transparency for increased public trust. However, such deployments have conflicting requirements including fast payments, strong user privacy and regulatory oversight. None of the existing blockchain transaction techniques supports all of these three requirements. In this paper we design a new blockchain currency, called PRCash, that addresses the above challenge. The primary technical contribution of our work is a novel regulation mechanism for transactions that use cryptographic commitments. We enable regulation of spending limits using zero-knowledge proofs. PRCash is the first blockchain currency that provides fast payments, good level of user privacy and regulatory control at the same time.

Cryptocurrencies record transactions between parties in a blockchain maintained by a peer-to-peer network. In most cryptocurrencies, transactions explicitly identify the previous transaction providing the funds they are spending, revealing the amount and sender/recipient pseudonyms. This is a considerable privacy issue. Zerocash resolves this by using zero-knowledge proofs to hide both the source, destination and amount of the transacted funds. To receive payments in Zerocash, however, the recipient must scan the blockchain, testing if each transaction is destined for them. This is not practical for mobile and other bandwidth constrained devices. In this paper, we build ZLiTE, a system that can support the so called “light clients”, which can receive transactions aided by a server equipped with a Trusted Execution Environment. Even with the use of a TEE, this is not a trivial problem. First, we must ensure that server processing the blockchain does not leak sensitive information via side channels. Second, we need to design a bandwidth efficient mechanism for the client to keep an up-to-date version of the witness needed in order to spend the funds they previously received.

3 Domain Secure 2.0 (3DS 2.0) is the most prominent user authentication protocol for credit card based online payment. 3DS 2.0 relies on risk assessment to decide whether to challenge the payment initiator for second factor authentication information (e.g., through a passcode). The 3DS 2.0 standard itself does not specify how to implement transaction risk assessment. The research questions addressed in this paper therefore are: how is transaction risk assessment implemented for current credit cards and are there practical exploits against the 3DS 2.0 risk assessment approach? We conduct a detailed reverse engineering study of 3DS 2.0 for payment using a browser, the first study of this kind. Through experiments with different cards, from different countries and for varying amounts, we deduct the data and decision making process that card issuers use in transaction risk assessment. We will see that card issuers differ considerable in terms of their risk appetite. We also demonstrate a practical impersonation attack against 3DS 2.0 that avoids being challenged for second factor authentication information, requiring no more data than obtained with the reverse engineering approach presented in this paper.

It is possible to relay signals between a contactless EMV card and a shop’s EMV reader and so make a fraudulent payment without the card-owner’s knowledge. Existing countermeasures rely on proximity checking: the reader will measure round trip times in message-exchanges, and will reject replies that take longer than expected (which suggests they have been relayed). However, it is the reader that would receive the illicit payment from any relayed transaction, so a rogue reader has little incentive to enforce the required checks. Furthermore, cases of malware targeting point-of-sales systems are common. We propose three novel proximity-checking protocols that use a trusted platform module (TPM) to ensure that the reader performs the time-measurements correctly. After running one of our proposed protocols, the bank can be sure that the card and reader were in close proximity, even if the reader tries to subvert the protocol. Our first protocol makes changes to the cards and readers, our second modifies the readers and the banking backend, and our third allows the detection of relay attacks, after they have happened, with only changes to the readers.

Internet banking security is set to take a major step forward: On September 14, 2019, the Regulatory Technical Standards of the Revised Payment Service Directive (PSD2) are going to be effective within the European Union and the European Economic Area. This regulation makes two widely demanded transaction security properties mandatory: two-factor authentication, and the dynamic linking of the authentication code to the transaction’s beneficiary and amount (full transaction authentication). Even though the regulation is undoubtedly a positive development from a security perspective, it does not account for all the technical and human weak points involved in the transaction process. In this paper, we look at a series of attacks targeting online and mobile banking that are possible even in a post-PSD2 era. Despite the regulatory motivation of this work, the presented issues and suggestions to address them are likely to be universal for internet banking in general.

EMV, also known as Chip and PIN, is the world-wide standard for card-based electronic payment. Its security wavers: over the past years, researchers have demonstrated various practical attacks, ranging from using stolen cards by disabling PIN verification to cloning cards by pre-computing transaction data. Most of these attacks rely on violating certain unjustified and not explicitly stated core assumptions upon which EMV is built, namely that the input device (e.g. the ATM) is trusted and all communication channels are non-interceptable. In addition, EMV lacks a comprehensive formal description of its security.In this work we give a formal model for the security of electronic payment protocols in the Universal Composability (UC) framework. A particular challenge for electronic payment is that one participant of a transaction is a human who cannot perform cryptographic operations. Our goal is twofold. First, we want to enable a transition from the iterative engineering of such protocols to using cryptographic security models to argue about a protocol’s security. Second, we establish a more realistic adversarial model for payment protocols in the presence of insecure devices and channels.We prove a set of necessary requirements for secure electronic payment with regards to our model. We then discuss the security of current payment protocols based on these results and find that most are insecure or require unrealistically strong assumptions. Finally, we give a simple payment protocol inspired by chipTAN and photoTAN and prove its security.Our model captures the security properties of electronic payment protocols with human interaction. We show how to use this to reason about necessary requirements for secure electronic payment and how to develop a protocol based on the resulting guidelines. We hope that this will facilitate the development of new protocols with well-understood security properties.

Trick-Taking Games (TTGs) are card games in which each player plays one of his cards in turn according to a given rule. The player with the highest card then wins the trick, i.e., he gets all the cards that have been played during the round. For instance, Spades is a famous TTG proposed by online casinos, where each player must play a card that follows the leading suit when it is possible. Otherwise, he can play any of his cards. In such a game, a dishonest user can play a wrong card even if he has cards of the leading suit. Since his other cards are hidden, there is no way to detect the cheat. Hence, the other players realize the problem later, i.e., when the cheater plays a card that he is not supposed to have. In this case, the game is biased and is canceled. Our goal is to design protocols that prevent such a cheat for TTGs. We give a security model for secure Spades protocols, and we design a scheme called SecureSpades. This scheme is secure under the Decisional Diffie-Hellman assumption in the random oracle model. Our model and our scheme can be extended to several other TTGs, such as Belotte, Whist, Bridge, etc.

While many tailor made card game protocols are known, the vast majority of those lack three important features: mechanisms for distributing financial rewards and punishing cheaters, composability guarantees and flexibility, focusing on the specific game of poker. Even though folklore holds that poker protocols can be used to play any card game, this conjecture remains unproven and, in fact, does not hold for a number of protocols (including recent results). We both tackle the problem of constructing protocols for general card games and initiate a treatment of such protocols in the Universal Composability (UC) framework, introducing an ideal functionality that captures card games that use a set of core card operations. Based on this formalism, we introduce Royale, the first UC-secure general card games which supports financial rewards/penalties enforcement. We remark that Royale also yields the first UC-secure poker protocol. Interestingly, Royale performs better than most previous works (that do not have composability guarantees), which we highlight through a detailed concrete complexity analysis and benchmarks from a prototype implementation.

We present a very simple universally verifiable MPC protocol. The first component is a threshold somewhat homomorphic cryptosystem that permits an arbitrary number of additions (in the source group), followed by a single multiplication, followed by an arbitrary number of additions in the target group. The second component is a black-box construction of universally verifiable distributed encryption switching between any public key encryption schemes supporting shared setup and key generation phases, as long as the schemes satisfy some natural additive-homomorphic properties. This allows us to switch back from the target group to the source group, and hence perform an arbitrary number of multiplications. The key generation algorithm of our prototypical cryptosystem, which is based upon concurrent verifiable secret sharing, permits robust re-construction of powers of a shared secret.

We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of f faults among $$n=2f+1$$ parties. Our protocols achieve an expected O(1) round complexity and an expected $$O(n^2)$$ communication complexity. The exact round complexity in expectation is 10 for a static adversary and 16 for a strongly rushing adaptive adversary. For comparison, previous protocols in the same setting require expected 29 rounds.

Ensuring secure deduplication of encrypted data is a very active topic of research because deduplication is effective at reducing storage costs. Schemes supporting deduplication of encrypted data that are not vulnerable to content guessing attacks (such as Message Locked Encryption) have been proposed recently [Bellare et al. 2013, Li et al. 2015]. However in all these schemes, there is a key derivation phase that solely depends on a short hash of the data and not the data itself. Therefore, a file specific key can be obtained by anyone possessing the hash. Since hash values are usually not meant to be secret, a desired solution will be a more robust oblivious key generation protocol where file hashes need not be kept private. Motivated by this use-case, we propose a new primitive for oblivious pseudorandom function (OPRF) on committed vector inputs in the universal composable (UC) framework. We formalize this functionality as $$\mathcal {F}_\mathsf {OOPRF}$$ , where $$\mathsf {OOPRF}$$ stands for Ownership-based Oblivious PRF. $$\mathcal {F}_\mathsf {OOPRF}$$ produces a unique random key on input a vector digest provided the client proves knowledge of a (parametrisable) number of random positions of the input vector.To construct an efficient $$\mathsf {OOPRF}$$ protocol, we carefully combine a hiding vector commitment scheme, a variant of the PRF scheme of Dodis-Yampolskiy [Dodis et al. 2005] and a homomorphic encryption scheme glued together with concrete, efficient instantiations of proofs of knowledge. To the best of our knowledge, our work shows for the first time how these primitives can be combined in a secure, efficient and useful way. We also propose a new vector commitment scheme with constant sized public parameters but $$(\log n)$$ size witnesses where n is the length of the committed vector. This can be of independent interest.

A constrained pseudo random function (PRF) behaves like a standard PRF, but with the added feature that the (master) secret key holder, having secret key K, can produce a constrained key, $$K_f$$ , that allows for the evaluation of the PRF on a subset of the domain as determined by a predicate function f within some family $$\mathcal {F}$$ . While previous constructions gave constrained PRFs for poly-sized circuits, all reductions for such functionality were based in the selective model of security where an attacker declares which point he is attacking before seeing any constrained keys.In this paper we give new constrained PRF constructions for arbitrary circuits in the random oracle model based on indistinguishability obfuscation. Our solution is constructed from two recently emerged primitives: an adaptively secure Attribute-Based Encryption (ABE) for circuits and a Universal Sampler Scheme as introduced by Hofheinz et al. Both primitives are constructible from indistinguishability obfuscation ( $$i\mathcal {O}$$ ) (and injective pseudorandom generators) with only polynomial loss.

Lattice-based encryption schemes still suffer from a low message throughput per ciphertext and inefficient solutions towards realizing enhanced security properties such as CCA1- or CCA2-security. This is mainly due to the fact that the underlying schemes still follow a traditional design concept and do not tap the full potentials of LWE. Furthermore, the desired security features are also often achieved by costly approaches or less efficient generic transformations. Recently, a novel encryption scheme based on the A-LWE assumption (relying on the hardness of LWE) has been proposed, where data is embedded into the error term without changing its target distributions. By this novelty it is possible to encrypt much more data as compared to the classical approach. In this paper we revisit this approach and propose several techniques in order to improve the message throughput per ciphertext. Furthermore, we present a very efficient trapdoor construction of reduced storage size. More precisely, the secret and public key sizes are reduced to just 1 polynomial, as opposed to $$O( \log q)$$ polynomials following previous constructions. Finally, we give an efficient implementation of the scheme instantiated with the new trapdoor construction. In particular, we attest high message throughputs and low ciphertext expansion factors at efficient running times. Our scheme even ensures CCA (or RCCA) security, while entailing a great deal of flexibility to encrypt arbitrary large messages or signatures by use of the same secret key.

We propose a proof of work protocol that computes the discrete logarithm of an element in a cyclic group. Individual provers generating proofs of work perform a distributed version of the Pollard rho algorithm. Such a protocol could capture the computational power expended to construct proof-of-work-based blockchains for a more useful purpose, as well as incentivize advances in hardware, software, or algorithms for an important cryptographic problem. We describe our proposed construction and elaborate on challenges and potential trade-offs that arise in designing a practical proof of work.

We introduce the notion of two-factor signatures (2FS), a generalization of a two-out-of-two threshold signature scheme in which one of the parties is a hardware token which can store a high-entropy secret, and the other party is a human who knows a low-entropy password. The security (unforgeability) property of 2FS requires that an external adversary corrupting either party (the token or the computer the human is using) cannot forge a signature.This primitive is useful in contexts like hardware cryptocurrency wallets in which a signature conveys the authorization of a transaction. By the above security property, a hardware wallet implementing a two-factor signature scheme is secure against attacks mounted by a malicious hardware vendor; in contrast, all currently used wallet systems break under such an attack (and as such are not secure under our definition).We construct efficient provably-secure 2FS schemes which produce either Schnorr signature (assuming the DLOG assumption), or EC-DSA signatures (assuming security of EC-DSA and the CDH assumption) in the Random Oracle Model, and evaluate the performance of implementations of them. Our EC-DSA based 2FS scheme can directly replace currently used hardware wallets for Bitcoin and other major cryptocurrencies to enable security against malicious hardware vendors.

Bitcoin, being the most successful cryptocurrency, has been repeatedly attacked with many users losing their funds. The industry’s response to securing the user’s assets is to offer tamper-resistant hardware wallets. Although such wallets are considered to be the most secure means for managing an account, no formal attempt has been previously done to identify, model and formally verify their properties. This paper provides the first formal model of the Bitcoin hardware wallet operations. We identify the properties and security parameters of a Bitcoin wallet and formally define them in the Universal Composition (UC) Framework. We present a modular treatment of a hardware wallet ecosystem, by realizing the wallet functionality in a hybrid setting defined by a set of protocols. This approach allows us to capture in detail the wallet’s components, their interaction and the potential threats. We deduce the wallet’s security by proving that it is secure under common cryptographic assumptions, provided that there is no deviation in the protocol execution. Finally, we define the attacks that are successful under a protocol deviation, and analyze the security of commercially available wallets.

The adoption of blockchain based distributed ledgers is growing fast due to their ability to provide reliability, integrity, and auditability without trusted entities. One of the key capabilities of these emerging platforms is the ability to create self-enforcing smart contracts. However, the development of smart contracts has proven to be error-prone in practice, and as a result, contracts deployed on public platforms are often riddled with security vulnerabilities. This issue is exacerbated by the design of these platforms, which forbids updating contract code and rolling back malicious transactions. In light of this, it is crucial to ensure that a smart contract is secure before deploying it and trusting it with significant amounts of cryptocurrency. To this end, we introduce the VeriSolid framework for the formal verification of contracts that are specified using a transition-system based model with rigorous operational semantics. Our model-based approach allows developers to reason about and verify contract behavior at a high level of abstraction. VeriSolid allows the generation of Solidity code from the verified models, which enables the correct-by-design development of smart contracts.

We prove Bitcoin is secure under temporary dishonest majority. We assume the adversary can corrupt a specific fraction of parties and also introduce crash failures, i.e., some honest participants are offline during the execution of the protocol. We demand a majority of honest online participants on expectation. We explore three different models and present the requirements for proving Bitcoin’s security in all of them: we first examine a synchronous model, then extend to a bounded delay model and last we consider a synchronous model that allows message losses.

Blockchains is a special type of distributed systems that operates in unsafe networks. In most blockchains, all nodes should reach consensus on all state transitions with Byzantine fault tolerant algorithms, which creates bottlenecks in performance. In this paper, we propose a new type of blockchains, namely Value-Centric Blockchains (VCBs), in which the states are specified as values (or more comprehensively, coins) with owners and the state transition records are then specified as proofs of the ownerships of individual values. We then formalize the “rational” assumptions that have been used in most blockchains. We further propose a VCB, VAPOR, that guarantees secure value transfers if all nodes are rational and keep the proofs of the values they owned, which is merely parts of the whole state transition record. As a result, we show that VAPOR enjoys significant benefits in throughput, decentralization, and flexibility without compromising security.

Bitcoin, Ethereum and other blockchain-based cryptocurrencies, as deployed today, cannot support more than several transactions per second. Off-chain payment channels, a “layer 2” solution, are a leading approach for cryptocurrency scaling. They enable two mutually distrustful parties to rapidly send payments between each other and can be linked together to form a payment network, such that payments between any two parties can be routed through the network along a path that connects them.We propose a novel payment channel protocol, called Sprites. The main advantage of Sprites compared with earlier protocols is a reduced “collateral cost,” meaning the amount of money $$\times $$ time that must be locked up before disputes are settled. In the Lightning Network and Raiden, a payment across a path of $$\ell $$ channels requires locking up collateral for $$\varTheta (\ell \varDelta )$$ time, where $$\varDelta $$ is the time to commit an on-chain transaction; every additional node on the path forces an increase in lock time. The Sprites construction provides a constant lock time, reducing the overall collateral cost to $$\varTheta (\ell + \varDelta ).$$ Our presentation of the Sprites protocol is also modular, making use of a generic state channel abstraction. Finally, Sprites improves on prior payment channel constructions by supporting partial withdrawals and deposits without any on-chain transactions.

So far, the topic of merged mining has mainly been considered in a security context, covering issues such as mining power centralization or cross-chain attack scenarios. In this work we show that key information for determining blockchain metrics such as the fork rate can be recovered through data extracted from merge mined cryptocurrencies. Specifically, we reconstruct a long-ranging view of forks and stale blocks in Bitcoin from its merge mined child chains, and compare our results to previous findings that were derived from live measurements. Thereby, we show that live monitoring alone is not sufficient to capture a large majority of these events, as we are able to identify a non-negligible portion of stale blocks that were previously unaccounted for. Their authenticity is ensured by cryptographic evidence regarding both, their position in the respective blockchain, as well as the Proof-of-Work difficulty.Furthermore, by applying this new technique to Litecoin and its child cryptocurrencies, we are able to provide the first extensive view and lower bound on the stale block and fork rate in the Litecoin network. Finally, we outline that a recovery of other important metrics and blockchain characteristics through merged mining may also be possible.

Bitcoin relies on a peer-to-peer overlay network to broadcast transactions and blocks. From the viewpoint of network measurement, we would like to observe this topology so we can characterize its performance, fairness and robustness. However, this is difficult because Bitcoin is deliberately designed to hide its topology from onlookers. Knowledge of the topology is not in itself a vulnerability, although it could conceivably help an attacker performing targeted eclipse attacks or to deanonymize transaction senders.In this paper we present TxProbe, a novel technique for reconstructing the Bitcoin network topology. TxProbe makes use of peculiarities in how Bitcoin processes out of order, or “orphaned” transactions. We conducted experiments on Bitcoin testnet that suggest our technique reconstructs topology with precision and recall surpassing 90%. We also used TxProbe to take a snapshot of the Bitcoin testnet in just a few hours. TxProbe may be useful for future measurement campaigns of Bitcoin or other cryptocurrency networks.

In the face of large-scale automated social engineering attacks to large online services, fast detection and remediation of compromised accounts are crucial to limit the spread of the attack and to mitigate the overall damage to users, companies, and the public at large. We advocate a fully automated approach based on machine learning: we develop an early warning system that harnesses account activity traces to predict which accounts are likely to be compromised in the future. We demonstrate the feasibility and applicability of the system through an experiment at a large-scale online service provider using four months of real-world production data encompassing hundreds of millions of users. We show that—even limiting ourselves to login data only in order to derive features with low computational cost, and a basic model selection approach—our classifier can be tuned to achieve good classification precision when used for forecasting. Our system correctly identifies up to one month in advance the accounts later flagged as suspicious with precision, recall, and false positive rates that indicate the mechanism is likely to prove valuable in operational settings to support additional layers of defense.

Aiming at the increasing threat of fraud in electronic transactions, so far researchers have already proposed many different models. However, few previous studies take advantage of the sequential characteristics of fraudulent transactions. In this paper, by statistical analysis on a real dataset, we discover that partial-order sequential features are able to reflect the intrinsic motivation of fraudsters, e.g., stealing the money as quickly as possible before being intercepted. Based on the sequential features, we propose a novel model, SeqFD (Sequential feature boosting Fraud Detector), to detect fraudulent transactions real-timely. SeqFD applies a sliding time window strategy to aggregate the historical transactions. In specific, statistical sequential features are computed based on the transactions within the time window. Thus, the raw dataset can be transformed into a feature set. Several classification models are evaluated on the feature set, and finally, XGBoost is validated to be a fast, accurate and robust classifier which fits well with SeqFD. The experiments on real dataset show that the proposed model reaches a 97.2% TPR (True Positive Rate) when FPR (False Positive Rate) is less than 1%. Furthermore, the average time for giving a prediction is 1.5 ms, which meets the real-time requirement in the industry.

Collaboration between financial institutions helps to improve detection of fraud. However, exchange of relevant data between these institutions is often not possible due to privacy constraints and data confidentiality. An important example of relevant data for fraud detection is given by a transaction graph, where the nodes represent bank accounts and the links consist of the transactions between these accounts. Previous works show that features derived from such graphs, like PageRank, can be used to improve fraud detection. However, each institution can only see a part of the whole transaction graph, corresponding to the accounts of its own customers. In this research a new method is described, making use of secure multiparty computation (MPC) techniques, allowing multiple parties to jointly compute the PageRank values of their combined transaction graphs securely, while guaranteeing that each party only learns the PageRank values of its own accounts and nothing about the other transaction graphs. In our experiments this method is applied to graphs containing up to tens of thousands of nodes. The execution time scales linearly with the number of nodes, and the method is highly parallelizable. Secure multiparty PageRank is feasible in a realistic setting with millions of nodes per party by extrapolating the results from our experiments.

We are increasingly surrounded by numerous embedded systems which collect, exchange, and process sensitive and safety-critical information. The Internet of Things (IoT) allows a large number of interconnected devices to be accessed and controlled remotely, across existing network infrastructure. Consequently, a remote attacker can exploit security vulnerabilities and compromise these systems. In this context, remote attestation is a very useful security service that allows to remotely and securely verify the integrity of devices’ software state, thus allowing the detection of potential malware on the device. However, current attestation schemes focus on detecting whether a device is infected by malware but not on disinfecting it and restoring its software to a benign state.In this paper we present HEALED – the first remote attestation scheme for embedded devices that allows both detection of software compromise and disinfection of compromised devices. HEALED uses Merkle Hash Trees (MHTs) for measurement of software state, which allows restoring a device to a benign state in a secure and efficient manner.

A one-time program (OTP) works as follows: Alice provides Bob with the implementation of some function. Bob can have the function evaluated exclusively on a single input of his choosing. Once executed, the program will fail to evaluate on any other input. State-of-the-art one-time programs have remained theoretical, requiring custom hardware that is cost-ineffective/unavailable, or confined to ad-hoc/unrealistic assumptions. To bridge this gap, we explore how the Trusted Execution Environment (TEE) of modern CPUs can realize the OTP functionality. Specifically, we build two flavours of such a system: in the first, the TEE directly enforces the one-timeness of the program; in the second, the program is represented with a garbled circuit and the TEE ensures Bob’s input can only be wired into the circuit once, equivalent to a smaller cryptographic primitive called one-time memory. These have different performance profiles: the first is best when Alice’s input is small and Bob’s is large, and the second for the converse.

The conventional (election) voting systems, e.g., representative democracy, have many limitations and often fail to serve the best interest of the people in a collective decision-making process. To address this issue, the concept of liquid democracy has been emerging as an alternative decision-making model to make better use of “the wisdom of crowds”. However, there is no known cryptographically secure e-voting implementation that supports liquid democracy.In this work, we propose a new voting concept called statement voting, which can be viewed as a natural extension of the conventional voting approaches. In the statement voting, instead of defining a concrete election candidate, each voter can define a statement in his/her ballot but leave the vote “undefined” during the voting phase. During the tally phase, the (conditional) actions expressed in the statement will be carried out to determine the final vote. We initiate the study of statement voting under the Universal Composability (UC) framework, and propose several construction frameworks together with their instantiations. As an application, we show how statement voting can be used to realize a UC-secure liquid democracy voting system. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes.

An attempt to derive signer-efficient digital signatures from aggregate signatures was made in a signature scheme referred to as Structure-free Compact Rapid Authentication (SCRA) (IEEE TIFS 2017). In this paper, we first mount a practical universal forgery attack against the NTRU instantiation of SCRA by observing only 8161 signatures. Second, we propose a new signature scheme ( $$\texttt {FAAS}$$ ), which transforms any single-signer aggregate signature scheme into a signer-efficient scheme. We show two efficient instantiations of $$\texttt {FAAS}$$ , namely, $$\texttt {FAAS}\hbox {-}{} \texttt {NTRU}$$ and $$\texttt {FAAS}\hbox {-}{} \texttt {RSA}$$ , both of which achieve high computational efficiency. Our experiments confirmed that $$\texttt {FAAS}$$ schemes achieve up to 100 $$\times $$ faster signature generation compared to their underlying schemes. Moreover, $$\texttt {FAAS}$$ schemes eliminate some of the costly operations such as Gaussian sampling, rejection sampling, and exponentiation at the signature generation that are shown to be susceptible to side-channel attacks. This enables $$\texttt {FAAS}$$ schemes to enhance the security and efficiency of their underlying schemes. Finally, we prove that $$\texttt {FAAS}$$ schemes are secure (in random oracle model), and open-source both our attack and $$\texttt {FAAS}$$ implementations for public testing purposes.