In one embodiment, an apparatus comprises a processor to read a data line from memory in response to a read request from a VM. The data line comprises encrypted memory data. The apparatus also comprises a memory encryption circuit in the processor. The memory encryption circuit is to use an address of the read request to select an entry from a P2K table; obtain a key identifier from the selected entry of the P2K table; use the key identifier to select a key for the read request; and use the selected key to decrypt the encrypted memory data into decrypted memory data. The processor is further to make the decrypted memory data available to the VM. The P2K table comprises multiple entries, each comprising (a) a key identifier for a page of memory and (b) an encrypted address for that page of memory. Other embodiments are described and claimed.