In one embodiment, an apparatus includes a page miss handler to receive a full address including a linear address portion having a linear address and a key identifier portion having a key identifier for a key. The page miss handler may insert an entry including this key identifier in a translation storage. The apparatus further may include a remapping table having a plurality of entries each to store information regarding a key identifier. Other embodiments are described and claimed.