diff --git a/identity/aidl/default/IdentityCredential.cpp b/identity/aidl/default/IdentityCredential.cpp
index aaae1f6..ff4107a 100644
--- a/identity/aidl/default/IdentityCredential.cpp
+++ b/identity/aidl/default/IdentityCredential.cpp
@@ -25,6 +25,7 @@
 #include <string.h>
 
 #include <android-base/logging.h>
+#include <android-base/stringprintf.h>
 
 #include <cppbor.h>
 #include <cppbor_parse.h>
@@ -32,6 +33,7 @@
 namespace aidl::android::hardware::identity {
 
 using ::aidl::android::hardware::keymaster::Timestamp;
+using ::android::base::StringPrintf;
 using ::std::optional;
 
 using namespace ::android::hardware::identity;
@@ -253,6 +255,12 @@
     return true;
 }
 
+ndk::ScopedAStatus IdentityCredential::setRequestedNamespaces(
+        const vector<RequestNamespace>& requestNamespaces) {
+    requestNamespaces_ = requestNamespaces;
+    return ndk::ScopedAStatus::ok();
+}
+
 ndk::ScopedAStatus IdentityCredential::startRetrieval(
         const vector<SecureAccessControlProfile>& accessControlProfiles,
         const HardwareAuthToken& authToken, const vector<uint8_t>& itemsRequest,
@@ -447,7 +455,7 @@
                         "Type mismatch in nameSpaces map"));
             }
             string requestedNamespace = nsKey->value();
-            vector<string> requestedKeys;
+            set<string> requestedKeys;
             for (size_t m = 0; m < nsInnerMap->size(); m++) {
                 const auto& [innerMapKeyItem, innerMapValueItem] = (*nsInnerMap)[m];
                 const cppbor::Tstr* nameItem = innerMapKeyItem->asTstr();
@@ -459,13 +467,13 @@
                             IIdentityCredentialStore::STATUS_INVALID_ITEMS_REQUEST_MESSAGE,
                             "Type mismatch in value in nameSpaces map"));
                 }
-                requestedKeys.push_back(nameItem->value());
+                requestedKeys.insert(nameItem->value());
             }
             requestedNameSpacesAndNames_[requestedNamespace] = requestedKeys;
         }
     }
 
-    // Finally, validate all the access control profiles in the requestData.
+    // Validate all the access control profiles in the requestData.
     bool haveAuthToken = (authToken.mac.size() > 0);
     for (const auto& profile : accessControlProfiles) {
         if (!secureAccessControlProfileCheckMac(profile, storageKey_)) {
@@ -496,10 +504,118 @@
     itemsRequest_ = itemsRequest;
     signingKeyBlob_ = signingKeyBlob;
 
+    // Finally, calculate the size of DeviceNameSpaces. We need to know it ahead of time.
+    expectedDeviceNameSpacesSize_ = calcDeviceNameSpacesSize();
+
     numStartRetrievalCalls_ += 1;
     return ndk::ScopedAStatus::ok();
 }
 
+size_t cborNumBytesForLength(size_t length) {
+    if (length < 24) {
+        return 0;
+    } else if (length <= 0xff) {
+        return 1;
+    } else if (length <= 0xffff) {
+        return 2;
+    } else if (length <= 0xffffffff) {
+        return 4;
+    }
+    return 8;
+}
+
+size_t cborNumBytesForTstr(const string& value) {
+    return 1 + cborNumBytesForLength(value.size()) + value.size();
+}
+
+size_t IdentityCredential::calcDeviceNameSpacesSize() {
+    /*
+     * This is how DeviceNameSpaces is defined:
+     *
+     *        DeviceNameSpaces = {
+     *            * NameSpace => DeviceSignedItems
+     *        }
+     *        DeviceSignedItems = {
+     *            + DataItemName => DataItemValue
+     *        }
+     *
+     *        Namespace = tstr
+     *        DataItemName = tstr
+     *        DataItemValue = any
+     *
+     * This function will calculate its length using knowledge of how CBOR is
+     * encoded.
+     */
+    size_t ret = 0;
+    size_t numNamespacesWithValues = 0;
+    for (const RequestNamespace& rns : requestNamespaces_) {
+        vector<RequestDataItem> itemsToInclude;
+
+        for (const RequestDataItem& rdi : rns.items) {
+            // If we have a CBOR request message, skip if item isn't in it
+            if (itemsRequest_.size() > 0) {
+                const auto& it = requestedNameSpacesAndNames_.find(rns.namespaceName);
+                if (it == requestedNameSpacesAndNames_.end()) {
+                    continue;
+                }
+                const set<string>& dataItemNames = it->second;
+                if (dataItemNames.find(rdi.name) == dataItemNames.end()) {
+                    continue;
+                }
+            }
+
+            // Access is granted if at least one of the profiles grants access.
+            //
+            // If an item is configured without any profiles, access is denied.
+            //
+            bool authorized = false;
+            for (auto id : rdi.accessControlProfileIds) {
+                auto it = profileIdToAccessCheckResult_.find(id);
+                if (it != profileIdToAccessCheckResult_.end()) {
+                    int accessControlForProfile = it->second;
+                    if (accessControlForProfile == IIdentityCredentialStore::STATUS_OK) {
+                        authorized = true;
+                        break;
+                    }
+                }
+            }
+            if (!authorized) {
+                continue;
+            }
+
+            itemsToInclude.push_back(rdi);
+        }
+
+        // If no entries are to be in the namespace, we don't include it...
+        if (itemsToInclude.size() == 0) {
+            continue;
+        }
+
+        // Key: NameSpace
+        ret += cborNumBytesForTstr(rns.namespaceName);
+
+        // Value: Open the DeviceSignedItems map
+        ret += 1 + cborNumBytesForLength(itemsToInclude.size());
+
+        for (const RequestDataItem& item : itemsToInclude) {
+            // Key: DataItemName
+            ret += cborNumBytesForTstr(item.name);
+
+            // Value: DataItemValue - entryData.size is the length of serialized CBOR so we use
+            // that.
+            ret += item.size;
+        }
+
+        numNamespacesWithValues++;
+    }
+
+    // Now that we now the nunber of namespaces with values, we know how many
+    // bytes the DeviceNamespaces map in the beginning is going to take up.
+    ret += 1 + cborNumBytesForLength(numNamespacesWithValues);
+
+    return ret;
+}
+
 ndk::ScopedAStatus IdentityCredential::startRetrieveEntryValue(
         const string& nameSpace, const string& name, int32_t entrySize,
         const vector<int32_t>& accessControlProfileIds) {
@@ -558,8 +674,8 @@
                     IIdentityCredentialStore::STATUS_NOT_IN_REQUEST_MESSAGE,
                     "Name space was not requested in startRetrieval"));
         }
-        const auto& dataItemNames = it->second;
-        if (std::find(dataItemNames.begin(), dataItemNames.end(), name) == dataItemNames.end()) {
+        const set<string>& dataItemNames = it->second;
+        if (dataItemNames.find(name) == dataItemNames.end()) {
             return ndk::ScopedAStatus(AStatus_fromServiceSpecificErrorWithMessage(
                     IIdentityCredentialStore::STATUS_NOT_IN_REQUEST_MESSAGE,
                     "Data item name in name space was not requested in startRetrieval"));
@@ -653,6 +769,17 @@
     }
     vector<uint8_t> encodedDeviceNameSpaces = deviceNameSpacesMap_.encode();
 
+    if (encodedDeviceNameSpaces.size() != expectedDeviceNameSpacesSize_) {
+        LOG(ERROR) << "encodedDeviceNameSpaces is " << encodedDeviceNameSpaces.size() << " bytes, "
+                   << "was expecting " << expectedDeviceNameSpacesSize_;
+        return ndk::ScopedAStatus(AStatus_fromServiceSpecificErrorWithMessage(
+                IIdentityCredentialStore::STATUS_INVALID_DATA,
+                StringPrintf(
+                        "Unexpected CBOR size %zd for encodedDeviceNameSpaces, was expecting %zd",
+                        encodedDeviceNameSpaces.size(), expectedDeviceNameSpacesSize_)
+                        .c_str()));
+    }
+
     // If there's no signing key or no sessionTranscript or no reader ephemeral
     // public key, we return the empty MAC.
     optional<vector<uint8_t>> mac;
diff --git a/identity/aidl/default/IdentityCredential.h b/identity/aidl/default/IdentityCredential.h
index 6072afe..a8bad88 100644
--- a/identity/aidl/default/IdentityCredential.h
+++ b/identity/aidl/default/IdentityCredential.h
@@ -32,15 +32,17 @@
 
 using ::aidl::android::hardware::keymaster::HardwareAuthToken;
 using ::std::map;
+using ::std::set;
 using ::std::string;
 using ::std::vector;
 
-using MapStringToVectorOfStrings = map<string, vector<string>>;
-
 class IdentityCredential : public BnIdentityCredential {
   public:
     IdentityCredential(const vector<uint8_t>& credentialData)
-        : credentialData_(credentialData), numStartRetrievalCalls_(0), authChallenge_(0) {}
+        : credentialData_(credentialData),
+          numStartRetrievalCalls_(0),
+          authChallenge_(0),
+          expectedDeviceNameSpacesSize_(0) {}
 
     // Parses and decrypts credentialData_, return a status code from
     // IIdentityCredentialStore. Must be called right after construction.
@@ -51,6 +53,8 @@
     ndk::ScopedAStatus createEphemeralKeyPair(vector<uint8_t>* outKeyPair) override;
     ndk::ScopedAStatus setReaderEphemeralPublicKey(const vector<uint8_t>& publicKey) override;
     ndk::ScopedAStatus createAuthChallenge(int64_t* outChallenge) override;
+    ndk::ScopedAStatus setRequestedNamespaces(
+            const vector<RequestNamespace>& requestNamespaces) override;
     ndk::ScopedAStatus startRetrieval(
             const vector<SecureAccessControlProfile>& accessControlProfiles,
             const HardwareAuthToken& authToken, const vector<uint8_t>& itemsRequest,
@@ -86,6 +90,9 @@
     // Set by createAuthChallenge()
     uint64_t authChallenge_;
 
+    // Set by setRequestedNamespaces()
+    vector<RequestNamespace> requestNamespaces_;
+
     // Set at startRetrieval() time.
     map<int32_t, int> profileIdToAccessCheckResult_;
     vector<uint8_t> signingKeyBlob_;
@@ -93,16 +100,21 @@
     std::unique_ptr<cppbor::Item> sessionTranscriptItem_;
     vector<uint8_t> itemsRequest_;
     vector<int32_t> requestCountsRemaining_;
-    MapStringToVectorOfStrings requestedNameSpacesAndNames_;
+    map<string, set<string>> requestedNameSpacesAndNames_;
     cppbor::Map deviceNameSpacesMap_;
     cppbor::Map currentNameSpaceDeviceNameSpacesMap_;
 
+    // Calculated at startRetrieval() time.
+    size_t expectedDeviceNameSpacesSize_;
+
     // Set at startRetrieveEntryValue() time.
     string currentNameSpace_;
     string currentName_;
     size_t entryRemainingBytes_;
     vector<uint8_t> entryValue_;
     vector<uint8_t> entryAdditionalData_;
+
+    size_t calcDeviceNameSpacesSize();
 };
 
 }  // namespace aidl::android::hardware::identity
diff --git a/identity/aidl/default/WritableIdentityCredential.cpp b/identity/aidl/default/WritableIdentityCredential.cpp
index b392444..8bc4b49 100644
--- a/identity/aidl/default/WritableIdentityCredential.cpp
+++ b/identity/aidl/default/WritableIdentityCredential.cpp
@@ -22,6 +22,7 @@
 #include <android/hardware/identity/support/IdentityCredentialSupport.h>
 
 #include <android-base/logging.h>
+#include <android-base/stringprintf.h>
 
 #include <cppbor/cppbor.h>
 #include <cppbor/cppbor_parse.h>
@@ -34,6 +35,7 @@
 
 namespace aidl::android::hardware::identity {
 
+using ::android::base::StringPrintf;
 using ::std::optional;
 using namespace ::android::hardware::identity;
 
@@ -105,6 +107,12 @@
     return ndk::ScopedAStatus::ok();
 }
 
+ndk::ScopedAStatus WritableIdentityCredential::setExpectedProofOfProvisioningSize(
+        int32_t expectedProofOfProvisioningSize) {
+    expectedProofOfProvisioningSize_ = expectedProofOfProvisioningSize;
+    return ndk::ScopedAStatus::ok();
+}
+
 ndk::ScopedAStatus WritableIdentityCredential::startPersonalization(
         int32_t accessControlProfileCount, const vector<int32_t>& entryCounts) {
     if (startPersonalizationCalled_) {
@@ -382,6 +390,16 @@
             .add(testCredential_);
     vector<uint8_t> encodedCbor = popArray.encode();
 
+    if (encodedCbor.size() != expectedProofOfProvisioningSize_) {
+        LOG(ERROR) << "CBOR for proofOfProvisioning is " << encodedCbor.size() << " bytes, "
+                   << "was expecting " << expectedProofOfProvisioningSize_;
+        return ndk::ScopedAStatus(AStatus_fromServiceSpecificErrorWithMessage(
+                IIdentityCredentialStore::STATUS_INVALID_DATA,
+                StringPrintf("Unexpected CBOR size %zd for proofOfProvisioning, was expecting %zd",
+                             encodedCbor.size(), expectedProofOfProvisioningSize_)
+                        .c_str()));
+    }
+
     optional<vector<uint8_t>> signature = support::coseSignEcDsa(credentialPrivKey_,
                                                                  encodedCbor,  // payload
                                                                  {},           // additionalData
diff --git a/identity/aidl/default/WritableIdentityCredential.h b/identity/aidl/default/WritableIdentityCredential.h
index 976686a..5645852 100644
--- a/identity/aidl/default/WritableIdentityCredential.h
+++ b/identity/aidl/default/WritableIdentityCredential.h
@@ -43,6 +43,9 @@
                                                  const vector<uint8_t>& attestationChallenge,
                                                  vector<Certificate>* outCertificateChain) override;
 
+    ndk::ScopedAStatus setExpectedProofOfProvisioningSize(
+            int32_t expectedProofOfProvisioningSize) override;
+
     ndk::ScopedAStatus startPersonalization(int32_t accessControlProfileCount,
                                             const vector<int32_t>& entryCounts) override;
 
@@ -62,7 +65,7 @@
             vector<uint8_t>* outCredentialData,
             vector<uint8_t>* outProofOfProvisioningSignature) override;
 
-    // private:
+  private:
     string docType_;
     bool testCredential_;
 
@@ -82,6 +85,7 @@
     cppbor::Array signedDataAccessControlProfiles_;
     cppbor::Map signedDataNamespaces_;
     cppbor::Array signedDataCurrentNamespace_;
+    size_t expectedProofOfProvisioningSize_;
 
     // This field is initialized in addAccessControlProfile
     set<int32_t> accessControlProfileIds_;