Erased Secrets: Practical Information-Theoretic Group Secrecy

We consider the scenario where a group of wireless nodes want to exchange a secret key, such that no eavesdropper can guess the key. Today, this can be achieved using publickey cryptography, e.g., the Diffie-Hellman or the RSA keyexchange algorithms. However, such algorithms require expensive computation, which may be impractical or even beyond the capabilities of wireless nodes. We propose an alternative solution, which enables a group of wireless nodes to exchange a secret key without the use of public-key cryptography. We leverage the nature of wireless networks— namely, that any two nodes are unlikely to correctly receive or overhear the exact same bits fromeach transmission. Based on this, we develop a protocol that enables the group of nodes to agree on secret bits at a rate depending on the properties of the wireless network that interconnects them. Our protocol uses simple, polynomial-time operations and does not require any changes to the physical orMAC-layer of network devices. We formally prove and experimentally demonstrate that our protocol can generate information-theoretically secret keys in a realistic setting.