Skip to main content

2015 | Book

Financial Cryptography and Data Security

FC 2015 International Workshops, BITCOIN, WAHC, and Wearable, San Juan, Puerto Rico, January 30, 2015, Revised Selected Papers

Editors: Michael Brenner, Nicolas Christin, Benjamin Johnson, Kurt Rohloff

Publisher: Springer Berlin Heidelberg

Book Series: Lecture Notes in Computer Science


About this book

This book constitutes the refereed proceedings of three workshops held at the 19th International Conference on Financial Cryptography and Data Security, FC 2015, in San Juan, Puerto Rico, in January 2015.

The 22 full papers presented were carefully reviewed and selected from 39 submissions. They feature the outcome of the Second Workshop on Bitcoin Research, BITCOIN 2015, the Third Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2015, and the First Workshop on Wearable Security and Privacy, Wearable 2015.

Table of Contents

On the Malleability of Bitcoin Transactions
We study the problem of malleability of Bitcoin transactions. Our first two contributions can be summarized as follows:
we perform practical experiments on Bitcoin that show that it is very easy to maul Bitcoin transactions with high probability, and
we analyze the behavior of the popular Bitcoin wallets in the situation when their transactions are mauled; we conclude that most of them are to some extend not able to handle this situation correctly.
The contributions in points (i) and (ii) are experimental. We also address a more theoretical problem of protecting the Bitcoin distributed contracts against the “malleability” attacks. It is well-known that malleability can pose serious problems in some of those contracts. It concerns mostly the protocols which use a “refund” transaction to withdraw a financial deposit in case the other party interrupts the protocol. Our third contribution is as follows:
we show a general method for dealing with the transaction malleability in Bitcoin contracts. In short: this is achieved by creating a malleability-resilient “refund” transaction which does not require any modification of the Bitcoin protocol.
Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek
Trends, Tips, Tolls: A Longitudinal Study of Bitcoin Transaction Fees
The Bitcoin protocol supports optional direct payments from transaction partners to miners. These “fees” are supposed to substitute miners’ minting rewards in the long run. Acknowledging their role for the stability of the system, the right level of transaction fees is a hot topic of normative debates. This paper contributes empirical evidence from a historical analysis of agents’ revealed behavior concerning their payment of transaction fees. We identify several regime shifts, which can be largely explained by changes in the default client software or actions of big intermediaries in the ecosystem. Overall, it seems that rules dominate ratio, a state that is sustainable only if fees remain negligible.
Malte Möser, Rainer Böhme
ZombieCoin: Powering Next-Generation Botnets with Bitcoin
Botnets are the preeminent source of online crime and arguably the greatest threat to the Internet infrastructure. In this paper, we present ZombieCoin, a botnet command-and-control (C&C) mechanism that runs on the Bitcoin network. ZombieCoin offers considerable advantages over existing C&C techniques, most notably the fact that Bitcoin is designed to resist the very regulatory processes currently used to combat botnets. We believe this is a desirable avenue botmasters may explore in the near future and our work is intended as a first step towards devising effective countermeasures.
Syed Taha Ali, Patrick McCorry, Peter Hyun-Jeen Lee, Feng Hao
Cuckoo Cycle: A Memory Bound Graph-Theoretic Proof-of-Work
We introduce the first graph-theoretic proof-of-work system, based on finding small cycles or other structures in large random graphs. Such problems are trivially verifiable and arbitrarily scalable, presumably requiring memory linear in graph size to solve efficiently. Our cycle finding algorithm uses one bit per edge, and up to one bit per node. Runtime is linear in graph size and dominated by random access latency, ideal properties for a memory bound proof-of-work. We exhibit two alternative algorithms that allow for a memory-time trade-off (TMTO)—decreased memory usage, by a factor k, coupled with increased runtime, by a factor \(\varOmega (k)\). The constant implied in \(\varOmega ()\) gives a notion of memory-hardness, which is shown to be dependent on cycle length, guiding the latter’s choice. Our algorithms are shown to parallelize reasonably well.
John Tromp
When Bitcoin Mining Pools Run Dry
A Game-Theoretic Analysis of the Long-Term Impact of Attacks Between Mining Pools
Bitcoin has established itself as the most successful cryptocurrency with adoption seen in many commercial scenarios. While most stakeholders have jointly benefited from the growing importance of Bitcoin, conflicting interests continue to negatively impact the ecosystem. In particular, incentives to derive short-term profits from attacks on mining pools threaten the long-term viability of Bitcoin.
We develop a game-theoretic model that allows us to capture short-term as well as long-term impacts of attacks against mining pools. Using this model, we study the conditions under which the mining pools have no incentives to launch attacks against each other (i.e., peaceful equilibria), and the conditions under which one mining pool is marginalized by attacks (i.e., one-sided attack equilibria). Our results provide guidelines for ensuring that the Bitcoin ecosystem remains long-term viable and trustworthy.
Aron Laszka, Benjamin Johnson, Jens Grossklags
Issues in Designing a Bitcoin-like Community Currency
The invention of the Bitcoin protocol has opened the door to new forms of financial interaction. One such form may be to adapt Bitcoin technology for use as a community currency. A community currency is a form of money issued by a non-government entity to serve the economic or social interests of a group of people, often in a small geographic area. We propose a model of a community cryptocurrency that includes a community fund from which community members may take out loans if the community votes to approve them. We consider possible vulnerabilities and mitigations to issues that would affect this community fund, including issues of identity, voting protocols and funds management. We conclude that these vulnerabilities are, in most cases, amenable to technological mitigations that must be adaptable to both community values and changing conditions, emphasizing the need for careful currency design.
David Vandervort, Dale Gaucas, Robert St Jacques
The Bitcoin Market Potential Index
The Bitcoin Market Potential Index (BMPI) is a new composite indicator that conceptualizes and ranks the potential utility of bitcoin across 178 countries to show which countries have the most and least potential to see bitcoin adoption. The index utilizes a data set with 40 variables grouped into the index’s seven equally weighted sub-indices: technology penetration, international remittances, inflation, size of informal economy, financial repression, historical financial crises, and bitcoin penetration. Data across the different BMPI variables were first standardized as follows.
Garrick Hileman
Cryptographic Currencies from a Tech-Policy Perspective: Policy Issues and Technical Directions
We study legal and policy issues surrounding crypto currencies, such as Bitcoin, and how those issues interact with technical design options. With an interdisciplinary team, we consider in depth a variety of issues surrounding law, policy, and crypto currencies—such as the physical location where a crypto currency’s value exists for jurisdictional and other purposes, the regulation of anonymous or pseudonymous currencies, and challenges as virtual currency protocols and laws evolve. We reflect on how different technical directions may interact with the relevant laws and policies, raising key issues for both policy experts and technologists.
Emily McReynolds, Adam Lerner, Will Scott, Franziska Roesner, Tadayoshi Kohno
Blindcoin: Blinded, Accountable Mixes for Bitcoin
Mixcoin is a Bitcoin mixing protocol proposed by Bonneau et al. which provides strong accountability guarantees [13]. However, in the Mixcoin protocol, the mapping from a user’s input to output address is visible to the mixing server. We modify the Mixcoin protocol to provide guarantees that the input/output address mapping for any user is kept hidden from the mixing server. In order to achieve this, we make use of a blind signature scheme [14, 23] as well as an append-only public log. The scheme is fully compatible with Bitcoin, forces mixes to be accountable, preserves user anonymity even against a malicious mix, is resilient to denial of service attacks, and easily scales to many users.
Luke Valenta, Brendan Rowan
Privacy-Enhancing Overlays in Bitcoin
In this paper, we explore the role of privacy-enhancing overlays in Bitcoin. To examine the effectiveness of different solutions, we first propose a formal definitional framework for virtual currencies and put forth a new notion of anonymity, taint resistance, that they can satisfy. We then approach the problem from a theoretical angle, by proposing various solutions to achieve provable taint resistance, and from a practical angle, by examining the taint resistance of the Coinjoin protocol.
Sarah Meiklejohn, Claudio Orlandi
Search-and-Compute on Encrypted Data
Private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the user’s sensitive data will be protected from exposure. Given an encrypted database, the users typically submit queries similar to the following examples:
  • How many employees in an organization make over $100,000?
  • What is the average age of factory workers suffering from leukemia?
Answering the above questions requires one to search and then compute over the encrypted databases in sequence. In the case of privately processing queries with only one of these operations, many efficient solutions have been developed using a special-purpose encryption scheme (e.g., searchable encryption). In this paper, we are interested in efficiently processing queries that need to perform both operations on fully encrypted databases. One immediate solution is to use several special-purpose encryption schemes at the same time, but this approach is associated with a high computational cost for maintaining multiple encryption contexts. The other solution is to use a privacy homomorphic scheme. However, no secure solutions have been developed that meet the efficiency requirements.
In this work, we construct a unified framework so as to efficiently and privately process queries with “search” and “compute” operations. To this end, the first part of our work involves devising some underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of the circuit primitives. One technique is to exploit SIMD techniques to accelerate their basic operations. In contrast to general SIMD approaches, our SIMD implementation can be applied even when one basic operation is executed. The other technique is to take a large integer ring (e.g., \(\mathbb {Z}_{2^{t}}\)) as a message space instead of a binary field. Even for an integer of k bits with \(k>t\), addition can be performed with degree 1 circuits with lazy carry operations. Finally, we present various experiments by varying the parameters, such as the query type and the number of tuples.
Jung Hee Cheon, Miran Kim, Myungsun Kim
Accelerating SWHE Based PIRs Using GPUs
In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doröz et al. construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14–34 times speedup for index comparison and 4–18 times speedup for data aggregation compared to a pure CPU software implementation.
Wei Dai, Yarkın Doröz, Berk Sunar
Combining Secret Sharing and Garbled Circuits for Efficient Private IEEE 754 Floating-Point Computations
Two of the major branches in secure multi-party computation research are secret sharing and garbled circuits. This work succeeds in combining these to enable seamlessly switching to the technique more efficient for the required functionality. As an example, we add garbled circuits based IEEE 754 floating-point numbers to a secret sharing environment achieving very high efficiency and the first, to our knowledge, fully IEEE 754 compliant secure floating-point implementation.
Pille Pullonen, Sander Siim
Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in PIR
Private Information Retrieval (PIR) protects users’ privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a “real world” level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an underlying secret-key (somewhat) additively homomorphic encryption scheme, and has been reused in numerous subsequent works in the PIR community (PETS 2012, FC 2013, NDSS 2014, etc.).
In this paper, we show that this encryption scheme is not one-way: we present an attack that decrypts arbitrary ciphertext without the secret key, and is quite efficient: it amounts to applying the LLL algorithm twice on small matrices. Used against existing practical instantiations of PIR protocols, it allows the server to recover the users’ access pattern in a matter of seconds.
Tancrède Lepoint, Mehdi Tibouchi
Homomorphic Computation of Edit Distance
These days genomic sequence analysis provides a key way of understanding the biology of an organism. However, since these sequences contain much private information, it can be very dangerous to reveal any part of them. It is desirable to protect this sensitive information when performing sequence analysis in public. As a first step in this direction, we present a method to perform the edit distance algorithm on encrypted data to obtain an encrypted result. In our approach, the genomic data owner provides only the encrypted sequence, and the public commercial cloud can perform the sequence analysis without decryption. The result can be decrypted only by the data owner or designated representative holding the decryption key.
In this paper, we describe how to calculate edit distance on encrypted data with a somewhat homomorphic encryption scheme and analyze its performance. More precisely, given two encrypted sequences of lengths n and m, we show that a somewhat homomorphic scheme of depth \({\mathcal {O}}((n+m) \log \log (n+m))\) can evaluate the edit distance algorithm in \({\mathcal {O}}(nm \log (n+m))\) homomorphic computations. In the case of \(n=m\), the depth can be brought down to \({\mathcal {O}}(n)\) using our optimization technique. Finally, we present the estimated performance of the edit distance algorithm and verify it by implementing it for short DNA sequences.
Jung Hee Cheon, Miran Kim, Kristin Lauter
HEtest: A Homomorphic Encryption Testing Framework
In this work, we present a generic open-source software framework that can evaluate the correctness and performance of homomorphic encryption software. Our framework, called HEtest, automates the entire process of a test: generation of data for testing (such as circuits and inputs), execution of a test, comparison of performance to an insecure baseline, statistical analysis of the test results, and production of a LaTeX report. To illustrate the capability of our framework, we present a case study of our analysis of the open-source HElib homomorphic encryption software. We stress though that HEtest is written in a modular fashion, so it can easily be adapted to test any homomorphic encryption software.
Mayank Varia, Sophia Yakoubov, Yang Yang
Users’ Privacy Concerns About Wearables
Impact of Form Factor, Sensors and Type of Data Collected
Wearables have become popular in several application domains, including healthcare, entertainment and security. Their pervasiveness, small size and autonomy, enlarges the potential of these devices to be employed in different activities and scenarios. Wearable devices collect data ubiquitously and continuously, about the individual user and also her surroundings, which can pose many privacy challenges that neither users nor stakeholders are ready to deal with. Before designing effective solutions for developing privacy-enhanced wearables, we need first to identify and understand what are the potential privacy concerns that users have and how they are perceived. To contribute to that purpose, in this paper we present findings from a qualitative content analysis of online comments regarding privacy concerns of wearable device users. We also discuss how form factors, sensors employed, and the type of data collected impact the users’ perception of privacy. Our results show that users have different levels and types of privacy concerns depending on the type of wearable they use. By better understanding the users’ perspectives about wearable privacy, we aim at helping designers and researchers to develop effective solutions to create privacy-enhanced wearables.
Vivian Genaro Motti, Kelly Caine
On Vulnerabilities of the Security Association in the IEEE 802.15.6 Standard
Wireless Body Area Networks (WBAN) support a variety of real-time health monitoring and consumer electronics applications. The latest international standard for WBAN is the IEEE 802.15.6. The security association in this standard includes four elliptic curve-based key agreement protocols that are used for generating a master key. In this paper, we challenge the security of the IEEE 802.15.6 standard by showing vulnerabilities of those four protocols to several attacks. We perform a security analysis on the protocols, and show that they all have security problems, and are vulnerable to different attacks.
Mohsen Toorani
Visual Cryptography and Obfuscation: A Use-Case for Decrypting and Deobfuscating Information Using Augmented Reality
As new technologies emerge such as wearables, it opens up for new challenges, especially related to security and privacy. One such recent technology is smart glasses. The use of glasses introduces security and privacy concerns for the general public but also for the user itself. In this paper we present work which focus on privacy of the user during authentication. We propose and analyze two methods, visual cryptography and obfuscation for protecting the user against HUD and camera logging adversaries as well as shoulder-surfing.
Patrik Lantz, Bjorn Johansson, Martin Hell, Ben Smeets
Ok Glass, Leave Me Alone: Towards a Systematization of Privacy Enhancing Technologies for Wearable Computing
In the coming age of wearable computing, devices such as Google Glass will become as ubiquitous as smartphones. Their foreseeable deployment in public spaces will cause distinct implications on the privacy of people recorded by these devices. Particularly the discreet recording capabilities of such devices pose new challenges to consensual image disclosure. Therefore, new Privacy Enhancing Technologies (PETs) will be needed to help preserve our digital privacy. At the time of writing, no such PETs are available on the market to communicate privacy preferences towards Glass. In the scientific literature, a handful of approaches has been presented. However, none of them has been evaluated regarding their affordances and overall usefulness. In this paper, we provide the first systematization and qualitative evaluation of state of the art PETs that were designed to communicate privacy preferences towards (wearable) cameras, such as Google Glass. The purpose of this paper is to foster a broader discourse on how such technology should be designed in order to be fully privacy preserving and usable.
Katharina Krombholz, Adrian Dabrowski, Matthew Smith, Edgar Weippl
Design and Analysis of Shoulder Surfing Resistant PIN Based Authentication Mechanisms on Google Glass
This paper explores options to the built-in authentication mechanism of the Google Glass which is vulnerable to shoulder surfing attacks. Two simple PIN-based authentication techniques are presented, both of which provide protection against shoulder surfing. The techniques employ two interfaces for entering the PIN, namely, voice (Voice-based PIN) and touchpad (Touch-based PIN). To enter the same PIN, user has the freedom to choose either technique and thereby interface, as per the environment in which authentication is being performed. A user study was conducted with 30 participants to compare the performance of the proposed methods with the built-in technique. The results show that the proposed mechanisms have a significantly better login success rate than the built-in technique. Interestingly, although the average authentication times of the proposed methods are higher than that of the built-in one, the users perceived them as being faster. The results also indicate that the proposed methods have better perceived security and usability than the built-in method. The study reveals that when it comes to authentication on augmented reality devices, there is a need for authentication mechanisms that complement each other as users tend to prefer a different interface in different contexts.
Dhruv Kumar Yadav, Beatrice Ionascu, Sai Vamsi Krishna Ongole, Aditi Roy, Nasir Memon
Glass OTP: Secure and Convenient User Authentication on Google Glass
Wearable computing devices have become increasingly popular and while these devices promise to improve our lives, they come with new challenges. This paper focuses on user authentication mechanisms for the Google Glass device (Glass). Glass only has three sources of input: a camera, a microphone, and a touchpad. This limited set of interfaces makes the use of standard passwords infeasible or cumbersome. We therefore propose a One-Time-Password (OTP) authentication scheme, Glass OTP that uses the Glass camera to scan a QR code displayed on the user’s smartphone. We implement a proof of concept Glass lock screen which unlocks only upon scanning an OTP generated by the companion Android smartphone application. We also discuss the reliability, security, and convenience of the proposed solution as compared to the current solutions in use.
Pan Chan, Tzipora Halevi, Nasir Memon
Financial Cryptography and Data Security
Michael Brenner
Nicolas Christin
Benjamin Johnson
Kurt Rohloff
Copyright Year
Springer Berlin Heidelberg
Electronic ISBN
Print ISBN

Premium Partner