diff --git a/keystore/Android.mk b/keystore/Android.mk
index cef637a..7dd5aef 100644
--- a/keystore/Android.mk
+++ b/keystore/Android.mk
@@ -43,6 +43,7 @@
 	operation.cpp \
 	permissions.cpp \
 	user_state.cpp \
+	grant_store.cpp \
 	../../../frameworks/base/core/java/android/security/keymaster/IKeyAttestationApplicationIdProvider.aidl
 LOCAL_SHARED_LIBRARIES := \
 	libbinder \
diff --git a/keystore/IKeystoreService.cpp b/keystore/IKeystoreService.cpp
index 344687b..eee9942 100644
--- a/keystore/IKeystoreService.cpp
+++ b/keystore/IKeystoreService.cpp
@@ -442,7 +442,7 @@
         return ResponseCode(reply.readInt32());
     }
 
-    KeyStoreServiceReturnCode grant(const String16& name, int32_t granteeUid) override {
+    String16 grant(const String16& name, int32_t granteeUid) override {
         Parcel data, reply;
         data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
         data.writeString16(name);
@@ -450,14 +450,14 @@
         status_t status = remote()->transact(BnKeystoreService::GRANT, data, &reply);
         if (status != NO_ERROR) {
             ALOGD("grant() could not contact remote: %d\n", status);
-            return ResponseCode::SYSTEM_ERROR;
+            return String16();
         }
         int32_t err = reply.readExceptionCode();
         if (err < 0) {
             ALOGD("grant() caught exception %d\n", err);
-            return ResponseCode::SYSTEM_ERROR;
+            return String16();
         }
-        return ResponseCode(reply.readInt32());
+        return reply.readString16();
     }
 
     KeyStoreServiceReturnCode ungrant(const String16& name, int32_t granteeUid) override {
@@ -1112,9 +1112,9 @@
         CHECK_INTERFACE(IKeystoreService, data, reply);
         String16 name = data.readString16();
         int32_t granteeUid = data.readInt32();
-        int32_t ret = grant(name, granteeUid);
+        String16 ret = grant(name, granteeUid);
         reply->writeNoException();
-        reply->writeInt32(ret);
+        reply->writeString16(ret);
         return NO_ERROR;
     } break;
     case UNGRANT: {
diff --git a/keystore/grant_store.cpp b/keystore/grant_store.cpp
new file mode 100644
index 0000000..9c2e591
--- /dev/null
+++ b/keystore/grant_store.cpp
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "grant_store.h"
+
+#include <algorithm>
+#include <sstream>
+
+namespace keystore {
+
+static constexpr uint64_t kInvalidGrantNo = std::numeric_limits<uint64_t>::max();
+static const char* kKeystoreGrantInfix = "_KEYSTOREGRANT_";
+static constexpr size_t kKeystoreGrantInfixLength = 15;
+
+Grant::Grant(const std::string& alias, const std::string& key_file, const uint64_t grant_no)
+        : alias_(alias), key_file_(key_file), grant_no_(grant_no) {}
+
+static std::pair<uint64_t, std::string> parseGrantAlias(const std::string& grantAlias) {
+    auto pos = grantAlias.rfind(kKeystoreGrantInfix);
+    if (pos == std::string::npos) return {kInvalidGrantNo, ""};
+    std::stringstream s(grantAlias.substr(pos + kKeystoreGrantInfixLength));
+    std::string wrapped_alias = grantAlias.substr(0, pos);
+    uint64_t grant_no = kInvalidGrantNo;
+    s >> grant_no;
+    if (s.fail() || grant_no == kInvalidGrantNo) return {kInvalidGrantNo, ""};
+    return {grant_no, wrapped_alias};
+}
+
+std::string GrantStore::put(const uid_t uid, const std::string& alias, const std::string& key_file) {
+    std::stringstream s;
+    s << alias << kKeystoreGrantInfix;
+    auto& uid_grant_list = grants_[uid];
+
+    bool success = false;
+    auto iterator = std::find_if(uid_grant_list.begin(), uid_grant_list.end(),
+            [&](auto& entry) {
+                return success = entry.alias_ == alias && entry.key_file_ == key_file;
+            });
+    while (!success) {
+        std::tie(iterator, success) = uid_grant_list.emplace(alias, key_file, std::rand());
+    }
+    s << iterator->grant_no_;
+    return s.str();
+}
+
+const Grant* GrantStore::get(const uid_t uid, const std::string& alias) const {
+    uint64_t grant_no;
+    std::string wrappedAlias;
+    std::tie(grant_no, wrappedAlias) = parseGrantAlias(alias);
+    if (grant_no == kInvalidGrantNo) return nullptr;
+    auto uid_set_iter = grants_.find(uid);
+    if (uid_set_iter == grants_.end()) return nullptr;
+    auto& uid_grant_list = uid_set_iter->second;
+    auto grant = uid_grant_list.find(grant_no);
+    if (grant == uid_grant_list.end()) return nullptr;
+    if (grant->alias_ != wrappedAlias) return nullptr;
+    return &(*grant);
+}
+
+bool GrantStore::removeByFileName(const uid_t uid, const std::string& fileName) {
+    auto& uid_grant_list = grants_.operator[](uid);
+    for (auto i = uid_grant_list.begin(); i != uid_grant_list.end(); ++i) {
+        if (i->key_file_ == fileName) {
+            uid_grant_list.erase(i);
+            return true;
+        }
+    }
+    return false;
+}
+
+}  // namespace keystore
diff --git a/keystore/grant_store.h b/keystore/grant_store.h
new file mode 100644
index 0000000..43e814e
--- /dev/null
+++ b/keystore/grant_store.h
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef KEYSTORE_GRANT_STORE_H_
+#define KEYSTORE_GRANT_STORE_H_
+
+#include <set>
+#include <string>
+#include <unordered_map>
+
+namespace keystore {
+
+/**
+ * Grant represents a mapping from an alias to a key file.
+ * Normally, key file names are derived from the alias chosen by the client
+ * and the clients UID, to generate a per client name space.
+ * Grants allow assotiating a key file with a new name, thereby making
+ * it visible in another client's - the grantee's - namespace.
+ */
+class Grant {
+public:
+    Grant(const std::string& alias, const std::string& key_file, const uint64_t grant_no);
+    std::string alias_;
+    std::string key_file_;
+    uint64_t grant_no_;
+
+    operator const uint64_t&() const { return grant_no_; }
+};
+
+/**
+ * The GrantStore holds a set of sets of Grants. One set of Grants for each grantee.
+ * The uid parameter to each of the GrantStore function determines the grantee's
+ * name space. The methods put, get, and removeByAlias/ByFileName create, lookup, and
+ * remove a Grant, respectively.
+ * put also returns a new alias for the newly granted key which has to be returned
+ * to the granter. The grantee, and only the grantee, can use the granted key
+ * by this new alias.
+ */
+class GrantStore {
+public:
+    GrantStore() : grants_() {}
+    std::string put(const uid_t uid, const std::string& alias, const std::string& key_file);
+    const Grant* get(const uid_t uid, const std::string& alias) const;
+    bool removeByFileName(const uid_t uid, const std::string& filename);
+
+    // GrantStore is neither copyable nor movable.
+    GrantStore(const GrantStore&) = delete;
+    GrantStore& operator=(const GrantStore&) = delete;
+private:
+    std::unordered_map<uid_t, std::set<Grant, std::less<>>> grants_;
+};
+
+}  // namespace keystore
+
+#endif  // KEYSTORE_GRANT_STORE_H_
diff --git a/keystore/include/keystore/IKeystoreService.h b/keystore/include/keystore/IKeystoreService.h
index 18bd8eb..a045679 100644
--- a/keystore/include/keystore/IKeystoreService.h
+++ b/keystore/include/keystore/IKeystoreService.h
@@ -166,8 +166,7 @@
     virtual ::keystore::KeyStoreServiceReturnCode
     get_pubkey(const String16& name, ::keystore::hidl_vec<uint8_t>* pubKey) = 0;
 
-    virtual ::keystore::KeyStoreServiceReturnCode grant(const String16& name,
-                                                        int32_t granteeUid) = 0;
+    virtual String16 grant(const String16& name, int32_t granteeUid) = 0;
 
     virtual ::keystore::KeyStoreServiceReturnCode ungrant(const String16& name,
                                                           int32_t granteeUid) = 0;
diff --git a/keystore/key_store_service.cpp b/keystore/key_store_service.cpp
index 5f05e01..24a096c 100644
--- a/keystore/key_store_service.cpp
+++ b/keystore/key_store_service.cpp
@@ -512,22 +512,21 @@
     return ResponseCode::NO_ERROR;
 }
 
-KeyStoreServiceReturnCode KeyStoreService::grant(const String16& name, int32_t granteeUid) {
+String16 KeyStoreService::grant(const String16& name, int32_t granteeUid) {
     uid_t callingUid = IPCThreadState::self()->getCallingUid();
     auto result = checkBinderPermissionAndKeystoreState(P_GRANT);
     if (!result.isOk()) {
-        return result;
+        return String16();
     }
 
     String8 name8(name);
     String8 filename(mKeyStore->getKeyNameForUidWithDir(name8, callingUid, ::TYPE_ANY));
 
     if (access(filename.string(), R_OK) == -1) {
-        return (errno != ENOENT) ? ResponseCode::SYSTEM_ERROR : ResponseCode::KEY_NOT_FOUND;
+        return String16();
     }
 
-    mKeyStore->addGrant(filename.string(), granteeUid);
-    return ResponseCode::NO_ERROR;
+    return String16(mKeyStore->addGrant(filename.string(), String8(name).string(), granteeUid).c_str());
 }
 
 KeyStoreServiceReturnCode KeyStoreService::ungrant(const String16& name, int32_t granteeUid) {
diff --git a/keystore/key_store_service.h b/keystore/key_store_service.h
index 3b4ef85..4060bd1 100644
--- a/keystore/key_store_service.h
+++ b/keystore/key_store_service.h
@@ -84,7 +84,7 @@
     KeyStoreServiceReturnCode get_pubkey(const android::String16& name,
                                          hidl_vec<uint8_t>* pubKey) override;
 
-    KeyStoreServiceReturnCode grant(const android::String16& name, int32_t granteeUid) override;
+    android::String16 grant(const android::String16& name, int32_t granteeUid) override;
     KeyStoreServiceReturnCode ungrant(const android::String16& name, int32_t granteeUid) override;
 
     int64_t getmtime(const android::String16& name, int32_t uid) override;
diff --git a/keystore/keystore.cpp b/keystore/keystore.cpp
index 43bb4be..ab386ad 100644
--- a/keystore/keystore.cpp
+++ b/keystore/keystore.cpp
@@ -48,11 +48,6 @@
 }
 
 KeyStore::~KeyStore() {
-    for (android::Vector<grant_t*>::iterator it(mGrants.begin()); it != mGrants.end(); it++) {
-        delete *it;
-    }
-    mGrants.clear();
-
     for (android::Vector<UserState*>::iterator it(mMasterKeys.begin()); it != mMasterKeys.end();
          it++) {
         delete *it;
@@ -419,26 +414,12 @@
     return ResponseCode::NO_ERROR;
 }
 
-void KeyStore::addGrant(const char* filename, uid_t granteeUid) {
-    const grant_t* existing = getGrant(filename, granteeUid);
-    if (existing == NULL) {
-        grant_t* grant = new grant_t;
-        grant->uid = granteeUid;
-        grant->filename = reinterpret_cast<const uint8_t*>(strdup(filename));
-        mGrants.add(grant);
-    }
+std::string KeyStore::addGrant(const char* filename, const char* alias, uid_t granteeUid) {
+    return mGrants.put(granteeUid, alias, filename);
 }
 
 bool KeyStore::removeGrant(const char* filename, uid_t granteeUid) {
-    for (android::Vector<grant_t*>::iterator it(mGrants.begin()); it != mGrants.end(); it++) {
-        grant_t* grant = *it;
-        if (grant->uid == granteeUid &&
-            !strcmp(reinterpret_cast<const char*>(grant->filename), filename)) {
-            mGrants.erase(it);
-            return true;
-        }
-    }
-    return false;
+    return mGrants.removeByFileName(granteeUid, filename);
 }
 
 ResponseCode KeyStore::importKey(const uint8_t* key, size_t keyLen, const char* filename,
@@ -536,17 +517,9 @@
     }
 
     // They might be using a granted key.
-    android::String8 filename8 = getKeyName(keyName, type);
-    char* end;
-    strtoul(filename8.string(), &end, 10);
-    if (end[0] != '_' || end[1] == 0) {
-        return ResponseCode::KEY_NOT_FOUND;
-    }
-    filepath8 = android::String8::format("%s/%s", getUserState(userId)->getUserDirName(),
-                                         filename8.string());
-    if (!hasGrant(filepath8.string(), uid)) {
-        return responseCode;
-    }
+    auto grant = mGrants.get(uid, keyName.string());
+    if (!grant) return ResponseCode::KEY_NOT_FOUND;
+    filepath8 = grant->key_file_.c_str();
 
     // It is a granted key. Try to load it.
     return get(filepath8.string(), keyBlob, type, userId);
@@ -595,17 +568,6 @@
     return getUserState(userId);
 }
 
-const grant_t* KeyStore::getGrant(const char* filename, uid_t uid) const {
-    for (android::Vector<grant_t*>::const_iterator it(mGrants.begin()); it != mGrants.end(); it++) {
-        grant_t* grant = *it;
-        if (grant->uid == uid &&
-            !strcmp(reinterpret_cast<const char*>(grant->filename), filename)) {
-            return grant;
-        }
-    }
-    return NULL;
-}
-
 bool KeyStore::upgradeBlob(const char* filename, Blob* blob, const uint8_t oldVersion,
                            const BlobType type, uid_t uid) {
     bool updated = false;
diff --git a/keystore/keystore.h b/keystore/keystore.h
index 8ff8899..a08508f 100644
--- a/keystore/keystore.h
+++ b/keystore/keystore.h
@@ -25,11 +25,7 @@
 
 #include "blob.h"
 #include "include/keystore/keymaster_tags.h"
-
-typedef struct {
-    uint32_t uid;
-    const uint8_t* filename;
-} grant_t;
+#include "grant_store.h"
 
 using ::keystore::NullOr;
 
@@ -91,11 +87,8 @@
     ResponseCode list(const android::String8& prefix, android::Vector<android::String16>* matches,
                       uid_t userId);
 
-    void addGrant(const char* filename, uid_t granteeUid);
+    std::string addGrant(const char* filename, const char* alias, uid_t granteeUid);
     bool removeGrant(const char* filename, uid_t granteeUid);
-    bool hasGrant(const char* filename, const uid_t uid) const {
-        return getGrant(filename, uid) != NULL;
-    }
 
     ResponseCode importKey(const uint8_t* key, size_t keyLen, const char* filename, uid_t userId,
                            int32_t flags);
@@ -137,14 +130,12 @@
 
     android::Vector<UserState*> mMasterKeys;
 
-    android::Vector<grant_t*> mGrants;
+    ::keystore::GrantStore mGrants;
 
     typedef struct { uint32_t version; } keystore_metadata_t;
 
     keystore_metadata_t mMetaData;
 
-    const grant_t* getGrant(const char* filename, uid_t uid) const;
-
     /**
      * Upgrade the key from the current version to whatever is newest.
      */