A cloud based service use may be logged into the service through multiple client devices simultaneously. Methods, systems, and computer program products base upon cryptographic challenge response are provide to efficiently and securely simultaneously effect a logout from the cloud based service at one or many logged-in client devices associated with the user. When a valid logout request is received by the cloud based service, a current key associated with the user is invalidated, and in some instances, replaced with a new key. Upon subsequent attempt to use the cloud based service by the user, one or more tokens residing on any previously logged-in client device associated the user will not allow cloud based service usage until the user validly logs into the cloud-based service and receives one or more new tokens based upon the new key at each client device.