Zero pre-shared secret key establishment in the presence of jammers

We consider the problem of key establishment over a wireless radio channel in the presence of a communication jammer, initially introduced in 13. The communicating nodes are not assumed to pre-share any secret. The established key can later be used by a conventional spread-spectrum communication system. We introduce new communication concepts called intractable forward-decoding and efficient backward-decoding. Decoding under our mechanism requires at most twice the computation cost of the conventional SS decoding and one packet worth of signal storage. We introduce techniques that apply a key schedule to packet spreading and develop a provably optimal key schedule to minimize the bit-despreading cost. We also use efficient FFT-based algorithms for packet detection. We evaluate our techniques and show that they are efficient both in terms of resiliency against jammers and computation. Finally, our technique has additional features such as the inability to detect packet transmission until the last few bits are being transmitted, and transmissions being destination-specific. To the best of our knowledge, this is the first solution that is optimal in terms of communication energy cost with very little storage and computation overhead.