System and techniques for multi-tenant cryptographic memory isolation are described herein. A multiple key total memory encryption (MKTME) circuitry may receive a read request for encrypted memory. Here, the read request may include an encrypted memory address that itself includes a sequence of keyid bits and physical address bits. The MKTME circuitry may retrieve a keyid-nonce from a key table using the keyid bits. The MKTME circuitry may construct a tweak from the keyid-nonce, the keyid bits, and the physical address bits. The MKTME circuitry may then decrypt data specified by the read request using the tweak and a common key.