A first host device in a first network of a plurality of networks may receive, from an intermediate client device, a request to enroll the intermediate client device into the first network, including receiving a candidate inter-network encryption key. The first host device may determine whether any other intermediate client device is already enrolled in the first network. The first host device may, in response to determining that no other intermediate client device is already enrolled in the first network, set the candidate inter-network encryption key as an inter-network encryption key of the first host device for encrypting communications between the plurality of networks. The first host device may send, to the intermediate client device for forwarding to a second host device in a second network of the plurality of networks, an encrypted message that is encrypted using the inter-network encryption key of first host device.