A system and methods are provided for establishing an authenticated and encrypted communication connection between two devices with at most two round-trip communications. During establishment of an initial authenticated, encrypted communication connection (or afterward), a first device (e.g., a server) provides the second device (e.g., a client) with a token (e.g., a challenge) that lives or persists beyond the current connection. After that connection is terminated and the second device initiates a new connection, it uses the token as part of the handshaking process to reduce the necessary round-trip communications to one.