  We describe the design and implementation of efficient signature and
key-exchange schemes for the AVR ATmega and ARM Cortex M0 microcontrollers,
targeting the 128-bit security level. Our algorithms are based on an efficient
Montgomery ladder scalar multiplication on the Kummer surface of Gaudry and
Schost's genus-2 hyperelliptic curve, combined with the Jacobian point recovery
technique of Costello, Chung, and Smith. Our results are the first to show the
feasibility of software-only hyperelliptic cryptography on constrained
platforms, and represent a significant improvement on the elliptic-curve
state-of-the-art for both key exchange and signatures on these architectures.
Notably, our key-exchange scalar-multiplication software runs in under 9740k
cycles on the ATmega, and under 2650k cycles on the Cortex M0.
