International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Alptekin Küpçü

Publications

Year
Venue
Title
2017
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2013
EUROCRYPT
2009
EPRINT
Framework for Analyzing Optimistic Fair Exchange with Distributed Arbiters
Alptekin Küpçü Anna Lysyanskaya
Fair exchange is one of the most fundamental problems in secure distributed computation. Alice has something that Bob wants, and Bob has something that Alice wants. A fair exchange protocol would guarantee that, even if one of them maliciously deviates from the protocol, either both of them get the desired content, or neither of them do. It is known that no two-party protocol can guarantee fairness in general; therefore the presence of a trusted arbiter is necessary. In optimistic fair exchange, the arbiter only gets involved in case of faults. To reduce the trust put in an arbiter, it is natural to consider employing multiple arbiters. Avoine and Vaudenay (AV) [6] employ multiple autonomous arbiters in their optimistic fair exchange protocol which uses timeout mechanisms. They leave two open questions: (1) Can an optimistic fair exchange protocol without timeouts provide fairness when employing multiple autonomous arbiters? (2) Can any other optimistic fair exchange protocol with timeouts achieve better bounds on the number of honest arbiters required? In this paper, we answer both questions negatively. To answer these questions, we define a general class of optimistic fair exchange protocols with multiple arbiters, called “distributed arbiter fair exchange” (DAFE) protocols. Informally, in a DAFE protocol, if a participant fails to send a correctly formed message, the other party must contact some subset of the arbiters and get correctly formed responses from them. The arbiters do not talk to each other, but only to Alice and Bob. We prove that no DAFE protocol can exist. However, our impossibility results can be overcome in the timeout model (where all arbiters have access to loosely synchronized clocks) and also in case the arbiters can communicate (e.g., using secure multi-party computation with Omega(n^2) communication).
2008
EPRINT
Dynamic Provable Data Possession
As online storage-outsourcing services (e.g., Amazon's S3) and resource-sharing networks (e.g., peer-to-peer and grid networks) became popular, the problem of efficiently proving the integrity of data stored at untrusted servers has received increased attention. Ateniese et al. \cite{pdp} formalized this problem with a model called provable data possession (PDP). In this model, data is preprocessed by the client and then sent to an untrusted server for storage. The client can then challenge the server to prove that the data has not been tampered with or deleted (without sending the actual data). However, their PDP scheme applies only to static (or append-only) files. In reality, many outsourced storage applications (including network file systems and outsourced databases) need to handle dynamic data. This paper presents a definitional framework and an efficient construction for dynamic provable data possession (DPDP), which extends the PDP model to support provable updates to stored data (modifications to a block or insertion/deletion of a block). To achieve efficient DPDP, we use a new version of authenticated dictionaries based on rank information. The price of dynamic updates is a performance change from $O(1)$ to $O(\log{n})$, for a file consisting of $n$ blocks, while maintaining the same probability of detection. Yet, our experiments show that this price is very low in practice, and hence our system is applicable to real scenarios. Our contributions can be summarized as defining the DPDP framework formally, and constructing the first fully dynamic PDP solution, which performs verification without downloading actual data and is very efficient. We also show how our DPDP scheme can be extended to construct complete file systems and version control systems (e.g., CVS) at untrusted servers, so that it can be used in complex outsourcing applications.
2008
EPRINT
Usable Optimistic Fair Exchange
Alptekin Küpçü Anna Lysyanskaya
Fairly exchanging digital content is an everyday problem. It has been shown that fair exchange cannot be done without a trusted third party (called the Arbiter). Yet, even with a trusted party, it is still non-trivial to come up with an efficient solution, especially one that can be used in a p2p file sharing system with a high volume of data exchanged. We provide an efficient optimistic fair exchange mechanism for bartering digital files, where receiving a payment in return to a file (buying) is also considered fair. The exchange is optimistic, removing the need for the Arbiter’s involvement unless a dispute occurs. While the previous solutions employ costly cryptographic primitives for every file or block exchanged, our protocol employs them only once per peer, therefore achieving O(n) efficiency improvement when n blocks are exchanged between two peers. The rest of our protocol uses very efficient cryptography, making it perfectly suitable for a p2p file sharing system where tens of peers exchange thousands of blocks and they do not know beforehand which ones they will end up exchanging. Thus, for the first time, a provably secure (and privacy respecting when payments are made using e-cash) fair exchange protocol is being used in real bartering applications (e.g., BitTorrent) [14] without sacrificing performance.