Exchanging Pairwise Secrets Efficiently

We consider the problem where a group of wireless nodes, connected to the same broadcast domain, want to create pairwise secrets, in the presence of an adversary Eve, who tries to listen in and steal these secrets. Existing solutions assume that Eve cannot perform certain computations (e.g., large-integer factorization) in useful time. We ask the question: can we solve this problem without assuming anything about Eve's computational capabilities? We propose a simple secret-agreement protocol, where the wireless nodes keep exchanging bits until they have agreed on pairwise secrets that Eve cannot reconstruct with very high probability. Our protocol relies on Eve's limited network presence (the fact that she cannot be located at an arbitrary number of points in the network at the same time), but assumes nothing about her computational capabilities. We formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure (it leaks zero information to Eve about the secrets). Using a small wireless testbed of smartphones, we provide experimental evidence that it is feasible for 5 nodes to create thousands of secret bits per second, with their secrecy being independent from the adversary's capabilities.