We present a new scheme that allows two nodes of a Mobile Ad-hoc network to compute a shared key without communicating. Such service is important to secure routing protocols. The scheme is based on the novel combination of two well-known techniques: key pre-distribution and threshold secret sharing. Each node only needs to store a small number of keys, independent of the network size. The proposed scheme is secure against collusion of up to a certain number of nodes. Furthermore, it is robust and DoS-resistant since a node that joins a network can efficiently verify each share it obtains from so-called authorization nodes and trace invalid shares. We evaluate and compare via analysis and experiments the performance of the different stages of our scheme (node join, key derivation, verification and traceability) with the performance of the Threshold-DSA based scheme proposed in \cite{nty03,sty03}. Results clearly indicate that the new scheme is much more practical.
