A source device and a target device may endeavor to form a secure communication session whereby encrypted messages may be transmitted over an untrusted network, such as the internet. However, the exchange of many messages in the establishment of the communication session may involve considerable latency and computational resources, particularly in scenarios featuring many communication sessions (e.g., peer-to-peer communication sessions.) Techniques for initiating a communication session may be devised that enables the initiation of a communication session with only two exchanged messages, or even with a single message transmitted from the source device to the target device. Some embodiments of these techniques may also permit the inclusion of advantageous security features, such as authentication via public certificate to detect man-in-the-middle attacks and the inclusion of nonces to detect replay attacks, without increasing the number of messages involved in the initiation of the communication session.