FIG. 3 illustrates a system 300 for pairing and locating a wireless accessory, according to embodiments described herein. In one embodiment a mobile device 102 of a user of the wireless accessory 201 can present an accessory pairing UI 302 by which the user can pair the mobile device 102 with the wireless accessory 201. During an initial pairing (305) between the mobile device 102 and the wireless accessory, a public key exchange (310) can be performed between the mobile device 102 and the wireless accessory 201. In one embodiment the initial pairing 305 is performed over a secure wireless communication session that includes additional security over and beyond that which is provided by the wireless protocol. In one embodiment, during the public key exchange (310) the mobile device 102 and the wireless accessory 201 exchange public keys of public key pairs generated by the device and the accessory. In one embodiment the public key exchange (310) is a one-way transfer, in which the mobile device 102 transmits a public key of a public/private key pair to the wireless accessory 201. Alternatively, or additionally, the public key exchange (310) may be a Diffie-Hellman key exchange in which the device and the accessory establish a shared secret between two parties. In one embodiment, the public key exchange (310) additionally uses elliptic curve cryptography to establish the shared secret. For example, Elliptic-Curve Diffie-Hellman (ECDH) can be used to enable the establishment of a public key pair and one or more shared secrets. In one embodiment, the one or more shared secrets include an anti-tracking secret, which can be used by the wireless accessory 201 to periodically derive additional public keys. In one embodiment, the public key exchange (310) is performed as part of a collaborative key generation process in which that is performed by the mobile device 102 and the wireless accessory 201. In one embodiment, identity-based encryption is used at least in part. With identity-based encryption, the public key is, or is derived from, some unique element of information about the identity of the user, such as an e-mail address. The entity that is to decrypt the encrypted information can obtain the decryption key from a trusted central authority.