A host Virtual Machine Monitor (VMM) operates "blindly," without the host VMM having the ability to access data within a guest virtual machine (VM) or the ability to access directly control structures that control execution flow of the guest VM. Guest VMs execute within a protected region of memory (called a key domain) that even the host VMM cannot access. Virtualization data structures that pertain to the execution state (e.g., a Virtual Machine Control Structure (VMCS)) and memory mappings (e.g., Extended Page Tables (EPTs)) of the guest VM are also located in the protected memory region and are also encrypted with the key domain key. The host VMM and other guest VMs, which do not possess the key domain key for other key domains, cannot directly modify these control structures nor access the protected memory region. The host VMM, however, can verify correctness of the control structures of guest VMs.