Techniques described herein leverage a trusted entity within a domain to enable devices to establish trust with one another so they can securely discover each other and connect to one another. In various examples discussed herein, a device is configured to provide trust information to, and/or receive trust information from, the trusted entity. The trust information may include, for example, a public key of an encryption key pair, a certificate signed by the trusted entity proving authenticity, and/or a hash function and a hash seed used to compute a series of results that form a hash chain. The device may use the trust information to discover another device and to connect to the other device securely and automatically (e.g., with no user involvement or limited user involvement). Moreover, the device may use the trust information to dynamically change a MAC address being used to communicate with the other device.