Scalable session management is achieved by generating a cookie that includes an encrypted session key and encrypted cookie data. The cookie data is encrypted using the session key. The session key is then signed and encrypted using one or more public/private key pairs. The encrypted session key can be decrypted and verified using the same private/public key pair(s). Once verified, the decrypted session key can then be used to decrypt and verify the encrypted cookie data. A first server having the private/public key pair(s) may generate the cookie using a randomly generated session key. A second server having the same private/public key pair(s) may decrypt and verify the cookie even if the session key is not initially installed on the second server. A session key cache may be used to provide session key lookup to save public/private key operations on the servers.