Transport Layer Security (TLS) connection establishment between a client and a server for a new session is enabled using an ephemeral (temporary) key pair. In response to a request, the server generates a temporary certificate by signing an ephemeral public key using the server's private key. A certificate chain comprising at least the temporary certificate that includes the ephemeral public key, together with a server certificate, is output to the client by the server, which acts as a subordinate Certificate Authority. The client validates the certificates, generates a session key and outputs the session key wrapped by the ephemeral public key. To complete the connection establishment, the server applies the ephemeral private key to recover the session key derived at the client for the new session. The client and server thereafter use the session key to encrypt and decrypt data over the link. The ephemeral key pair is not reused.