Binding services are crucial building blocks in networks and networked applications. A binding service (e.g., the Domain Name System (DNS)) maps certain information, namely, binding keys (e.g., host names), to other information, i.e., binding values (e.g., IP addresses), and answers queries for such key-value bindings. Clearly, building secure binding services that ensure the integrity and authenticity of bindings are vital to the correct operations of many networks and networked applications. In this paper we present a novel approach for building generic secure binding services that allow arbitrary key-value bindings as (trusted) infrastructure services to support a variety of networks and networked applications. We combine the Identity-Based Encryption (IBE) crypto-mechanisms with distributed hash table (DHT) techniques to develop an innovative architecture for building scalable, robust and secure binding services. Using this architecture, we implement a prototype system called Vault and evaluate its performance both in a local testbed and on the PlanetLab.