The IEEE 802.11 Wireless Local Area Network (WLAN) specifications have been the subject of increased attention due to their rapid commercial adaptation and the introduction of new security and privacy concerns. The IEEE 802.1x standard was introduced in order to overcome the initial security shortcomings of the Wired Equivalent Privacy (WEP) protocol. The IEEE 802.1x standard is an extensible standard that couples 802.11 networks with various authentication services through the incorporation of an Extensible Authentication Protocol (EAP) authentication dialog. The existing implementations of EAP dialogs are based on standard cryptographic solutions for authentication and session key generation but do not, however, provide any form of user anonymity or privacy. Anonymity and privacy are currently of pressing interest, especially in the context of WLANs, which are simultaneously the best medium to provide privacy (there is no physical phone number or connection end-point with a predetermined owner) as well as the most threatening medium to user privacy, as they have the potential of disclosing not only the identity of the user, but also their physical location. At the same time, the potential "perfect hiding" capabilities of WLAN users also highlights the need to control anonymity by introducing more flexible authentication mechanisms. Moreover, payment for wireless services is completely decoupled from the above procedures, raising additional efficiency and privacy concerns. In this work we propose a new EAP authentication dialog based on anonymous electronic cash that provides for privacy, anonymity control, payment acceptance and billing, and authentication. Our solution is based on the notion of "public-key embedding e-cash," an e-cash variant we present and formalize in this paper. We present a concrete description of the new EAP authentication dialog in the context of IEEE 802.1x. We also present an effi- cient implementation of a public-key embedding e-cash scheme based on RSA blind signatures and prove its security.

We introduce the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using k disjoint subsets of the coins. The goal is to minimize the number of coins for any given N and k, while allowing the actual payments to be made on-line, namely without the need to know all payment requests in advance. The problem is motivated by the electronic cash model, where each coin is a long bit sequence, and typical electronic wallets have only limited storage capacity. The k-payment problem has additional applications in other resource-sharing scenarios. Our results include a complete characterization of the k-payment problem as follows. First, we prove a necessary and sufficient condition for a given set of coins to solve the problem. Using this characterization, we prove that the number of coins in any solution to the k-payment problem is at least k H N/k , where H n denotes the nth element in the harmonic series. This condition can also be used to efficiently determine k (the maximal number of exact payments) which a given set of coins allows in the worst case. Secondly, we give an algorithm which produces, for any N and k, a solution with a minimal number of coins. In the case that all denominations are available, the algorithm finds a coin allocation with at most (k+1)H N /(k+1) coins. (Both upper and lower bounds are the best possible.) Finally, we show how to generalize the algorithm to the case where some of the denominations are not available.

Any system which contains some form of cryptographic authentication, confidentiality and/or identification requires the provisioning of a secure key generation and distribution capability. The key distribution mechanism for wireless cellular systems, such as IS-95 CDMA, IS-136 TDMA and IS-91 Analog, has recently been investigated by the Telephone Industry Association's standards working groups. There are several requirements that a cellular key provisioning system must satisfy; however, the current approaches for such generation and distribution are in general inadequate. As with any commercial application, the system must satisfy cost (e.g., efficiency by all parties, minimal specialized equipment, etc.), convenience and most of all security requirements. The cellular system requirements, however, are much more constraining than most environments since the customers' cellular phones have minimal computational capabilities and the authenticated setup protocol is generally performed with the user and carrier never meeting face to face. Moreover, the cellular phone companies are also insisting, for business competition needs, that the key distribution and generation mechanism is as convenient and transparent to the user (customer) as possible. We propose a cryptographically secure approach for such generation and distribution which will satisfy the phone industries' needs as well as the needs of other applications using slow devices.