nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Financial Cryptography and Data Security

FC 2016 International Workshops, BITCOIN, VOTING, and WAHC, Christ Church, Barbados, February 26, 2016, Revised Selected Papers

herausgegeben von: Jeremy Clark, Sarah Meiklejohn, Peter Y.A. Ryan, Dan Wallach, Michael Brenner, Kurt Rohloff

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Inhaltsverzeichnis

Über dieses Buch

This book constitutes the refereed proceedings of three workshops heldat the 20th International Conference on Financial Cryptography and DataSecurity, FC 2016, in Christ Church, Barbados, in February 2016.
The 22 full papers presented were carefully reviewed and selected from 49 submissions. They feature the outcome of the Second Workshop on Bitcoin and Blockchain Research, BITCOIN 2016, the First Workshop on Secure Voting Systems, VOTING 2016, and the 4th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2016.

Inhaltsverzeichnis

Frontmatter

Third Workshop on Bitcoin and Blockchain Research, BITCOIN 2016

Frontmatter

Stressing Out: Bitcoin “Stress Testing”

Abstract

In this paper, we present an empirical study of a recent spam campaign (a “stress test”) that resulted in a DoS attack on Bitcoin. The goal of our investigation being to understand the methods spammers used and impact on Bitcoin users. To this end, we used a clustering based method to detect spam transactions. We then validate the clustering results and generate a conservative estimate that 385,256 (23.41 %) out of 1,645,667 total transactions were spam during the 10 day period at the peak of the campaign. We show the impact of increasing non-spam transaction fees from 45 to 68 Satoshis/byte (from $0.11 to $0.17 USD per kilobyte of transaction) on average, and increasing delays in processing non-spam transactions from 0.33 to 2.67 h on average, as well as estimate the cost of this spam attack at 201 BTC (or $49,000 USD). We conclude by pointing out changes that could be made to Bitcoin transaction fees that would mitigate some of the spam techniques used to effectively DoS Bitcoin.

Khaled Baqer, Danny Yuxing Huang, Damon McCoy, Nicholas Weaver

Why Buy When You Can Rent?

Bribery Attacks on Bitcoin-Style Consensus

Abstract

The Bitcoin cryptocurrency introduced a novel distributed consensus mechanism relying on economic incentives. While a coalition controlling a majority of computational power may undermine the system, for example by double-spending funds, it is often assumed it would be incentivized not to attack to protect its long-term stake in the health of the currency. We show how an attacker might purchase mining power (perhaps at a cost premium) for a short duration via bribery. Indeed, bribery can even be performed in-band with the system itself enforcing the bribe. A bribing attacker would not have the same concerns about the long-term health of the system, as their majority control is inherently short-lived. New modeling assumptions are needed to explain why such attacks have not been observed in practice. The need for all miners to avoid short-term profits by accepting bribes further suggests a potential tragedy of the commons which has not yet been analyzed.

Joseph Bonneau

Automated Verification of Electrum Wallet

Abstract

We introduce a formal modeling in ASLan++ of the two-factor authentication protocol used by the Electrum Bitcoin wallet. This allows us to perform an automatic analysis of the wallet and show that it is secure for standard scenarios in Dolev Yao model [Dolev 1981]. The result could be derived thanks to some advanced features of the protocol analyzer such as the possibility to specify (i) new intruder deduction rules with clauses and (ii) non-deducibility constraints.

Mathieu Turuani, Thomas Voegtlin, Michael Rusinowitch

Blindly Signed Contracts: Anonymous On-Blockchain and Off-Blockchain Bitcoin Transactions

Abstract

Although Bitcoin is often perceived to be an anonymous currency, research has shown that a user’s Bitcoin transactions can be linked to compromise the user’s anonymity. We present solutions to the anonymity problem for both transactions on Bitcoin’s blockchain and off the blockchain (in so called micropayment channel networks). We use an untrusted third party to issue anonymous vouchers which users redeem for Bitcoin. Blind signatures and Bitcoin transaction contracts (aka smart contracts) ensure the anonymity and fairness during the bitcoin $\leftrightarrow $ voucher exchange. Our schemes are practical, secure and anonymous.

Ethan Heilman, Foteini Baldimtsi, Sharon Goldberg

Proofs of Proofs of Work with Sublinear Complexity

Abstract

In the setting of blockchain based transaction ledgers we study the problem of “simplified payment verification” (SPV) which refers to the setting of a transaction verifier that wishes to examine the last k blocks of the blockchain (e.g., for the purpose of verification of a certain transaction) using as only advice the genesis block (or some “checkpoint” block that is known to it).

The straightforward solution to this task requires the delivery of the blockchain, the verification of the proof of work it contains, and subsequently the examination of the last k blocks. It follows that the communication required to complete this task is linear in the length of the chain.

At first thought the above seems the best one can hope: a sublinear in the length of the chain solution to the problem will be susceptible to an attacker that, using precomputation, can fool the verifier.

Contrary to this intuition, we show that with a suitable modification to the current Bitcoin blockchain protocol (that incurs a single hash expansion in each block and gives rise to the notion of an interconnected blockchain) we can produce proofs of proof of work with sublinear complexity in the length of the chain hence enabling SPV to be performed much more efficiently.

Aggelos Kiayias, Nikolaos Lamprou, Aikaterini-Panagiota Stouka

Step by Step Towards Creating a Safe Smart Contract: Lessons and Insights from a Cryptocurrency Lab

Abstract

We document our experiences in teaching smart contract programming to undergraduate students at the University of Maryland, the first pedagogical attempt of its kind. Since smart contracts deal directly with the movement of valuable currency units between contractual parties, security of a contract program is of paramount importance.

Our lab exposed numerous common pitfalls in designing safe and secure smart contracts. We document several typical classes of mistakes students made, suggest ways to fix/avoid them, and advocate best practices for programming smart contracts. Finally, our pedagogical efforts have also resulted in online open course materials for programming smart contracts, which may be of independent interest to the community.

Kevin Delmolino, Mitchell Arnett, Ahmed Kosba, Andrew Miller, Elaine Shi

EthIKS: Using Ethereum to Audit a CONIKS Key Transparency Log

Abstract

CONIKS is a proposed key transparency system which enables a centralized service provider to maintain an auditable yet privacy-preserving directory of users’ public keys. In the original CONIKS design, users must monitor that their data is correctly included in every published snapshot of the directory, necessitating either slow updates or trust in an unspecified third-party to audit that the data structure has stayed consistent. We demonstrate that the data structures for CONIKS are very similar to those used in Ethereum, a consensus computation platform with a Turing-complete programming environment. We can take advantage of this to embed the core CONIKS data structures into an Ethereum contract with only minor modifications. Users may then trust the Ethereum network to audit the data structure for consistency and non-equivocation. Users who do not trust (or are unaware of) Ethereum can self-audit the CONIKS data structure as before. We have implemented a prototype contract for our hybrid EthIKS scheme, demonstrating that it adds only modest bandwidth overhead to CONIKS proofs and costs hundredths of pennies per key update in fees at today’s rates.

Joseph Bonneau

On Scaling Decentralized Blockchains

(A Position Paper)

Abstract

The increasing popularity of blockchain-based cryptocurrencies has made scalability a primary and urgent concern. We analyze how fundamental and circumstantial bottlenecks in Bitcoin limit the ability of its current peer-to-peer overlay network to support substantially higher throughputs and lower latencies. Our results suggest that reparameterization of block size and intervals should be viewed only as a first increment toward achieving next-generation, high-load blockchain protocols, and major advances will additionally require a basic rethinking of technical approaches. We offer a structured perspective on the design space for such approaches. Within this perspective, we enumerate and briefly discuss a number of recently proposed protocol ideas and offer several new ideas and open challenges.

Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gün Sirer, Dawn Song, Roger Wattenhofer

Bitcoin Covenants

Abstract

This paper presents an extension to Bitcoin’s script language enabling covenants, a primitive that allows transactions to restrict how the value they transfer is used in the future. Covenants expand the set of financial instruments expressible in Bitcoin, and enable new powerful and novel use cases. We illustrate two novel security constructs built using covenants.

The first, vaults, focuses on improving the security of private cryptographic keys. Historically, maintaining these keys securely and reliably has been a critical vulnerability for Bitcoin users. We show how covenants enable vaults, which disincentivize key theft by preventing an attacker from gaining full access to stolen funds.

The second construct, poison transactions, is a generally useful mechanism for penalizing double-spending attacks. Bitcoin-NG, a protocol that has been recently proposed to improve Bitcoin’s throughput, latency and overall scalability, requires this feature. We show how covenants enable poison transactions, and detail how Bitcoin-NG can be implemented progressively as an overlay on top of the Bitcoin blockchain.

Malte Möser, Ittay Eyal, Emin Gün Sirer

Cryptocurrencies Without Proof of Work

Abstract

We study decentralized cryptocurrency protocols in which the participants do not deplete physical scarce resources. Such protocols commonly rely on Proof of Stake, i.e., on mechanisms that extend voting power to the stakeholders of the system. We offer analysis of existing protocols that have a substantial amount of popularity. We then present our novel pure Proof of Stake protocols, and argue that they help in mitigating problems that the existing protocols exhibit.

Iddo Bentov, Ariel Gabizon, Alex Mizrahi

First Workshop on Secure Voting Systems, VOTING 2016

Frontmatter

Coercion-Resistant Internet Voting with Everlasting Privacy

Abstract

The cryptographic voting protocol presented in this paper offers public verifiability, everlasting privacy, and coercion-resistance simultaneously. Voters are authenticated anonymously based on perfectly hiding commitments and zero-knowledge proofs. Their vote and participation secrecy is therefore protected independently of computational intractability assumptions or trusted authorities. Coercion-resistance is achieved based on a new mechanism for deniable vote updating. To evade coercion by submitting a final secret vote update, the voter needs not to remember the history of all precedent votes. The protocol uses two types of mix networks to guarantee that vote updating cannot be detected by the coercer. The input sizes and running times of the mix networks are quadratic with respect to the number of submitted ballots.

Philipp Locher, Rolf Haenni, Reto E. Koenig

Selene: Voting with Transparent Verifiability and Coercion-Mitigation

Abstract

End-to-end verifiable voting schemes typically involve voters handling an encrypted ballot in order to confirm that their vote is accurately included in the tally. While this may be technically valid, from a public acceptance standpoint it may be problematic: many voters may not really understand the purpose of the encrypted ballot and the various checks that they can perform. In this paper we take a different approach and revisit an old idea: to provide each voter with a private tracking number. Votes are posted on a bulletin board in the clear along with their associated tracking number. This is appealing in that it provides voters with a very simple, intuitive way to verify their vote, in the clear. However, there are obvious drawbacks: we must ensure that no two voters are assigned the same tracker and we need to keep the link between voters and trackers private.

We propose a scheme that addresses both of these problems: we ensure that voters get unique trackers and we close off coercion opportunities by ensuring that the voters only learn their tracking numbers after the votes have been posted. The resulting scheme provides receipt-freeness, and indeed a good level of coercion-resistance while also providing a more immediately understandable form of verifiability.

Peter Y. A. Ryan, Peter B. Rønne, Vincenzo Iovino

On the Possibility of Non-interactive E-Voting in the Public-Key Setting

Abstract

In 2010 Hao, Ryan and Zielinski proposed a simple decentralized e-voting protocol that only requires 2 rounds of communication. Thus, for k elections their protocol needs 2k rounds of communication. Observing that the first round of their protocol is aimed to establish the public-keys of the voters, we propose an extension of the protocol as a non-interactive e-voting scheme in the public-key setting (NIVS) in which the voters, after having published their public-keys, can use the corresponding secret-keys to participate in an arbitrary number of one-round elections.

We first construct a NIVS with a standard tally function where the number of votes for each candidate is counted.

Further, we present constructions for two alternative types of elections. Specifically in the first type (dead or alive elections) the tally shows if at least one voter cast a vote for the candidate. In the second one (elections by unanimity), the tally shows if all voters cast a vote for the candidate.

Our constructions are based on bilinear groups of prime order.

As definitional contribution we provide formal computational definitions for privacy and verifiability of NIVSs. We conclude by showing intriguing relations between our results, secure computation, electronic exams and conference management systems.

Rosario Giustolisi, Vincenzo Iovino, Peter B. Rønne

Efficiency Comparison of Various Approaches in E-Voting Protocols

Abstract

In order to ensure the security of remote Internet voting, the systems that are currently proposed make use of complex cryptographic techniques. Since these techniques are often computationally extensive, efficiency becomes an issue. Identifying the most efficient Internet voting system is a non-trivial task – in particular for someone who does not have a sufficient knowledge on the systems that currently exist, and on the cryptographic components that constitute those systems. Aside from these components, the efficiency of Internet voting also depends on various parameters, such as expected number of participating voters and ballot complexity. In this paper we propose a tool for evaluating the efficiency of different approaches for an input scenario, that could be of use to election organizers deciding how to implement the voting system.

Oksana Kulyk, Melanie Volkamer

Remote Electronic Voting Can Be Efficient, Verifiable and Coercion-Resistant

Abstract

The coercion issue in remote electronic voting has always been of particular interest. However, to date, all proposals addressing it either suffer from some shortcomings or are not efficient enough to be used in real world elections. To fill this gap, we propose a new coercion-resistant electronic voting scheme practical for real polls. Our scheme relies on credentials generated thanks to a recent algebraic Message Authentication Code (MAC) scheme due to Chase et al. To enable multiple elections and credentials revocation, we also design a novel sequential aggregate MAC scheme, that is of independent interest. Thanks to it, eligible voters’ credentials can be efficiently updated.

Roberto Araújo, Amira Barki, Solenn Brunet, Jacques Traoré

Universal Cast-as-Intended Verifiability

Abstract

In electronic voting, we say that a protocol has cast-as-intended verifiability if the contents of each encrypted vote can be audited in order to ensure that they match the voter’s selections. It is traditionally thought that this verification can only be performed by the voter who casts the vote, since only she knows the content of her vote. In this work, we show that this is not the case: we present the first cast-as-intended verification mechanism which is universally verifiable, i.e., the first protocol in which anyone (the voter herself or another party) can check that the contents of an encrypted vote match the voter’s selections. To achieve this goal, we assume the existence of a trusted registrar. We formally define universal cast-as-intended verifiability and we show that our protocol satisfies such property, while also satisfying ballot privacy. We give a general construction of the protocol and an efficient instantiation which is provably secure in the random oracle model. We also present a voting system which can be implemented on top of the voting protocol, which is intended to present a more intuitive process to the voter.

Alex Escala, Sandra Guasch, Javier Herranz, Paz Morillo

4th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2016

Frontmatter

Hiding Access Patterns in Range Queries Using Private Information Retrieval and ORAM

Abstract

We study the problem of privacy preserving range search that provides data, query, and response confidentiality to the users for range queries. We propose two methods based on Private Information Retrieval (PIR) and Oblivious RAM (ORAM) techniques. For PIR-based queries, Lipmaa’s computationally-private information retrieval (CPIR) scheme is employed. For the ORAM-based method, Stefanov et al.’s Path ORAM scheme is adapted to enable privacy preserving range search. Our analyses show that from the computational point of view, the ORAM-based method performs much better due to cheap server operations. However, CPIR utilizes the bandwidth better especially for large databases, its security definitions are more formal, and it is more flexible for various settings with multiple clients and/or bandwidth limitations. In this work, to make CPIR a practical alternative for large databases, we improve its performance via shared memory OpenMP and distributed memory OpenMP-MPI parallelization with a scalable data/task partitioning.

Gamze Tillem, Ömer Mert Candan, Erkay Savaş, Kamer Kaya

Optimizing MPC for Robust and Scalable Integer and Floating-Point Arithmetic

Abstract

Secure multiparty computation (SMC) is a rapidly maturing field, but its number of practical applications so far has been small. Most existing applications have been run on small data volumes with the exception of a recent study processing tens of millions of education and tax records. For practical usability, SMC frameworks must be able to work with large collections of data and perform reliably under such conditions. In this work we demonstrate that with the help of our recently developed tools and some optimizations, the Sharemind secure computation framework is capable of executing tens of millions integer operations or hundreds of thousands floating-point operations per second. We also demonstrate robustness in handling a billion integer inputs and a million floating-point inputs in parallel. Such capabilities are absolutely necessary for real world deployments.

Liisi Kerik, Peeter Laud, Jaak Randmets

On-the-fly Homomorphic Batching/Unbatching

Abstract

We introduce a homomorphic batching technique that can be used to pack multiple ciphertext messages into one ciphertext for parallel processing. One is able to use the method to batch or unbatch messages homomorphically to further improve the flexibility of encrypted domain evaluations. In particular, we show various approaches to implement Number Theoretic Transform (NTT) homomorphically in Fast Fourier Transform (FFT) speed. Also, we present the limitations that we encounter in application of these methods. We implement homomorphic batching in various settings and present concrete performance figures. Finally, we present an implementation of a homomorphic NTT method in which we process each element in an independent ciphertext. The advantage of this method is we are able to batch independent homomorphic NTT evaluations and achieve better amortized time.

Yarkın Doröz, Gizem S. Çetin, Berk Sunar

Using Intel Software Guard Extensions for Efficient Two-Party Secure Function Evaluation

Abstract

Recent developments have made two-party secure function evaluation (2P-SFE) vastly more efficient. However, because they make extensive use of cryptographic operations, these protocols remain too slow for practical use by most applications. The introduction of Intel’s Software Guard Extensions (SGX), which provide an environment for the isolated execution of code and handling of data, offers an opportunity to overcome such performance concerns. In this paper, we explore the challenges of using SGX to achieve security guarantees similar to those found in traditional 2P-SFE systems. After demonstrating a number of critical concerns, we develop two protocols for secure computation in the semi-honest model on this platform: one in which both parties are SGX-enabled and a second in which only one party has direct access to this hardware. We then show how these protocols can be made secure in the malicious model. We conclude that implementing 2P-SFE on SGX-enabled devices can render it practical for a wide range of applications.

Debayan Gupta, Benjamin Mood, Joan Feigenbaum, Kevin Butler, Patrick Traynor

CallForFire: A Mission-Critical Cloud-Based Application Built Using the Nomad Framework

Abstract

In this demo paper we describe CallForFire, a GIS-based mission-critical defense application that can be deployed in the cloud. CallForFire enables secure computation of enemy target locations and selection of firing assets. It is built using the Nomad framework, which enables the development of secure cloud-based applications. Our experimental results validate the feasibility of this application within the Nomad framework.

Mamadou H. Diallo, Michael August, Roger Hallman, Megan Kline, Henry Au, Vic Beach

Cryptographic Solutions for Genomic Privacy

Abstract

With the help of rapidly developing technology, DNA sequencing is becoming less expensive. As a consequence, the research in genomics has gained speed in paving the way to personalized (genomic) medicine, and geneticists need large collections of human genomes to further increase this speed. Furthermore, individuals are using their genomes to learn about their (genetic) predispositions to diseases, their ancestries, and even their (genetic) compatibilities with potential partners. This trend has also caused the launch of health-related websites and online social networks (OSNs), in which individuals share their genomic data (e.g., OpenSNP or 23andMe). On the other hand, genomic data carries much sensitive information about its owner. By analyzing the DNA of an individual, it is now possible to learn about his disease predispositions (e.g., for Alzheimer’s or Parkinson’s), ancestries, and physical attributes. The threat to genomic privacy is magnified by the fact that a person’s genome is correlated to his family members’ genomes, thus leading to interdependent privacy risks. In this work, focusing on our existing and ongoing work on genomic privacy, we will first highlight one serious threat for genomic privacy. Then, we will present the high level descriptions of our cryptographic solutions to protect the privacy of genomic data.

Erman Ayday

Backmatter

Titel: Financial Cryptography and Data Security
herausgegeben von: Jeremy Clark
Sarah Meiklejohn
Peter Y.A. Ryan
Dan Wallach
Michael Brenner
Kurt Rohloff
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-53357-4
Print ISBN: 978-3-662-53356-7
DOI: https://doi.org/10.1007/978-3-662-53357-4