diff --git a/keystore/grant_store.cpp b/keystore/grant_store.cpp
index 2fb09c1..9244b7c 100644
--- a/keystore/grant_store.cpp
+++ b/keystore/grant_store.cpp
@@ -75,10 +75,11 @@
     return &(*grant);
 }
 
-bool GrantStore::removeByFileAlias(const uid_t uid, const std::string& alias) {
-    auto& uid_grant_list = grants_[uid];
+bool GrantStore::removeByFileAlias(const uid_t granteeUid, const uid_t granterUid,
+        const std::string& alias) {
+    auto& uid_grant_list = grants_[granteeUid];
     for (auto i = uid_grant_list.begin(); i != uid_grant_list.end(); ++i) {
-        if (i->alias_ == alias) {
+        if (i->alias_ == alias && i->owner_uid_ == granterUid) {
             uid_grant_list.erase(i);
             return true;
         }
@@ -86,4 +87,19 @@
     return false;
 }
 
+void GrantStore::removeAllGrantsToKey(const uid_t granterUid, const std::string& alias) {
+    for (auto& uid_grant_list : grants_) {
+        for (auto i = uid_grant_list.second.begin(); i != uid_grant_list.second.end(); ++i) {
+            if (i->alias_ == alias && i->owner_uid_ == granterUid) {
+                uid_grant_list.second.erase(i);
+                break;
+            }
+        }
+    }
+}
+
+void GrantStore::removeAllGrantsToUid(const uid_t granteeUid) {
+    grants_.erase(granteeUid);
+}
+
 }  // namespace keystore
diff --git a/keystore/grant_store.h b/keystore/grant_store.h
index ab03630..6341c76 100644
--- a/keystore/grant_store.h
+++ b/keystore/grant_store.h
@@ -34,10 +34,12 @@
 public:
     Grant(const std::string& alias, const std::string& owner_dir_name, const uid_t owner_uid,
           const uint64_t grant_no);
-    std::string alias_;
-    std::string owner_dir_name_;
-    uid_t owner_uid_;
-    uint64_t grant_no_;
+    // the following three field are used to recover the key filename that the grant refers to
+    std::string alias_;            ///< original/wrapped key alias
+    std::string owner_dir_name_;   ///< key owner key directory
+    uid_t owner_uid_;              ///< key owner uid
+
+    uint64_t grant_no_;            ///< numeric grant identifier - randomly assigned
 
     operator const uint64_t&() const { return grant_no_; }
 };
@@ -57,7 +59,9 @@
     std::string put(const uid_t uid, const std::string& alias, const std::string& owner_dir_name,
                     const uid_t owner_uid);
     const Grant* get(const uid_t uid, const std::string& alias) const;
-    bool removeByFileAlias(const uid_t uid, const std::string& alias);
+    bool removeByFileAlias(const uid_t granteeUid, const uid_t granterUid, const std::string& alias);
+    void removeAllGrantsToKey(const uid_t granterUid, const std::string& alias);
+    void removeAllGrantsToUid(const uid_t granteeUid);
 
     // GrantStore is neither copyable nor movable.
     GrantStore(const GrantStore&) = delete;
diff --git a/keystore/key_store_service.cpp b/keystore/key_store_service.cpp
index c8842c5..85de181 100644
--- a/keystore/key_store_service.cpp
+++ b/keystore/key_store_service.cpp
@@ -191,16 +191,21 @@
     }
     String8 name8(name);
     ALOGI("del %s %d", name8.string(), targetUid);
-    String8 filename(mKeyStore->getKeyNameForUidWithDir(name8, targetUid, ::TYPE_ANY));
-    ResponseCode result = mKeyStore->del(filename.string(), ::TYPE_ANY, get_user_id(targetUid));
+    auto filename = mKeyStore->getBlobFileNameIfExists(name8, targetUid, ::TYPE_ANY);
+    if (!filename.isOk()) return ResponseCode::KEY_NOT_FOUND;
+
+    ResponseCode result = mKeyStore->del(filename.value().string(), ::TYPE_ANY,
+            get_user_id(targetUid));
     if (result != ResponseCode::NO_ERROR) {
         return result;
     }
 
-    // Also delete any characteristics files
-    String8 chrFilename(
-        mKeyStore->getKeyNameForUidWithDir(name8, targetUid, ::TYPE_KEY_CHARACTERISTICS));
-    return mKeyStore->del(chrFilename.string(), ::TYPE_KEY_CHARACTERISTICS, get_user_id(targetUid));
+    filename = mKeyStore->getBlobFileNameIfExists(name8, targetUid, ::TYPE_KEY_CHARACTERISTICS);
+    if (filename.isOk()) {
+        return mKeyStore->del(filename.value().string(), ::TYPE_KEY_CHARACTERISTICS,
+                get_user_id(targetUid));
+    }
+    return ResponseCode::NO_ERROR;
 }
 
 KeyStoreServiceReturnCode KeyStoreService::exist(const String16& name, int targetUid) {
@@ -209,13 +214,8 @@
         return ResponseCode::PERMISSION_DENIED;
     }
 
-    String8 name8(name);
-    String8 filename(mKeyStore->getKeyNameForUidWithDir(name8, targetUid, ::TYPE_ANY));
-
-    if (access(filename.string(), R_OK) == -1) {
-        return (errno != ENOENT) ? ResponseCode::SYSTEM_ERROR : ResponseCode::KEY_NOT_FOUND;
-    }
-    return ResponseCode::NO_ERROR;
+    auto filename = mKeyStore->getBlobFileNameIfExists(String8(name), targetUid, ::TYPE_ANY);
+    return filename.isOk() ? ResponseCode::NO_ERROR : ResponseCode::KEY_NOT_FOUND;
 }
 
 KeyStoreServiceReturnCode KeyStoreService::list(const String16& prefix, int targetUid,
@@ -543,7 +543,7 @@
         return (errno != ENOENT) ? ResponseCode::SYSTEM_ERROR : ResponseCode::KEY_NOT_FOUND;
     }
 
-    return mKeyStore->removeGrant(name8, granteeUid) ? ResponseCode::NO_ERROR
+    return mKeyStore->removeGrant(name8, callingUid, granteeUid) ? ResponseCode::NO_ERROR
                                                      : ResponseCode::KEY_NOT_FOUND;
 }
 
@@ -554,17 +554,16 @@
         return -1L;
     }
 
-    String8 name8(name);
-    String8 filename(mKeyStore->getKeyNameForUidWithDir(name8, targetUid, ::TYPE_ANY));
+    auto filename = mKeyStore->getBlobFileNameIfExists(String8(name), targetUid, ::TYPE_ANY);
 
-    if (access(filename.string(), R_OK) == -1) {
-        ALOGW("could not access %s for getmtime", filename.string());
+    if (!filename.isOk()) {
+        ALOGW("could not access %s for getmtime", filename.value().string());
         return -1L;
     }
 
-    int fd = TEMP_FAILURE_RETRY(open(filename.string(), O_NOFOLLOW, O_RDONLY));
+    int fd = TEMP_FAILURE_RETRY(open(filename.value().string(), O_NOFOLLOW, O_RDONLY));
     if (fd < 0) {
-        ALOGW("could not open %s for getmtime", filename.string());
+        ALOGW("could not open %s for getmtime", filename.value().string());
         return -1L;
     }
 
@@ -572,7 +571,7 @@
     int ret = fstat(fd, &s);
     close(fd);
     if (ret == -1) {
-        ALOGW("could not stat %s for getmtime", filename.string());
+        ALOGW("could not stat %s for getmtime", filename.value().string());
         return -1L;
     }
 
@@ -652,6 +651,8 @@
     }
     ALOGI("clear_uid %" PRId64, targetUid64);
 
+    mKeyStore->removeAllGrantsToUid(targetUid);
+
     String8 prefix = String8::format("%u_", targetUid);
     Vector<String16> aliases;
     if (mKeyStore->list(prefix, &aliases, get_user_id(targetUid)) != ResponseCode::NO_ERROR) {
@@ -1893,8 +1894,12 @@
             return;
         }
 
-        String8 filename(mKeyStore->getKeyNameForUidWithDir(name8, uid, ::TYPE_KEYMASTER_10));
-        error = mKeyStore->del(filename.string(), ::TYPE_ANY, get_user_id(uid));
+        auto filename = mKeyStore->getBlobFileNameIfExists(name8, uid, ::TYPE_KEYMASTER_10);
+        if (!filename.isOk()) {
+            ALOGI("trying to upgrade a non existing blob");
+            return;
+        }
+        error = mKeyStore->del(filename.value().string(), ::TYPE_ANY, get_user_id(uid));
         if (!error.isOk()) {
             ALOGI("upgradeKeyBlob keystore->del failed %d", (int)error);
             return;
@@ -1907,7 +1912,7 @@
         newBlob.setSuperEncrypted(blob->isSuperEncrypted());
         newBlob.setCriticalToDeviceEncryption(blob->isCriticalToDeviceEncryption());
 
-        error = mKeyStore->put(filename.string(), &newBlob, get_user_id(uid));
+        error = mKeyStore->put(filename.value().string(), &newBlob, get_user_id(uid));
         if (!error.isOk()) {
             ALOGI("upgradeKeyBlob keystore->put failed %d", (int)error);
             return;
diff --git a/keystore/keystore.cpp b/keystore/keystore.cpp
index 18ecb4a..a61ef73 100644
--- a/keystore/keystore.cpp
+++ b/keystore/keystore.cpp
@@ -156,6 +156,30 @@
     }
 }
 
+NullOr<android::String8> KeyStore::getBlobFileNameIfExists(const android::String8& alias, uid_t uid,
+                                                          const BlobType type) {
+    android::String8 filepath8(getKeyNameForUidWithDir(alias, uid, type));
+
+    if (!access(filepath8.string(), R_OK | W_OK)) return filepath8;
+
+    // If this is one of the legacy UID->UID mappings, use it.
+    uid_t euid = get_keystore_euid(uid);
+    if (euid != uid) {
+        filepath8 = getKeyNameForUidWithDir(alias, euid, type);
+        if (!access(filepath8.string(), R_OK | W_OK)) return filepath8;
+    }
+
+    // They might be using a granted key.
+    auto grant = mGrants.get(uid, alias.string());
+    if (grant) {
+        filepath8 = String8::format("%s/%s", grant->owner_dir_name_.c_str(),
+                getKeyNameForUid(String8(grant->alias_.c_str()), grant->owner_uid_, type).c_str());
+        if (!access(filepath8.string(), R_OK | W_OK)) return filepath8;
+    }
+    return {};
+}
+
+
 void KeyStore::resetUser(uid_t userId, bool keepUnenryptedEntries) {
     android::String8 prefix("");
     android::Vector<android::String16> aliases;
@@ -310,11 +334,23 @@
                               mEntropy);
 }
 
+static NullOr<std::tuple<uid_t, std::string>> filename2UidAlias(const std::string& filename);
+
 ResponseCode KeyStore::del(const char* filename, const BlobType type, uid_t userId) {
     Blob keyBlob;
+    auto uidAlias = filename2UidAlias(filename);
+    uid_t uid;
+    std::string alias;
+    if (uidAlias.isOk()) {
+        std::tie(uid, alias) = std::move(uidAlias).value();
+    }
     ResponseCode rc = get(filename, &keyBlob, type, userId);
     if (rc == ResponseCode::VALUE_CORRUPTED) {
         // The file is corrupt, the best we can do is rm it.
+        if (uidAlias.isOk()) {
+            // remove possible grants
+            mGrants.removeAllGrantsToKey(uid, alias);
+        }
         return (unlink(filename) && errno != ENOENT) ?
                 ResponseCode::SYSTEM_ERROR : ResponseCode::NO_ERROR;
     }
@@ -332,8 +368,16 @@
             return ResponseCode::SYSTEM_ERROR;
     }
 
-    return (unlink(filename) && errno != ENOENT) ?
+    rc = (unlink(filename) && errno != ENOENT) ?
             ResponseCode::SYSTEM_ERROR : ResponseCode::NO_ERROR;
+
+    if (rc == ResponseCode::NO_ERROR && keyBlob.getType() != ::TYPE_KEY_CHARACTERISTICS) {
+        // now that we have successfully deleted a key, let's make sure there are no stale grants
+        if (uidAlias.isOk()) {
+            mGrants.removeAllGrantsToKey(uid, alias);
+        }
+    }
+    return rc;
 }
 
 /*
@@ -373,6 +417,29 @@
     *out = '\0';
 }
 
+static NullOr<std::tuple<uid_t, std::string>> filename2UidAlias(const std::string& filepath) {
+    auto filenamebase = filepath.find_last_of('/');
+    std::string filename = filenamebase == std::string::npos ? filepath :
+            filepath.substr(filenamebase + 1);
+
+    if (filename[0] == '.') return {};
+
+    auto sep = filename.find('_');
+    if (sep == std::string::npos) return {};
+
+    std::stringstream s(filename.substr(0, sep));
+    uid_t uid;
+    s >> uid;
+    if (!s) return {};
+
+    auto alias = filename.substr(sep + 1);
+
+    std::vector<char> alias_buffer(decode_key_length(alias.c_str(), alias.size()) + 1);
+
+    decode_key(alias_buffer.data(), alias.c_str(), alias.size());
+    return std::tuple<uid_t, std::string>(uid, alias_buffer.data());
+}
+
 ResponseCode KeyStore::list(const android::String8& prefix,
                             android::Vector<android::String16>* matches, uid_t userId) {
 
@@ -421,8 +488,11 @@
                        granterUid);
 }
 
-bool KeyStore::removeGrant(const char* alias, uid_t granteeUid) {
-    return mGrants.removeByFileAlias(granteeUid, alias);
+bool KeyStore::removeGrant(const char* alias, const uid_t granterUid, const uid_t granteeUid) {
+    return mGrants.removeByFileAlias(granteeUid, granterUid, alias);
+}
+void KeyStore::removeAllGrantsToUid(const uid_t granteeUid) {
+    mGrants.removeAllGrantsToUid(granteeUid);
 }
 
 ResponseCode KeyStore::importKey(const uint8_t* key, size_t keyLen, const char* filename,
@@ -501,32 +571,13 @@
 
 ResponseCode KeyStore::getKeyForName(Blob* keyBlob, const android::String8& keyName,
                                      const uid_t uid, const BlobType type) {
-    android::String8 filepath8(getKeyNameForUidWithDir(keyName, uid, type));
+    auto filepath8 = getBlobFileNameIfExists(keyName, uid, type);
     uid_t userId = get_user_id(uid);
 
-    ResponseCode responseCode = get(filepath8.string(), keyBlob, type, userId);
-    if (responseCode != ResponseCode::KEY_NOT_FOUND) {
-        return responseCode;
-    }
+    if (filepath8.isOk())
+        return get(filepath8.value().string(), keyBlob, type, userId);
 
-    // If this is one of the legacy UID->UID mappings, use it.
-    uid_t euid = get_keystore_euid(uid);
-    if (euid != uid) {
-        filepath8 = getKeyNameForUidWithDir(keyName, euid, type);
-        responseCode = get(filepath8.string(), keyBlob, type, userId);
-        if (responseCode == ResponseCode::NO_ERROR) {
-            return responseCode;
-        }
-    }
-
-    // They might be using a granted key.
-    auto grant = mGrants.get(uid, keyName.string());
-    if (!grant) return ResponseCode::KEY_NOT_FOUND;
-    filepath8 = String8::format("%s/%s", grant->owner_dir_name_.c_str(),
-            getKeyNameForUid(String8(grant->alias_.c_str()), grant->owner_uid_, type).c_str());
-
-    // It is a granted key. Try to load it.
-    return get(filepath8.string(), keyBlob, type, userId);
+    return ResponseCode::KEY_NOT_FOUND;
 }
 
 UserState* KeyStore::getUserState(uid_t userId) {
diff --git a/keystore/keystore.h b/keystore/keystore.h
index 39761bb..a0b747f 100644
--- a/keystore/keystore.h
+++ b/keystore/keystore.h
@@ -70,6 +70,8 @@
                                       const BlobType type);
     android::String8 getKeyNameForUidWithDir(const android::String8& keyName, uid_t uid,
                                              const BlobType type);
+    NullOr<android::String8> getBlobFileNameIfExists(const android::String8& alias, uid_t uid,
+                                                    const BlobType type);
 
     /*
      * Delete entries owned by userId. If keepUnencryptedEntries is true
@@ -88,7 +90,8 @@
                       uid_t userId);
 
     std::string addGrant(const char* alias, uid_t granterUid, uid_t granteeUid);
-    bool removeGrant(const char* alias, uid_t granteeUid);
+    bool removeGrant(const char* alias, const uid_t granterUid, const uid_t granteeUid);
+    void removeAllGrantsToUid(const uid_t granteeUid);
 
     ResponseCode importKey(const uint8_t* key, size_t keyLen, const char* filename, uid_t userId,
                            int32_t flags);
diff --git a/keystore/permissions.h b/keystore/permissions.h
index 80d0e04..1f7b7a6 100644
--- a/keystore/permissions.h
+++ b/keystore/permissions.h
@@ -61,4 +61,52 @@
 
 int configure_selinux();
 
+/*
+ * Keystore grants.
+ *
+ * What are keystore grants?
+ *
+ * Keystore grants are a mechanism that allows an app to grant the permission to use one of its
+ * keys to an other app.
+ *
+ * Liftime of a grant:
+ *
+ * A keystore grant is ephemeral in that is never persistently stored. When the keystore process
+ * exits, all grants are lost. Also, grants can be explicitly revoked by the granter by invoking
+ * the ungrant operation.
+ *
+ * What happens when a grant is created?
+ *
+ * The grant operation expects a valid key alias and the uid of the grantee, i.e., the app that
+ * shall be allowed to use the key denoted by the alias. It then makes an entry in the grant store
+ * which generates a new alias of the form <alias>_KEYSTOREGRANT_<random_grant_no_>. This grant
+ * alias is returned to the caller which can pass the new alias to the grantee. For every grantee,
+ * the grant store keeps a set of grants, an entry of which holds the following information:
+ *  - the owner of the key by uid, aka granter uid,
+ *  - the original alias of the granted key, and
+ *  - the random grant number.
+ * (See "grant_store.h:class Grant")
+ *
+ * What happens when a grant is used?
+ *
+ * Upon any keystore operation that expects an alias, the alias and the caller's uid are used
+ * to retrieve a key file. If that fails some operations try to retrieve a key file indirectly
+ * through a grant. These operations include:
+ *  - attestKey
+ *  - begin
+ *  - exportKey
+ *  - get
+ *  - getKeyCharacteristics
+ *  - del
+ *  - exist
+ *  - getmtime
+ * Operations that DO NOT follow the grant indirection are:
+ *  - import
+ *  - generate
+ *  - grant
+ *  - ungrant
+ * Especially, the latter two mean that neither can a grantee transitively grant a granted key
+ * to a third, nor can they relinquish access to the key or revoke access to the key by a third.
+ */
+
 #endif  // KEYSTORE_PERMISSIONS_H_