Authenticating privately over public Wi-Fi hotspots

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). In this work we lay out the operation of our protocol in detail, its security analysis, and propose an implementation compatible with the Wi-Fi Extensible Authentication Protocol (EAP) along with optimizations for deployments of over 10 million clients. We evaluate the performance of its mobile and provider components, and show that a client can be authenticated in 43.9 milliseconds on a GPU platform, giving an end-to-end authentication of 1.12 seconds.