Truly ubiquitous computing with very small, self-powered and wirelessly networked integrated circuits will become possible within a decade. Applications of these devices include biosensors, environmental monitors, and defense, all of which bring a need for security and privacy. Enabling the use of strong cryptographic algorithms on extremely constrained devices requires rethinking, from an energy-first perspective, the design and implementation of basic cryptographic building blocks.