Systems and methods are directed to discovering trusted remote devices and establishing trusted communications with trusted remote devices. A local device can determine one or more time periods of expected silence in a communication between the local device and a remote device; and embed trusted communication messages in the one or more time periods for at least one of: discovering that the remote device is a trusted remote device, performing a trusted communication with the trusted remote device. The communication may be based on a Bluetooth protocol in a link layer.