They might have to deploy their private key on the devices they maintain for their clients, perhaps relying on a secure keystore on-device to try to protect it from client sniffing (presuming quietly selling it to the client isn't part-and-parcel of the deal).

Others have suggested they could provide a cloud-type service to achieve the same result.