System and method for securely deploying a virtual machine in a data center is disclosed. In one embodiment, public keys are established between the requesting virtual machine and the deployed virtual machine, so that authentication and communication between the machines can occur using the public keys. In another embodiment, a secret private key is established between the requesting virtual machine and the deployed virtual machine using a password authenticated key exchange protocol. Authentication and communication between the machines is then established using the secret private key.