Technologies disclosed herein provide cryptographic computing with cryptographically encoded pointers in multi-tenant environments. An example method comprises executing, by a trusted runtime, first instructions to generate a first address key for a private memory region in the memory and generate a first cryptographically encoded pointer to the private memory region in the memory. Generating the first cryptographically encoded pointer includes storing first context information associated with the private memory region in first bits of the first cryptographically encoded pointer and performing a cryptographic algorithm on a slice of a first linear address of the private memory region based, at least in part, on the first address key and a first tweak, the first tweak including the first context information. The method further includes permitting a first tenant in the multi-tenant environment to access the first address key and the first cryptographically encoded pointer to the private memory region.