Key agreement and digital certificates allow bootstrapping secure communication links and verifying identities or information. Thus, they are the cornerstone of many basic security functionalities. However, the resource-constrained nature of wireless sensor nodes limits the use of traditional solutions in wireless sensor networks. Public-key cryptography introduces high delays, drains nodes’ batteries, and it can lead to DoS attacks. Centralized architectures based on a trust center suffer of similar problems due to multi-hop topologies, collisions or packet losses. This paper describes a novel security scheme for sensor networks allowing for fast, resource-friendly, and distributed key agreement and verification of information, featuring the fast operation of symmetric-key cryptography and the functionality of public-key certificates. The core idea of our system relies on the cryptographic association of identification information with polynomial shares. This concept allows the base station of a sensor network to sign node identification and configuration information such as routing addresses or access control roles. The information is signed by means of the polynomial shares distributed to nodes creating a lightweight digital certificate for each node. The optimized schemes described and analyzed in this paper allow sensor nodes to operate in a fully stand-alone and distributed way, being able to perform a combined key agreement and lightweight digital certificate verification handshake within a few milliseconds with very low memory requirements, while exhibiting high resiliency.