Some embodiments provide non-transitory machine-readable medium that stores a program which when executed by at least one processing unit of a device synchronizes a set of keychains stored on the device with a set of other devices. The device and the set of other devices are communicatively coupled to one another through a peer-to-peer (P2P) network. The program receives a modification to a keychain in the set of keychains stored on the device. The program generates an update request for each device in the set of other devices in order to synchronize the set of keychains stored on device with the set of other devices. The program transmits through the P2P network the set of update requests to the set of other devices over a set of separate, secure communication channels.