diff --git a/keystore2/src/keystore2_main.rs b/keystore2/src/keystore2_main.rs
index 45338c4..dab6867 100644
--- a/keystore2/src/keystore2_main.rs
+++ b/keystore2/src/keystore2_main.rs
@@ -96,7 +96,11 @@
             panic!("Failed to register service {} because of {:?}.", AUTHORIZATION_SERVICE_NAME, e);
         });
 
-    let maintenance_service = Maintenance::new_native_binder().unwrap_or_else(|e| {
+    let (delete_listener, legacykeystore) = LegacyKeystore::new_native_binder(
+        &keystore2::globals::DB_PATH.read().expect("Could not get DB_PATH."),
+    );
+
+    let maintenance_service = Maintenance::new_native_binder(delete_listener).unwrap_or_else(|e| {
         panic!("Failed to create service {} because of {:?}.", USER_MANAGER_SERVICE_NAME, e);
     });
     binder::add_service(USER_MANAGER_SERVICE_NAME, maintenance_service.as_binder()).unwrap_or_else(
@@ -120,9 +124,6 @@
         });
     }
 
-    let legacykeystore = LegacyKeystore::new_native_binder(
-        &keystore2::globals::DB_PATH.read().expect("Could not get DB_PATH."),
-    );
     binder::add_service(LEGACY_KEYSTORE_SERVICE_NAME, legacykeystore.as_binder()).unwrap_or_else(
         |e| {
             panic!(
diff --git a/keystore2/src/legacy_blob.rs b/keystore2/src/legacy_blob.rs
index e0d2133..6b16d2e 100644
--- a/keystore2/src/legacy_blob.rs
+++ b/keystore2/src/legacy_blob.rs
@@ -678,7 +678,7 @@
     }
 
     /// List all entries belonging to the given uid.
-    pub fn list_legacy_keystore_entries(&self, uid: u32) -> Result<Vec<String>> {
+    pub fn list_legacy_keystore_entries_for_uid(&self, uid: u32) -> Result<Vec<String>> {
         let mut path = self.path.clone();
         let user_id = uid_to_android_user(uid);
         path.push(format!("user_{}", user_id));
@@ -690,7 +690,7 @@
                 _ => {
                     return Err(e).context(format!(
                         concat!(
-                            "In list_legacy_keystore_entries: ,",
+                            "In list_legacy_keystore_entries_for_uid: ,",
                             "Failed to open legacy blob database: {:?}"
                         ),
                         path
@@ -701,21 +701,54 @@
         let mut result: Vec<String> = Vec::new();
         for entry in dir {
             let file_name = entry
-                .context("In list_legacy_keystore_entries: Trying to access dir entry")?
+                .context("In list_legacy_keystore_entries_for_uid: Trying to access dir entry")?
                 .file_name();
             if let Some(f) = file_name.to_str() {
                 let encoded_alias = &f[uid_str.len() + 1..];
                 if f.starts_with(&uid_str) && !Self::is_keystore_alias(encoded_alias) {
-                    result.push(
-                        Self::decode_alias(encoded_alias)
-                            .context("In list_legacy_keystore_entries: Trying to decode alias.")?,
-                    )
+                    result.push(Self::decode_alias(encoded_alias).context(
+                        "In list_legacy_keystore_entries_for_uid: Trying to decode alias.",
+                    )?)
                 }
             }
         }
         Ok(result)
     }
 
+    fn extract_legacy_alias(encoded_alias: &str) -> Option<String> {
+        if !Self::is_keystore_alias(encoded_alias) {
+            Self::decode_alias(encoded_alias).ok()
+        } else {
+            None
+        }
+    }
+
+    /// Lists all keystore entries belonging to the given user. Returns a map of UIDs
+    /// to sets of decoded aliases. Only returns entries that do not begin with
+    /// KNOWN_KEYSTORE_PREFIXES.
+    pub fn list_legacy_keystore_entries_for_user(
+        &self,
+        user_id: u32,
+    ) -> Result<HashMap<u32, HashSet<String>>> {
+        let user_entries = self
+            .list_user(user_id)
+            .context("In list_legacy_keystore_entries_for_user: Trying to list user.")?;
+
+        let result =
+            user_entries.into_iter().fold(HashMap::<u32, HashSet<String>>::new(), |mut acc, v| {
+                if let Some(sep_pos) = v.find('_') {
+                    if let Ok(uid) = v[0..sep_pos].parse::<u32>() {
+                        if let Some(alias) = Self::extract_legacy_alias(&v[sep_pos + 1..]) {
+                            let entry = acc.entry(uid).or_default();
+                            entry.insert(alias);
+                        }
+                    }
+                }
+                acc
+            });
+        Ok(result)
+    }
+
     /// This function constructs the legacy blob file name which has the form:
     /// user_<android user id>/<uid>_<alias>. Legacy blob file names must not use
     /// known keystore prefixes.
@@ -798,10 +831,10 @@
             .is_none())
     }
 
-    fn extract_alias(encoded_alias: &str) -> Option<String> {
+    fn extract_keystore_alias(encoded_alias: &str) -> Option<String> {
         // We can check the encoded alias because the prefixes we are interested
         // in are all in the printable range that don't get mangled.
-        for prefix in &["USRPKEY_", "USRSKEY_", "USRCERT_", "CACERT_"] {
+        for prefix in Self::KNOWN_KEYSTORE_PREFIXES {
             if let Some(alias) = encoded_alias.strip_prefix(prefix) {
                 return Self::decode_alias(&alias).ok();
             }
@@ -849,7 +882,7 @@
             user_entries.into_iter().fold(HashMap::<u32, HashSet<String>>::new(), |mut acc, v| {
                 if let Some(sep_pos) = v.find('_') {
                     if let Ok(uid) = v[0..sep_pos].parse::<u32>() {
-                        if let Some(alias) = Self::extract_alias(&v[sep_pos + 1..]) {
+                        if let Some(alias) = Self::extract_keystore_alias(&v[sep_pos + 1..]) {
                             let entry = acc.entry(uid).or_default();
                             entry.insert(alias);
                         }
@@ -877,7 +910,7 @@
                     return None;
                 }
                 let encoded_alias = &v[uid_str.len()..];
-                Self::extract_alias(encoded_alias)
+                Self::extract_keystore_alias(encoded_alias)
             })
             .collect();
 
@@ -1388,7 +1421,7 @@
         let temp_dir = TempDir::new("list_legacy_keystore_entries_on_non_existing_user")?;
         let legacy_blob_loader = LegacyBlobLoader::new(temp_dir.path());
 
-        assert!(legacy_blob_loader.list_legacy_keystore_entries(20)?.is_empty());
+        assert!(legacy_blob_loader.list_legacy_keystore_entries_for_user(20)?.is_empty());
 
         Ok(())
     }
diff --git a/keystore2/src/maintenance.rs b/keystore2/src/maintenance.rs
index 0633bc1..637fb61 100644
--- a/keystore2/src/maintenance.rs
+++ b/keystore2/src/maintenance.rs
@@ -32,22 +32,35 @@
 use android_security_maintenance::binder::{
     BinderFeatures, Interface, Result as BinderResult, Strong, ThreadState,
 };
+use android_system_keystore2::aidl::android::system::keystore2::KeyDescriptor::KeyDescriptor;
 use android_system_keystore2::aidl::android::system::keystore2::ResponseCode::ResponseCode;
-use android_system_keystore2::aidl::android::system::keystore2::{
-    Domain::Domain, KeyDescriptor::KeyDescriptor,
-};
 use anyhow::{Context, Result};
 use keystore2_crypto::Password;
 
+/// Reexport Domain for the benefit of DeleteListener
+pub use android_system_keystore2::aidl::android::system::keystore2::Domain::Domain;
+
+/// The Maintenance module takes a delete listener argument which observes user and namespace
+/// deletion events.
+pub trait DeleteListener {
+    /// Called by the maintenance module when an app/namespace is deleted.
+    fn delete_namespace(&self, domain: Domain, namespace: i64) -> Result<()>;
+    /// Called by the maintenance module when a user is deleted.
+    fn delete_user(&self, user_id: u32) -> Result<()>;
+}
+
 /// This struct is defined to implement the aforementioned AIDL interface.
-/// As of now, it is an empty struct.
-pub struct Maintenance;
+pub struct Maintenance {
+    delete_listener: Box<dyn DeleteListener + Send + Sync + 'static>,
+}
 
 impl Maintenance {
-    /// Create a new instance of Keystore User Manager service.
-    pub fn new_native_binder() -> Result<Strong<dyn IKeystoreMaintenance>> {
+    /// Create a new instance of Keystore Maintenance service.
+    pub fn new_native_binder(
+        delete_listener: Box<dyn DeleteListener + Send + Sync + 'static>,
+    ) -> Result<Strong<dyn IKeystoreMaintenance>> {
         Ok(BnKeystoreMaintenance::new_binder(
-            Self,
+            Self { delete_listener },
             BinderFeatures { set_requesting_sid: true, ..BinderFeatures::default() },
         ))
     }
@@ -89,7 +102,7 @@
         }
     }
 
-    fn add_or_remove_user(user_id: i32) -> Result<()> {
+    fn add_or_remove_user(&self, user_id: i32) -> Result<()> {
         // Check permission. Function should return if this failed. Therefore having '?' at the end
         // is very important.
         check_keystore_permission(KeystorePerm::change_user()).context("In add_or_remove_user.")?;
@@ -102,10 +115,13 @@
                 false,
             )
         })
-        .context("In add_or_remove_user: Trying to delete keys from db.")
+        .context("In add_or_remove_user: Trying to delete keys from db.")?;
+        self.delete_listener
+            .delete_user(user_id as u32)
+            .context("In add_or_remove_user: While invoking the delete listener.")
     }
 
-    fn clear_namespace(domain: Domain, nspace: i64) -> Result<()> {
+    fn clear_namespace(&self, domain: Domain, nspace: i64) -> Result<()> {
         // Permission check. Must return on error. Do not touch the '?'.
         check_keystore_permission(KeystorePerm::clear_uid()).context("In clear_namespace.")?;
 
@@ -113,7 +129,10 @@
             .bulk_delete_uid(domain, nspace)
             .context("In clear_namespace: Trying to delete legacy keys.")?;
         DB.with(|db| db.borrow_mut().unbind_keys_for_namespace(domain, nspace))
-            .context("In clear_namespace: Trying to delete keys from db.")
+            .context("In clear_namespace: Trying to delete keys from db.")?;
+        self.delete_listener
+            .delete_namespace(domain, nspace)
+            .context("In clear_namespace: While invoking the delete listener.")
     }
 
     fn get_state(user_id: i32) -> Result<AidlUserState> {
@@ -231,17 +250,17 @@
 
     fn onUserAdded(&self, user_id: i32) -> BinderResult<()> {
         let _wp = wd::watch_millis("IKeystoreMaintenance::onUserAdded", 500);
-        map_or_log_err(Self::add_or_remove_user(user_id), Ok)
+        map_or_log_err(self.add_or_remove_user(user_id), Ok)
     }
 
     fn onUserRemoved(&self, user_id: i32) -> BinderResult<()> {
         let _wp = wd::watch_millis("IKeystoreMaintenance::onUserRemoved", 500);
-        map_or_log_err(Self::add_or_remove_user(user_id), Ok)
+        map_or_log_err(self.add_or_remove_user(user_id), Ok)
     }
 
     fn clearNamespace(&self, domain: Domain, nspace: i64) -> BinderResult<()> {
         let _wp = wd::watch_millis("IKeystoreMaintenance::clearNamespace", 500);
-        map_or_log_err(Self::clear_namespace(domain, nspace), Ok)
+        map_or_log_err(self.clear_namespace(domain, nspace), Ok)
     }
 
     fn getState(&self, user_id: i32) -> BinderResult<AidlUserState> {