Embodiments of the invention can establish secure communications using a single non-traceable request message from a first computer and a single non-traceable response message from a second computer. Non-traceability may be provided through the use of blinding factors. The request and response messages can also include signatures that provide for non-repudiation. In addition, the encryption of the request and response message is not based on the static keys pairs, which are used for validation of the signatures. As such, perfect forward secrecy is maintained.