Financial Cryptography

The advent of the Internet was believed to be a critical factor in accelerating the ease of distribution and overall adoption of ”E-Payment” schemes. However, the ”dot-com” boom of the late 1990’s yielded few successful new payment systems. Instead, many recurring problems plagued the Internet-based schemes, and an examination of these persistent pitfalls suggests necessary changes in approach for future ”E-Payment” entrepreneurs.

We present the ”Peppercoin” method for processing micropayments efficiently. With this method, a fraction of the micropayments received are determined, via a procedure known as ”cryptographic selection,” to qualify for upgrade to a macropayment. The merchant deposits the upgraded micropayments as macropayments, and merely logs locally the non-qualifying micropayments. In this manner, the merchant transforms a large collection of small micropayments into a smaller collection of macropayments, of the same total expected value. The merchant pays much less for processing the resulting macropayments, since there are fewer of them. Consumers are billed for exactly the amount they spend, based on auxiliary information recorded in each micropayment. The method is highly secure, and compatible with existing payment mechanisms such as credit cards.

With the explosive growth of mobile communications, users may often access value-added services through foreign service providers. These providers will interact directly with users, later providing details to a user’s home service provider regarding the services rendered; the home service provider, in turn, bills the user. One critical concern is that the foreign service provider might inflate the usage figures it furnishes to the home service provider. In this paper, we address this issue using a microcredit scheme. The scheme is efficient as the verification time required by the home service provider is only logarithmic in the number of microcredit transactions, and the verification time required by the foreign service provider is constant. Moreover, the communication complexity per microcredit transaction between the user and foreign service provider is also constant. The scheme uses QuasiModo trees, which have been previously applied to certificate revocation. It improves upon previous chain-based proposals and their tree-based analogues. As a byproduct, our scheme yields a micropayment protocol which is an improvement over tree schemes with respect to both communication complexity and time complexity (in both cases by a factor of approximately 2, amortized).

Systems for the support of customer relationship management are becoming increasingly attractive for vendors. Loyalty systems provide an interesting possibility for vendors in customer relationship management. This holds for both real world and online vendors. However, beside some potential benefits of a loyalty system, customers may also fear an invasion into their privacy, and may thus refuse to participate in such programs. In this paper, we present a privacy-friendly loyalty system to be used by online vendors to issue loyalty points. The system prevents vendors from exploiting data for the creation of customer profiles by providing unconditional unlinkability of loyalty points with regard to purchases. In the proposed system, we apply the difficulty for the computation of discrete logarithms in a group of prime order to construct a secure and privacy-friendly counter. More precisely, all computations are carried out over special cryptographic groups based on elliptic curves where the decisional Diffie-Hellman problems can be solved easily while the computational Diffie-Hellman is believed to be hard.

Pinkas and Sander’s (2002) login protocol protects against online guessing attacks by employing human-in-the-loop techniques (also known as Reverse Turing Tests or RTTs). We first note that this, and other protocols involving RTTs, are susceptible to minor variations of well-known middle-person attacks, and suggest techniques to address such attacks. We then present complementary modifications in what we call a history-based protocol with RTT’s. Preliminary analysis indicates that the new protocol offer opportunities for improved security, improved user-friendliness (fewer RTTs to legitimate users), and greater flexibility (e.g. in customizing protocol parameters to particular situations).

We introduce an authentication framework called Query-Directed Passwords (QDP) that incorporates the convenience of authentication by long-term knowledge questions and offers stronger security than from traditional types of personal questions. Security is strengthened for this scheme by imposing several restrictions on the questions and answers, and specifying how QDP is implemented in conjunction with other factors. Four QDP implementations are examined for call center applications. We examine the security and convenience of one of these implementations in detail. This implementation involves client-end storage of questions in a computer file or a wallet card, and follows a basic challenge-response authentication protocol.

This is a brief summary of the invited lecture delivered during the conference. The interested reader is referred to [2] for more information.

MasterCard provides internationally accepted debit and credit payment programs. These programs provide cost-effective solutions that enable transactions to be performed in a wide variety of acceptance environments.

Looking at current cryptographic-based e-voting protocols, one can distinguish three basic design paradigms (or approaches): (a) Mix-Networks based, (b) Homomorphic Encryption based, and (c) Blind Signatures based. Each of the three possesses different advantages and disadvantages w.r.t. the basic properties of (i) efficient tallying, (ii) universal verifiability, and (iii) allowing write-in ballot capability (in addition to predetermined candidates). In fact, none of the approaches results in a scheme that simultaneously achieves all three. This is unfortunate, since the three basic properties are crucial for efficiency, integrity and versatility (flexibility), respectively. Further, one can argue that a serious business offering of voting technology should offer a flexible technology that achieves various election goals with a single user interface. This motivates our goal, which is to suggest a new ”vector-ballot” based approach for secret-ballot e-voting that is based on three new notions: Provably Consistent Vector Ballot Encodings, Shrink-and-Mix Networks and Punch-Hole-Vector-Ballots. At the heart of our approach is the combination of mix networks and homomorphic encryption under a single user interface; given this, it is rather surprising that it achieves much more than any of the previous approaches for e-voting achieved in terms of the basic properties. Our approach is presented in two generic designs called ”homomorphic vector-ballots with write-in votes” and ”multi-candidate punch-hole vector-ballots”; both of our designs can be instantiated over any homomorphic encryption function.

Most voting schemes rely on a number of authorities. If too many of these authorities are dishonest then voter privacy may be violated. To give stronger guarantees of voter privacy Kiayias and Yung [1] introduced the concept of elections with perfect ballot secrecy. In this type of election scheme it is guaranteed that the only thing revealed about voters’ choices is the result of the election, no matter how many parties are corrupt. Our first contribution is to suggest a simple voting scheme with perfect ballot secrecy that is more efficient than [1].

Considering the question of achieving maximal privacy in other protocols, we look at anonymous broadcast. We suggest the notion of perfect message secrecy; meaning that nothing is revealed about who sent which message, no matter how many parties are corrupt. Our second contribution is an anonymous broadcast channel with perfect message secrecy built on top of a broadcast channel.

Biometrics are receiving a lot of attention because of the potential to increase the accuracy and reliability of identification and authentication functions. A lot of research has been done to assess the performance of biometric systems, with an emphasis on false acceptances and rejections. Much less research has been done on the usability and acceptability of biometric security systems. A number of factors are increasing the usability of biometric devices. The sensors are getting smaller, cheaper, more reliable, and designed with better ergonomic characteristics. The biometric algorithms are also getting better, and many systems include features to train the users and provide feedback during use. In addition, biometric devices are being integrated into associated security systems, such as access control and encryption services, to provide a seamless environment.

Mental models that may be useful in communicating within security communities can communicate perverse incentives to naïve end users. When experts use models and metaphors in their own explanations and understanding of a systems, the metaphors are used to explain a particular element of a system based on a common understanding. When experts communicate to non-experts then those who are not expert then those end users take more than is intended by the expert.

System Administrators are users too! While the focus of human-computer interaction in security has to this point in time been on end-users, an important class of users who manage networked systems should not be ignored. In fact, system administrators may have more effect on security than individual users since they manage larger systems on behalf of users. End-users have become dependent upon the availability of services such as network-attached storage, authentication servers, web servers, and email gateways. These Internet-scale services often have thousands of hardware and software components and require considerable amounts of human effort to plan, configure, install, upgrade, monitor, troubleshoot, and sunset. The complexity of managing these services is alarming in that a recent survey of three Internet site showed that 51% of all failures are caused by operator errors [1].

Software correctness alone is not sufficient to achieve security, as some viruses and e-mail worms have demonstrated. For example, the Love Letter worm caused widespread damage even though it did not exploit any software flaws. It spread because users were unaware that attempting to view an attachment would damage their files and propagate the worm. User expectations are an essential part of the definition of computer security.

Many companies have brought new Internet payment systems to market, and many have failed. Innovative technology is important, but obviously not sufficient. Technology must match consumer interests and the changing legal environment.

We propose a new cryptographically protected multi-round auction mechanism for online auctions. This auction mechanism is designed to provide (in this order) security, cognitive convenience, and round-effectiveness. One can vary internal parameters of the mechanism to trade off bid privacy and cognitive costs, or cognitive costs and the number of rounds. We are aware of no previous work that interleaves cryptography explicitly with the mechanism design.

This paper presents a secure Generalized Vickrey Auction (GVA) scheme that does not require third-party servers, i.e., the scheme is executed only by an auctioneer and bidders. Combinatorial auctions, in which multiple goods are sold simultaneously, have recently attracted considerable attention. The GVA can handle combinatorial auctions and has good theoretical characteristics such as incentive compatibility and Pareto efficiency.

Secure GVA schemes have been developed to prevent frauds by an auctioneer. However, existing methods require third-party servers to execute the protocol. Having third-party servers that are operated by independent organizations is difficult in practice. Therefore, it is desirable that a protocol be executed by the participants themselves. However, if bidders take part in the execution of the auction procedure, a bidder might have an incentive to be an active adversary so that he manipulates the declarations of other bidders to become a winner or to decrease his payment.

In our proposed scheme, we use a new protocol that can achieve the same outcome as the GVA. In this protocol, the procedure executed by a bidder affects neither the prices nor the allocation of the bidder. Therefore, a bidder does not have an incentive to be an active adversary.

We describe the design and implementation of secure and robust protocol and system for a national electronic lottery. Electronic lotteries at a national level are a viable cost effective alternative to mechanical ones when there is a business need to support many types of ”games of chance” and to allow increased drawing frequency. Electronic lotteries are, in fact, extremely high risk financial application: If one discovers a way to predict or otherwise claim the winning numbers (even once) the result is huge financial damages. Moreover, the e-lottery process is complex, which increases the possibility of fraud or costly accidental failures. In addition, a national lottery must adhere to auditability and (regulatory) fairness requirements regarding its drawings. Our mechanism, which we believe is the first one of its kind to be described in the literature, builds upon a number of cryptographic primitives that ensure the unpredictability of the winning numbers, the prevention of their premature leakages and prevention of fraud. We also provide measures for auditability, fairness, and trustworthiness of the process. Besides cryptography, we incorporate security mechanisms that eliminate various risks along the entire process. Our system which was commissioned by a national organization, was implemented in the field and has been operational and active for a while, now.

Chameleon signatures are non-interactive signatures based on a hash-and-sign paradigm, and similar in efficiency to regular signatures. The distinguishing characteristic of chameleon signatures is that their are non-transferable, with only the designated recipient capable of asserting its validity. In this paper, we introduce the first identity-based chameleon hash function. The general advantages of identity-based cryptography over conventional schemes relative to key distribution are even more pronounced in a chameleon hashing scheme, because the owner of a public key does not necessarily need to retrieve the associated secret key. We use the identity-based chameleon hashing scheme to build the id-based chameleon signature and a novel sealed-bid auction scheme that is robust, communication efficient (bidders send a single message), and secure under a particular trust model.

In many markets, it can be beneficial for competing firms to coordinate their actions. The average payoffs for everyone in the group can be improved by everyone agreeing on a deal to collude. However, such arrangements usually have the problem that nobody has an incentive to adhere to the agreement. In this paper we investigate a way for two companies to communicate together and agree on a coordinated strategy in such a way that both participants have an incentive to keep to the agreement.

We provide a more efficient solution to the game theoretic problem solved by Dodis, Halevi and Rabin in [DHR00]: two selfish rational parties want to select one of a list of pairs, according to some probability distribution, so that one party learns the first element and the other learns the second, and neither gains any other information. In game theory terms, the problem is to achieve a correlated equilibrium without the trusted mediator. Our solution is more efficient than [DHR00] in terms of the probability distribution.

In an anonymous credential system a user can prove anonymously the possession of credentials to a service provider. Multi-show and non-transferability are two important properties of such systems. More precisely, in a multi-show system the same credential can be used more than once without threatening anonymity, moreover, lending of non-transferable credentials is inconvenient. In this paper we give a construction for multi-show non-transferable credentials for which the owner can prove that the credentials satisfy access control policies expressed by means of linear boolean formulae.

In wireless ad-hoc broadcast networks the pairing problem consists of establishing a (long-term) connection between two specific physical nodes in the network that do not yet know each other. We focus on the ephemeral version of this problem. Ephemeral pairings occur, for example, when electronic business cards are exchanged between two people that meet, or when one pays at a check-out using a wireless wallet.

Apart from introducing this new problem, we present several ephemeral key exchange protocols, both for the case of authentic channels as well as for the case of private channels.

Mixminion is an open source, deployed system under active development. It resists known forms of traffic analysis, allowing parties to communicate without revealing their identities.

MorphMix is a peer-to-peer circuit-based mix network to provide practical anonymous low-latency Internet access for millions of users. The basic ideas of MorphMix have been published before; this paper focuses on solving open problems and giving an analysis of the resistance to attacks and the performance it offers assuming realistic scenarios with very many users. We demonstrate that MorphMix scales very well and can support as many nodes as there are public IP addresses. In addition, we show that MorphMix is indeed practical because it provides good resistance from long-term profiling and offers acceptable performance despite the heterogeneity of the nodes and the fact that nodes can join or leave the system at any time.

A mix is a communication proxy that attempts to hide the correspondence between its incoming and outgoing messages. Timing attacks are a significant challenge for mix-based systems that wish to support interactive, low-latency applications. However, the potency of these attacks has not been studied carefully. In this paper, we investigate timing analysis attacks on low-latency mix systems and clarify the threat they pose. We propose a novel technique, defensive dropping, to thwart timing attacks. Through simulations and analysis, we show that defensive dropping can be effective against attackers who employ timing analysis.

Our proof technique is markedly different than previous work. We establish a connection with information theory – a connection we believe is useful also elsewhere, and which we believe supplies the correct language to attack the problem. We introduce ”obscurant networks” – networks that can obscure the destination of each particular player, and we show almost all executions of the protocol include such a network.