Wi-Fi connectivity using open hotspots hosted on untrusted Access Points (APs) has been a staple of mobile network deployments for many years as mobile providers seek to offload smartphone traffic to Wi-Fi. Currently, the available hotspot solutions allow for mobility patterns and client identities to be monitored by the parties hosting the APs as well as by the underlying service provider. We propose a protocol and system that allows a service provider to authenticate its clients, and hides the client identity from both AP and service provider at the time of authentication. Particularly, the client is guaranteed that either the provider cannot do better than to guess their identity randomly or they obtain proof that the provider is trying to reveal their identity by using different keys. Our protocol is based on Private Information Retrieval (PIR) with an augmented cheating detection mechanism based on our extensions to the NTRU encryption scheme. The somewhat-homomorphic encryption makes auditing of multiple rows in a single query possible, and optimizes PIR for highly parallel GPU computations with the use of the Fast Fourier Transform (FFT).

Spread spectrum (SS) communication relies on the assumption that some secret is shared beforehand among communicating nodes to establish the spreading sequence for long-term wireless communication. Strasser et al. identified this as the circular dependency problem (CDP). This problem is exacerbated in large networks, where nodes join and leave the network frequently, and preconfiguration of secrets through physical contact is infeasible. In this work, we introduce an efficient and adversary-resilient secret sharing mechanism based on two novel paradigms (intractable forward decoding, efficient backward decoding) called Time Reversed Message Extraction and Key Scheduling (TREKS) that enables SS communication without preshared secrets. TREKS is four orders of magnitude faster than previous solutions to the CDP. Furthermore, our approach can be used to operate long-term SS communication without establishing any keys. The energy cost under TREKS is provably optimal with minimal storage overhead, and computation cost at most twice that of traditional SS. We evaluate TREKS through simulation and empirically using an experimental testbed consisting of USRP, GNU Radio, and GPU-equipped nodes. Using TREKS under a modest hardware setup, we can sustain a 1--Mbps long-term SS communication spread by a factor of 100 (i.e., 100 Megachips per second) over a 200-MHz bandwidth in real time.

As mobile devices evolve, end users have ever increasing demand for ubiquitous network access. WiFi, being now commonplace, has the potential to fulfill this demand. Apart from WiFi hotspots deployed by ISPs, home users start showing interest in sharing bandwidth with others (e.g. Fon bases its business model on users sharing open access points.) However, all existing WiFi sharing approaches are unsecured due to the difficulty of distributing access keys, discouraging potential users.