Using Merkle´s Puzzle for key agreement with low-end devices

Due to severe resource restrictions, many established cryptographic schemes are not executable in sensor and actuator networks. Especially for key exchange algorithms (KE), the foundation of many cryptographic protocols, the situation is extremely challenging as most KE rely on elaborate computations and/or huge data. Hence, there is a continuous search for KE with reduced complexity. Observe that most KE burden the same workload on both communication partners. In this paper, we follow a different approach that respects the usually asymmetric capabilities of network nodes and users. We describe a key agreement protocol that allows for pushing the workload almost completely to the stronger device, e.g., the user. This allows to get any desired security level, independent of the capabilities of the weak device.