The kidney exchange problem (KEP) seeks to find possible exchanges among pairs of patients and their incompatible kidney donors while meeting specific optimization criteria such as maximizing the overall number of possible transplants. Recently, several privacy-preserving protocols for solving the KEP have been proposed. However, the protocols known to date lack scalability in practice since the KEP is an NP-complete problem. We address this issue by proposing a novel privacy-preserving protocol which computes an approximate solution for the KEP that scales well for the large numbers of patient-donor pairs encountered in practice. As opposed to prior work on privacy-preserving kidney exchange, our protocol is generic w.r.t. the security model that can be employed. Compared to the most efficient privacy-preserving protocols for kidney exchange existing to date, our protocol is entirely data oblivious and it exhibits a far superior run time performance. As a second contribution, we use a real-world data set to simulate the application of our protocol as part of a kidney exchange platform, where patient-donor pairs register and de-register over time, and thereby determine its approximation quality in a real-world setting.

Traditionally, kidney exchange allows patients with an incompatible living kidney donor to exchange their donors in form of exchange cycles. Today, additional transplants are achieved through so-called exchange chains. These are initiated by an altruistic donor, who donates a kidney without requiring anything in return. In practice, kidney exchange is typically facilitated through central platforms, which compute potential exchange cycles and chains for a large number of patients and donors. To overcome the severe security issues of this centralized approach, several secure multi-party computation (SMPC) protocols for kidney exchange have been proposed recently. However, the privacy-preserving protocols proposed to date either do not scale for a sufficient number of patients and donors or do not support exchange chains. In this paper, we present the first SMPC protocol that both supports exchange chains and yields efficient run times for a large number of patients and donors. We have implemented our protocol in the framework MP-SPDZ and evaluated its run time performance. Besides, we present evaluation results based on real-world data for the use of our protocol in a dynamic setting, where patient-donor pairs and altruistic donors arrive and depart over time.

The Kidney Exchange Problem (KEP) aims at finding an optimal set of exchanges among pairs of patients and their medically incompatible living kidney donors as well as altruistic donors who are not associated with any particular patient but want to donate a kidney to any person in need. Existing platforms that offer the finding of such exchanges for patient-donor pairs and altruistic donors are organized in a centralized fashion and operated by a single platform operator. This makes them susceptible to manipulation and corruption. Recent research has targeted these security issues by proposing decentralized Secure Multi-Party Computation (SMPC) protocols for solving the KEP. However, these protocols fail to meet two important requirements for kidney exchange in practice. First, they do not allow for altruistic donors. While such donors are not legally allowed in all countries, they have been shown to have a positive effect on the number of transplants that can be found. Second, the existing SMPC protocols do not support prioritization, which is used in existing platforms to give priority to certain exchanges or patient-donor pairs, e.g., to patients who are hard to match due to their medical characteristics. In this paper, we introduce a generic gate for implementing prioritization in kidney exchange. We extend two existing SMPC protocols for solving the KEP such that they allow for altruistic donors and prioritization and present one novel SMPC protocol for solving the KEP with altruistic donors and prioritization based on dynamic programming. We prove the security of all protocols and analyze their complexity. We implement all protocols and evaluate their performance for the setting where altruistic donors are legally allowed and for the setting where they are not. Thereby, we determine the performance impact of the inclusion of altruistic donors and obtain those approaches that perform best for each setting.

The current cyber insurance model is poorly suited for and does not aid the cyber resilience of the maritime transport system. Traditional maritime insurance increasingly exempts cyber claims from policies making cyber insurance a necessity for protecting against cyber risk. With an ever-growing number of cyber events in the maritime transportation system, effective cyber insurance is a necessary investment. Our paper attempts to address this disconnect by analyzing the current cyber insurance marketplace in the maritime transportation system and identifying challenges and opportunities that aim to increase resilience.

To this day, there are still some countries where the exchange of kidneys between multiple incompatible patient-donor pairs is restricted by law. Typically, legal regulations in this context are put in place to prohibit coercion and manipulation in order to prevent a market for organ trade. Yet, in countries where kidney exchange is practiced, existing platforms to facilitate such exchanges generally lack sufficient privacy mechanisms. In this paper, we propose a privacy-preserving protocol for kidney exchange that not only addresses the privacy problem of existing platforms but also is geared to lead the way in overcoming legal issues in those countries where kidney exchange is still not practiced. In our approach, we use the concept of secret sharing to distribute the medical data of patients and donors among a set of computing peers in a privacy-preserving fashion. These computing peers then execute our new Secure Multi-Party Computation (SMPC) protocol among each other to determine an optimal set of kidney exchanges. As part of our new protocol, we devise a privacy-preserving solution to the maximum matching problem on general graphs. We have implemented the protocol in the SMPC benchmarking framework MP-SPDZ and provide a comprehensive performance evaluation. Furthermore, we analyze the practicality of our protocol when used in a dynamic setting where patients and donors arrive and depart over time) based on a data set from the United Network for Organ Sharing.

The kidney exchange problem (KEP) seeks to determine a constellation of exchanges that maximizes the number of possible transplants between a set of patients and their incompatible donors. Recently, Secure Multi-Party Computation (SMPC) techniques were used to devise privacy-preserving protocols that allow the solving of the KEP in a distributed fashion. However, these protocols lack sufficient performance in practice. In the non-privacy-preserving case, the most efficient algorithms solving the KEP are based on integer programming. It is in this context, that we propose a privacy-preserving protocol based on these integer programming techniques that efficiently solves the KEP in a privacy-preserving fashion. We prove the security of this protocol and analyze its complexity. Furthermore, we provide a comprehensive performance evaluation of an implementation of the protocol in the SMPC benchmarking framework MP-SPDZ.

Secure Multi-Party Computation (SMPC) allows a set of parties to securely compute a functionality in a distributed fashion without the need for any trusted external party. Usually, it is assumed that the parties know each other and have already established authenticated channels among each other. However, in practice the parties sometimes must stay anonymous. In this paper, we conceptualize a framework that enables the repeated execution of an SMPC protocol for a given functionality such that the parties can keep their participation in the protocol executions private and at the same time be sure that only authorized parties may take part in a protocol execution. We identify the security properties that an implementation of our framework must meet and introduce a first implementation of the framework that achieves these properties.

The primitive of conditional random selection allows the selection of a data record uniformly at random from the subset of data records that meet a specified condition. In this paper, we extend a previously introduced privacy-preserving two-party protocol (that implements this primitive in the context of passive adversaries) to the multi-party case. Additionally, we provide a comprehensive performance analysis of the newly designed protocol and discuss application scenarios.

A subgraph check is a variant of the common subgraph matching-operating on a reference and a test graph- determining whether a test graph is a subgraph of the reference graph. In this paper, we present two novel privacy-preserving subgraph checking protocols. In our first protocol, all subgraph checks are carried out independently of each other. The second protocol allows for a substantial performance improvement over the straight-forward approach of the first protocol by exploiting structural similarities among the test graphs to be checked against the reference graph.

Current bartering platforms place the burden of finding simultaneously executable quotes on their users. In addition, these bartering platforms do not keep quotes private. To address these shortcomings, this paper introduces a privacy-preserving bartering protocol secure in the semi-honest model. At its core, the novel bartering protocol uses a newly-developed bipartite matching protocol which determines simultaneously executable quotes in an efficient manner. While the new privacy-preserving bipartite matching protocol does not always yield the maximal set of simultaneously executable quotes, it keeps the parties' quotes private at all times. Moreover, our new privacy-preserving bipartite matching protocol is more efficient than existing solutions in that it only requires linear communication in the number of quotes the parties specify.

A majority of electronic bartering transactions is carried out via online platforms. Typically, these platforms require users to disclose sensitive information about their trade capabilities which might restrict their room for negotiation. It is in this context that we propose a novel decentralized and privacy-preserving bartering protocol for multiple parties that offers the same privacy guarantees as provided by traditional bartering and by cash payments. The proposed protocol is even secure against an active attacker who controls a majority of colluding parties.

This paper introduces two-party protocols for various operations on two integer intervals that are privacy-preserving in the semi-honest model. Specifically, this work proposes new protocols for determining whether two intervals overlap; computing the boundaries and size of the overlap; and selecting a random sub-interval within the overlap. The protocols are presented both for homomorphic encryption and for secret sharing as basic secure multi-party computation techniques. Moreover, this paper presents a comprehensive performance evaluation of the newly-developed protocols.

Both B2B bartering as well as bartering between individuals is increasingly facilitated through online platforms. However, these platforms lack automation and neglect the privacy of their users by leaking crucial information about their offers and demands. It is in this context that we introduce the first privacy-preserving two-party bartering protocol which is secure against active attackers. As main building blocks, our bartering protocol uses novel protocols operating on common encrypted input for securely selecting an element out of multiple elements, securely selecting a random element out of an interval, and obliviously shrinking an interval which are of independent interest.

In this paper, we introduce a new primitive - referred to as conditional random selection. This new primitive allows the random selection of a data record from the subset of data records that meet a specified condition. We present a new privacy-preserving protocol that implements the new primitive and is secure in the semi-honest model. At its core, it uses newly developed protocols for oblivious shuffling, oblivious swapping, and privacy-preserving less than comparison on binary values with shared output. We show the relevance of conditional random selection in various application scenarios.

Bartering plays a significant role in today's global economy-both between individuals as well as in B2B settings. However, aside from lacking automation, today's bartering solutions and supporting platforms typically neglect the privacy needs of their users. In this paper, we present a novel two-party protocol which addresses these shortcomings. The new protocol automatically determines whether the desired and offered commodities and quantities overlap in such a way that both parties are willing to barter. Throughout the protocol, the commodities and quantities as specified by the parties are kept private. We show that the protocol is privacy-preserving in the semi-honest model. As main building blocks, the new bartering protocol uses a novel privacy-preserving protocol for selecting a random subinterval out of the overlap of two intervals as well as a newly-developed secure protocol for input-symmetric strong conditional oblivious transfer.

In this paper we introduce the novel notion called Verifiable Private Equality Test (VPET) and propose an efficient 2-party protocol for its implementation. VPET enables two parties to securely perform an arbitrary number of comparisons on a fixed collection of (key, value) pairs and thus it is more generic than existing techniques such as Private Equality Test and Private Set Intersection.

Recently, new protocols were proposed which allow two parties to reconcile their ordered input sets in a fair and privacy-preserving manner. In this paper we present the design and implementation of these protocols on different platforms and extensively study their performance.

This paper introduces a new parallel algorithm that allows for an efficient LLL reduction using today's emerging many-core systems. This work develops suitable methods that efficiently implement the idea of splitting a lattice basis into smaller sub problems, LLL reducing the sub problems, and recombining the sub problems afterwards to obtain an overall LLL reduced basis. The new many-core algorithm outperforms any current parallel LLL algorithm. Experiments on a 48-core test system show a speed-up of approximately 10 for SVP challenge type lattice bases and a remarkable speed-up of approximately 50 for knapsack type lattice bases.

Mobile ad-hoc networks are becoming ever more popular due to their flexibility, low cost, and ease of deployment. However, to achieve these benefits the network must employ a sophisticated routing protocol. Early proposed routing protocols were not designed to operate in the presence of attackers. There have been many subsequent attempts to secure these protocols, each with its own advantages and disadvantages. To allow for a comparison of these secure protocols, a single common attacker model is needed. Our first contribution in this work is to develop a comprehensive attacker model categorizing attackers based on their capabilities. This is in contrast to the existing models which seek to categorize attacks and then map that categorization back onto the attackers. Our second contribution is an analysis of the SAODV routing protocol using our new model, which demonstrates the structured approach inherent in our model and its benefits compared to existing work.

Passwords are ubiquitous, and users and service providers alike rely on them for their security. However, good passwords may sometimes be hard to remember. For years, security practitioners have battled with the dilemma of how to authenticate people who have forgotten their passwords. Existing approaches suffer from high false positive and false negative rates, where the former is often due to low entropy or public availability of information, whereas the latter often is due to unclear or changing answers, or ambiguous or fault prone entry of the same. Good security questions should be based on long-lived personal preferences and knowledge, and avoid publicly available information. We show that many of the questions used by online matchmaking services are suitable as security questions. We first describe a new user interface approach suitable to such security questions that is offering a reduced risks of incorrect entry. We then detail the findings of experiments aimed at quantifying the security of our proposed method.

Organizations use security policies to regulate how they share and exchange information, e.g., under what conditions data can be exchanged, what protocols are to be used, who is granted access, etc. Agreement on specific policies is achieved though policy reconciliation, where multiple parties, with possibly different policies, exchange their security policies, resolve differences, and reach a consensus. Current solutions for policy reconciliation do not take into account the privacy concerns of reconciliating parties. This paper addresses the problem of preserving privacy during security policy reconciliation. We introduce new protocols that meet the privacy requirements of the organizations and allow parties to find a common policy rule which maximizes their individual preferences.

GSM suffers from various security weaknesses: Just recently, Barkan, Biham and Keller presented a ciphertext-only attack on the GSM encryption algorithm A5/2 which recovers the encryption key from a few dozen milliseconds of encrypted traffic within less than a second. Furthermore, it is well-known that it is possible to mount a man-in-the-middle attack in GSM during authentication which allows an attacker to make a victim mobile station authenticate itself to a fake base station which in turn forwards the authentication traffic to the real network, thus impersonating the victim mobile station to a real network and vice versa. We discuss the impact of GSM encryption attacks, that recover the encryption key, and the man-in-the-middle attack on the security of networks, which employ UMTS and GSM base stations simultaneously. We suggest to protect UMTS connections from GSM attacks by integrating an additional authentication and key agreement on intersystem handovers between GSM and UMTS.

This paper examines the use of Bluetooth for a collaborative music creation system called codeBLUE where the low cost, low power and small dimensions of Bluetooth technology are critical. Dancers using the codeBLUE system wear clothing incorporating Bluetooth-enabled sensors that measure and transmit information about the dancers' movements to a Bluetooth access point positioned in the demonstration area, which in turn forwards the information to a control system. The system software transforms the simple dance movements into musical modifications in real time, altering the melodic, rhythmic, and dynamic properties of the music stream in terms of MIDI parameters. A configuration console allows the DJ to modify the effects that each type of sensor produces, providing him or her yet another channel of creativity and keeping the codeBLUE experience fresh for participants. The paper describes the architecture, design, and hardware and software implementation of the codeBLUE proof-of-concept prototype. The paper also discusses our evaluation of the technology used for this application. The system has been successfully demonstrated to a live audience.

We propose a technique to reliably generate a cryptographic key from a user's voice while speaking a password. The key resists cryptanalysis even against an attacker who captures all system information related to generating or verifying the cryptographic key. Moreover, the technique is sufficiently robust to enable the user to reliably regenerate the key by uttering her password again. We describe an empirical evaluation of this technique using 250 utterances recorded from 50 users.

We present a novel approach to improving the security of passwords. In our approach, the legitimate user's typing patterns (e.g., durations of keystrokes, and latencies between keystrokes) are combined with the user's password to generate a hardened password that is convincingly more secure than conventional passwords against both online and offline attackers. In addition, our scheme automatically adapts to gradual changes in a user's typing patterns while maintaining the same hardened password across multiple logins, for use in file encryption or other applications requiring a longterm secret key. Using empirical data and a prototype implementation of our scheme, we give evidence that our approach is viable in practice, in terms of ease of use, improved security, and performance