Implementations of the present invention efficiently establish secure connections between a client and server, at least in part by authenticating the client and server early on in the connection setup phases. A client initiating a connection with a server identifies the secure communication protocols enabled at the client, and identifies these protocols in a connection request it sends to the server. The server processes the message and responds with a communication protocol it deems appropriate for the connection. The client and server then exchange appropriate authentication information, and then establish a connection session that implements the chosen communication protocol, and encrypts messages using the negotiated communication protocol. Additional implementations relate to reestablishing dropped connections behind virtual Internet Protocol addresses, without necessarily having to recommit much connection resource overhead.