Dacă cheia cuiva este folosită corect pentru a cripta datele, iar cheia este furat (adică toate mediile fizice care îl conțin sunt furate și astfel devin indisponibile; ca în „ultima mea cheie de blocare a bicicletei a fost furată”), atunci nici măcar nu are opțiunea de a recripta datele: ai pierdut accesul la ele.
Dacă cheia cuiva este direct folosit pentru a cripta datele, iar cheia este compromisă (valoarea ei a devenit cunoscută adversarilor, sau de asta e de temut), atunci
- dacă adversarii au acces la baza de date criptată cu cheia compromisă, atunci confidențialitatea datelor a fost sau va fi pierdută, indiferent de momentul în care are loc accesul (de exemplu, în viitor, dintr-o copie de rezervă veche)
- în caz contrar, decriptarea datelor cu cheia compromisă (dar încă disponibilă), apoi recriptarea datelor cu o cheie nouă, restabilește lucrurile la normal.
Dacă re-criptarea tuturor datelor este incomod, deoarece conține înregistrări mari (de exemplu, imagini sau videoclipuri), este posibil să reduceți costul de calcul prin indirect criptarea datelor cu cheia, folosind două niveluri de cheie. Fiecare înregistrare mare este criptată cu cheia sa individuală de înregistrare aleatorie, ea însăși criptată cu cheia principală și stocată ca o înregistrare auxiliară mică. Pentru a accesa o înregistrare în clar, se citește înregistrarea auxiliară, care este decriptată cu cheia principală care dă cheia de înregistrare, iar înregistrarea în sine este decriptată cu acea cheie de înregistrare. Pentru recriptare după compromiterea cheii principale (doar), trebuie doar să descifrăm și să recriptăm înregistrările auxiliare.
Cu toate acestea, acea criptare indirectă reduce cantitatea de date pe care adversarii trebuie să le obțină pentru a face o bună utilizare a unei chei compromise: acum au nevoie doar de o copie a înregistrărilor cheilor criptate sub vechea cheie pentru a folosi bine accesul ulterior la baza de date. Astfel, în caz de compromitere a cheii principale, ar putea fi recomandabil să decriptați și să recriptați imediat cheile de înregistrare, apoi să decriptați și să recriptați încet fiecare înregistrare individuală sub o nouă cheie de înregistrare aleatorie. În acest scop, înregistrările cheilor criptate trebuie să vină cu identificarea versiunii cheii principale sub care sunt criptate.