202 and history table 204, first block 210 (ID ‘Block 1’) is generated and completed which stores the hash value over ‘Block 0’.

The root hash value of the latest block (e.g., current block 212) in ledger 206 is referred to as a digest (shown as digest 218), which captures a validity state of current table 202, history table 204, and ledger 206. In this way, a single hash value, e.g., in digest 218, enables verification to be performed on data in the database, e.g., in current table 202, history table 204, and ledger 206, that was present at and before generation of digest 218. Digest 218 is stored in secure storage and/or published (e.g., via a website) for use by users of computing devices 102A-102N (as shown in FIG. 1).

As an example, suppose Block N-2 is the current block in ledger 206 and a transaction is received to update current table 202. In this example, history table 204 is updated to store the information stored in current table 202, and current table 202 is updated in accordance with the transaction. A new block in ledger 206 for the transaction is generated (e.g., current block 212). A transaction hash value 216 is then generated over the entry in history table 204 and a changed entry in current table 202 that is generated by the transaction that was performed on the entry. Transaction hash value 216 is inserted into block 212. To generate the root hash value, the updated rows are inserted as leaf nodes of a hierarchical hash data structure, such as a Merkle tree. Each leaf node is then hashed (e.g., SHA-256 hashed) to generate a hash value for the leaf nodes. For each node that is not a leaf, a hash value is generated therefor that is based on the hash values of its child nodes. A root hash value of the hierarchical hash data structure (e.g., a root hash value of the root node of the hierarchical hash data structure) is then determined based on the hash values of its child nodes and utilized as the root hash value (and digest 218) stored in current block 212.

It is noted that any given block comprises any number of transactions. A new block is generated responsive to one or more events, including, but not limited to, expiry of a predetermined time period (e.g., 30 seconds), when a block reaches a maximum number of transactions (e.g., 100,000), etc.

Additionally, with respect to FIG. 2, embodiments provide for a view of a ledger (i.e., a ledger view table 220) that comprises a union of current table 202 and history table 204. Ledger view table 220 is queryable or otherwise operatable via database operations and thus, provides a consolidate view of the current state of the data as well as all transactions previously performed on the current table.

Referring again to FIG. 1, information of identity map 108 is retrievable, e.g., via computing device 102A-102N. Identity map 108 is also modifiable to remove information or include new information.

FIG. 3 depicts a block diagram of a system 300 configured to update an identity map in accordance with an example embodiment. As shown in FIG. 3, system 300 comprises computing devices 102A-102B and DB host 104, a described above with reference to FIG. 1. DB host 104 executes ledger database 106 comprising identity map 108 and comprises ledger 202, an update application programming interface (API) 302 and a database verifier 304. As also shown in FIG. 3, computing device 102A comprises long-term signing key pair 110A, digest 118A, a short-term encryption key pair 306A, and an application 308A, and computing device 102B comprises long-term signing key pair 110B, digest 118B, a short-term encryption key pair 306B, and an application 308B. Each of applications 308A-308B is any software application in which a user desires encryption, for example, for data sharing or communications. Examples of applications 308A-308B include, but are not limited to, Microsoft Teams™ published by Microsoft Corporation of Redmond, WA, Microsoft Sharepoint™ published by Microsoft Corporation and/or the like.

Short-term encryption key pairs 306A-306B each comprise a short-term private encryption key and a short-term public encryption key. Each of short-term signing key pairs 306A-306B are generated by a trusted or customer-controlled service. Each of short-term encryption key pairs 306A-306B comprise randomly-generated numbers (e.g., the service comprises a random number generator that generates the short-term private encryption key and a short-term public encryption key). In accordance with an embodiment, the service executes locally on each of computing devices 102A-102N. In accordance with another embodiment, the service executes remotely from computing devices 102A-102N. In accordance with such an embodiment, short-term encryption key pairs 306A-306B are generated from a key generating web service, where computing devices 102A-102N submit a request to the service for a short-term key pair. Responsive to receiving the request, the service generates (e.g., randomly) the short-term key pair and provides the generated key pair to the requesting computing device via a response. In accordance with an embodiment, the service is a Proof of Possession (PoP)-based service; although it is noted that the embodiments described herein are not so limited.

The short-term private encryption key of pairs 306A-306B are respectively stored locally in a secure environment of a computing device of computing devices 102A-102N. Examples of a secure environment include, but are not limited to, a trusted platform module (TPM), a hardware security module (HSM), or any type of secure hardware and/or software-based cryptoprocessor.

Each of long-term key pairs 110A-110B and short-term key pairs 306A-306B are configured to expire after a predetermined time period, where the predetermined time period for long-term key pairs 110A-110B is relatively longer than the predetermined time period for short-term key pairs 306A-306B. For instance, each of long-term key pairs 110A-110B may expire after a week, a month, or year, whereas each of short-term key pairs 306A-306B may expire after a certain number of minutes, an hour, or a day.

A user is enabled to update information stored in identity map utilizing update API 302. Examples of information that is updateable includes, but is not limited, the user's identity, the long-term public signing key of the user and/or the short-term public encryption key of the user. In accordance with an embodiment, identity map 108 is configured such that only the user is allowed to update identity map 108 with their short-term public encryption key. This is achieved by signing the user's short-term public encryption key with the user's long-term private signing key, for example, by an application (e.g., application 308A or 308B). This advantageously prevents rogue users and the organization that maintains identity map 108 from tampering with keys of other users. The user may periodically update identity map 108 with new short-term public encryption keys as the old short-term public encryption key expires. This way, if the old short-term public encryption key is somehow compromised, the new short-term public encryption will be used.

To update identity map 108 with the short-term public encryption key of a user of computing device 102A, the short-term public encryption key is signed, for example, by application 308A, and application 308A sends a request 310A on behalf of the user to update API 302. In accordance with an embodiment, request 310A comprises digest 118A, which is representative of a state of ledger database 106, and the signed, short-term public encryption key of the user. In accordance with another embodiment, digest 118A and the signed, short-term public encryption key are included in separate requests to update API 302. It is noted in embodiments that a plurality of digests is provided to update API 302 via request(s), where the plurality of digests comprises some or all of the digests previously generated by ledger 202.

Update API 302 provides digest 118A to database verifier 304. Database verifier 304 validates ledger database 106 to determine whether ledger database 106 has been tampered with. For example, database verifier 304 generates a hierarchical hash data structure, such as a Merkle tree, based on the rows of tables (e.g., identity map 108) of ledger database 106. For instance, database verifier 304 generates a leaf node for each row of ledger database 106, where each leaf node comprises the contents of the corresponding row. Database verifier 304 then hashes each leaf node to generate a hash value for the leaf nodes. For instance, the contents of the leaf node are input into a hash function, which outputs the hash value. For each node that is not a leaf, database verifier 304 generates a hash value therefor that is based on the hash values of its child nodes. For instance, for a given node that is not a leaf, the hash values of its child nodes are input into a hash function, which outputs the hash value therefor. Database verifier 304 then generates a root hash value of the hierarchical hash data structure (e.g., a root hash value of the root node of the hierarchical hash data structure) based on the hash values of its child nodes. For instance, the hash values of its child nodes are input into a hash function, which outputs the root hash value.

Database verifier 304 then compares the determined root hash value to digest 118A received via request 310A. If the determined root hash value is equal to digest 118A, then database verifier 304 determines that ledger database 106 has not been tampered with and provides a notification 312 to update API 302 indicating that ledger database 106 has not been tampered with.

Responsive to receiving notification 312, update API 302 provides the short-term public encryption key to ledger database 106. Using the long-term public signing key of the user (e.g., LK_PK_A in column 116), ledger database 106 verifies that the short-term public encryption key was signed using the user's long-term private signing key. If ledger database 106 determines that the short-term public encryption key was signed using the user's long-term private signing key, ledger database 106 updates identity map 108 to include the short-term public encryption key. For instance, database host 104 stores the short-term public encryption key (e.g., ST_PK_A) in a column 320 of identity map 108 configured to store short-term public encryption keys. This way, the short-term public encryption key is associated with the long-term public signing key and the identity of the user.

If ledger database 106 determines that the short-term public encryption key was not signed using the user's long-term private signing key, ledger database 106 does not update identity map 108 with the short-term public encryption key. In accordance with an embodiment, update API 302 returns an error message to application 308A indicating that the short-term public encryption key was not successfully stored in identity map 108.

If the determined root hash value is not equal to digest 118A, then database verifier 304 determines that ledger database 106 has been tampered with and issues a notification to update API 302. In accordance with an embodiment, responsive to receiving the notification, update API 302 returns an error message to application 308A indicating that ledger database 106 has been tampered with and/or the short-term public encryption key was not successfully stored in identity map 108.

In accordance with an embodiment where some or all previously-generated digests are provided to update API 302, database verifier 304 verifies all such digests. This way, if an attacker manages to compromise ledger database 106 prior to the latest digest being generated and provides computing device(s) 102A-102B with that digest, database verifier 304 will still be able to verify that the ledger database 106 was compromised.

Computing device 102B updates identity map 108 in a similar fashion. For example, application 308B issues a request 310B to update API 302 on behalf of the user of computing device 102B to update API 302. In accordance with an embodiment, request 310B comprises digest 118B, which is representative of a state of ledger database 106, and the signed, short-term public encryption key of the user. In accordance with another embodiment, digest 118B and the signed, short-term public encryption key are included in separate requests to update API 302.

Database verifier 304 validates ledger database 106 by generating a root hash value representative of ledger database 106 in a similar manner as described above with respect to computing device 102A. Database verifier 304 then compares the determined root hash value to digest 118B received via request 310B. If the determined root hash value is equal to digest 118B, then database verifier 304 determines that ledger database 106 has not been tampered with and provides notification 312 to update API 302 indicating that ledger database 106 has not been tampered with.

Responsive to receiving notification 312, update API 302 provides the short-term public encryption key to ledger database 106. Using the long-term public signing key of the user (e.g., LK_PK_B in column 116), ledger database 106 verifies that the short-term public encryption key was signed using the user's long-term private signing key. If ledger database 106 determines that the short-term public encryption key was signed using the user's long-term private signing key, ledger database 106 updates identity map 108 to include the short-term public encryption key. For instance, database host 104 stores the short-term public encryption key (e.g., ST_PK_B) in a column 320 of identity map 108 configured to store short-term public encryption keys. This way, the short-term public encryption key is associated with the long-term public signing key and the identity of the user.

After some time, ledger 202 of database host 104 generates another digest 318 representative of the state of ledger database 106 in a similar manner as described above with reference to FIG. 2 based on identity map 108 (which is stored in updateable ledger table 202, as shown in FIG. 2) and history table 204 (as also shown in FIG. 2). The updated digest is made accessible to users of computing devices 102A-102B. In accordance with an embodiment, the organization that maintains identity map 108 publishes updated digest 318, for example, via a web page that is accessible to computing devices 102A-102B. In accordance with another embodiment, computing device(s) 102A-102B obtains updated digest 318 from database host 104. For example, database host 104 provides a request comprising digest 318 to computing devices 102A-102B, and computing devices 102A-102B store digest 318, for example, in a memory thereof. In another example, computing devices 102A-102B provide a request to database host 104 for digest 318, and database host 104 provides digest 318 to computing devices 102A-102B via a response.

Accordingly, an identity map may be updated many ways. For example, FIG. 4 shows a flowchart 400 for updating an identity map, according to an example embodiment. In an embodiment, flowchart 400 is implemented by system 300, as shown in FIG. 3. Accordingly, flowchart 400 will be described with continued reference to FIG. 3. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding flowchart 400 and system 300 of FIG. 3.

Flowchart 400 begins with step 402. In step 402, a request is received from a computing device on behalf of a first user to update an identity map maintained by a ledger database. The request comprises a first digest representative of a state of the ledger database and comprises a short-term public encryption key of the first user. The identity map comprises at least an identity of the first user and a long-term public signing key of the first user. For example, with reference to FIG. 3, update API 302 of database host 104 receives a request 310A from application 308A of computing device 102A to update identity map 108 maintained by ledger database 106. Request 310A comprises digest 118A and comprises a short-term public encryption key of short-term key pair 306A.

In accordance with one or more embodiments, the short-term public encryption key is signed by a long-term private signing key corresponding to the long-term public signing key. For example, with reference to FIG. 3, application 308A signs the short-term public encryption key of short-term key pair 306A with the long-term private signing key of long-term key pair 110A.

In accordance with one or more embodiments, the short-term public encryption key is configured to encrypt communications to the computing device. For example, with reference to FIG. 3, the short-term public encryption key (ST_PK_A) stored in identity map 108 is configured to encrypt communications to computing device 102A. Additional details regarding encrypting communications utilizing short-term public encryption keys are provided below with reference to FIG. 12.

In accordance with one or more embodiments, the identity comprises at least one of an email address of the first user, a username of the first user, or a phone number of the first user. For example, with reference to FIG. 3, User Identity 1 in column 114 of identity map 108 comprises at least one of an email address of the first user, a username of the first user, or a phone number of the first user.

In step 404, the ledger database is validated based at least on the first digest. For example, with reference to FIG. 3, update API 302 provides digest 118A to database verifier 304. Database verifier 304 validates ledger database 106 based at least on digest 118A. Additional details regarding validating ledger database 106 is described below with reference to FIGS. 9-11.

In step 406, responsive to said validating, the short-term public encryption key is associated with the long-term public signing key and the identity of the first user in the identity map. For example, with reference to FIG. 3, responsive to a successful validation of ledger database 106, update API 302 provides the short-term public encryption key to ledger database 106, and ledger database 106 associates, in identity map 108, the short-term public encryption key with the long-term public signing key and the identity of the first user. For example, ledger database 106 stores the short-term public encryption key (ST_PK_A) in column 320, thereby associating the short-term public encryption key with the long-term public signing key (LT_PK_A) stored in column 116 and the identity of the user stored in column 114.

In step 408, a second digest representative of the state of the ledger database is generated after associating the short-term public encryption key with the long-term public signing key and the identity of the first user. For example, with reference to FIG. 3, ledger 202 generates updated digest 318 representative of the state of ledger database 106 after associating the short-term public encryption key with the long-term public signing key and the identity of the first user.

In step 410, the first user is provided access to the second digest. For example, with reference FIG. 3, the user of computing device 102A is provided access to updated digest 318.

In accordance with one or more embodiments, the first user is provided access by at least one of publishing the second digest to a web page that is accessible to the computing device or providing the second digest to the computing device. For example, with reference to FIG. 3, database host 104 publishes updated digest 318 to a web page that is accessible to computing device 102A or provides updated digest 318 to computing device 102A. It is noted that in embodiments database host 104 provides access to some or all digests that are generated by ledger database 106 over time.

FIG. 5 depicts a block diagram of a system 500 configured to remove information from an identity map in accordance with an example embodiment. As shown in FIG. 5, system 500 comprises a computing device 502 and DB host 104, a described above with reference to FIG. 1. DB host 104 executes ledger database 106 comprising identity map 108 and comprises ledger 202, a revoke API 506 and a database verifier 504. Computing device 502 is an example of computing devices 102A-102N. In the example shown in FIG. 5, computing device 502 is associated with an administrator of the organization that maintains identity map 108. As also shown in FIG. 5, computing device 502 comprises an application 508 and a digest 518. Digest 518 is an example of digests 118A-118N, as described above with reference to FIG. 1. Application 508 is a software application that is utilized to access database host 104. In an embodiment in which identity map 108 is accessible over a network, application 508 is browser application (e.g., Microsoft Edge™ published by Microsoft Corporation).

In an example, an administrator would remove (or revoke) an identity and/or keys associated therewith of another user from identity map 108 in the event that the other user is no longer part of the organization. An administrator is enabled to remove information stored in identity map utilizing revoke API 506. For instance, the user causes application 508 to issue a request 510 on behalf of the administrator to revoke API 506. In accordance with an embodiment, request 510 comprises digest 518, which is representative of a state of ledger database 106, and the identity of the user for which key(s) are to be revoked. In accordance with another embodiment, digest 518 and the identity are included in separate requests to revoke API 506. It is noted in embodiments that a plurality of digests is provided to revoke API 506 via request(s), where the plurality of digests comprises some or all of the digests previously generated by ledger 202.

Revoke API 506 provides digest 518 to database verifier 504. Database verifier 504 is an example of database verifier 304, as described above with reference to FIG. 3. Database verifier 504 validates ledger database 106 to determine whether ledger database 106 has been tampered with. For example, database verifier 504 generates a hierarchical hash data structure, such as a Merkle tree, based on the rows of tables (e.g., identity map 108) of ledger database 106. For instance, database verifier 504 generates a leaf node for each row of ledger database 106, where each leaf node comprises the contents of the corresponding row. Database verifier 504 then hashes each leaf node to generate a hash value for the leaf nodes. For instance, the contents of the leaf node are input into a hash function, which outputs the hash value. For each node that is not a leaf, database verifier 504 generates a hash value therefor that is based on the hash values of its child nodes. For instance, for a given node that is not a leaf, the hash values of its child nodes are input into a hash function, which outputs the hash value therefor. Database verifier 504 then generates a root hash value of the hierarchical hash data structure (e.g., a root hash value of the root node of the hierarchical hash data structure) based on the hash values of its child nodes. For instance, the hash values of its child nodes are input into a hash function, which outputs the root hash value.

Database verifier 504 then compares the determined root hash value to digest 518 received via request 510. If the determined root hash value is equal to digest 518, then database verifier 504 determines that ledger database 106 has not been tampered with and provides a notification 512 to revoke API 506 indicating that ledger database 106 has not been tampered with.

Responsive to receiving notification 512, revoke API 506 provides the identity included in request 510 to ledger database 106. Ledger database 106 searches for an entry (or row) of identity map 108 that comprises the identity included in request 510. In the example shown in FIG. 5, the identity corresponds to User Identity 2 in column 114. After locating the entry, ledger database 106 removes the identity, the long-term public signing key (LT_PK_B) and/or the short-term public encryption key (ST_PK_B) associated therewith. In an example, request 510 specifies which of the long-term public signing key (LT_PK_B) and/or the short-term public encryption key (ST_PK_B) are to be removed.

If the determined root hash value is not equal to digest 518, then database verifier 504 determines that ledger database 106 has been tampered with and issues a notification to revoke API 506. In accordance with an embodiment, responsive to receiving the notification, revoke API 506 returns an error message to application 508 indicating that ledger database 106 has been tampered with and/or the identity, long-term public signing key, and/or the short-term public encryption key were not successfully removed from identity map 108.

In accordance with an embodiment where some or all previously-generated digests are provided to revoke API 506, database verifier 504 verifies all such digests. This way, if an attacker manages to compromise ledger database 106 prior to the latest digest being generated and provides computing device 502 with that digest, database verifier 504 will still be able to verify that the ledger database 106 was compromised.

After some time, ledger 202 of database host 104 generates another digest 520 representative of the state of ledger database 106 in a similar manner as described above with reference to FIG. 2 based on identity map 108 (which is stored in updateable ledger table 202, as shown in FIG. 2) and history table 204 (as also shown in FIG. 2). As described above with reference to FIG. 2, the information removed from identity map 108 is retained via history table 204. Updated digest 520 is made accessible to the administrator of computing device 502. In accordance with an embodiment, the organization that maintains identity map 108 publishes updated digest 520, for example, via a web page that is accessible to computing device 502. In accordance with another embodiment, computing device 502 obtains updated digest 520 from database host 104. For example, database host 104 provides a request comprising digest 520 to computing device 502, and computing device 502 stores digest 520, for example, in a memory thereof. In another example, computing device 502 provides a request to database host 104 for digest 520, and database host 104 provides digest 520 to computing device 502 via a response.

Accordingly, information from an identity map may be removed in many ways. For example, FIG. 6 shows a flowchart 600 for removing information from an identity map, according to an example embodiment. In an embodiment, flowchart 600 is implemented by system 500, as shown in FIG. 5, although the embodiments described herein are not so limited. Accordingly, flowchart 600 will be described with continued reference to FIG. 5. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding flowchart 600 and system 500 of FIG. 5.

Flowchart 600 begins with step 602. In step 602, a request is received from a computing device on behalf of a first user to remove at least one of a long-term public signing key or a short-term public encryption key of a second user from an identity map maintained by a ledger database. The request comprises a first digest representative of a state of the ledger database. For example, with reference to FIG. 5, revoke API 506 of database host 104 receives a request 510 from application 308 of computing device 502 to update identity map 108 maintained by ledger database 106. Request 510 comprises digest 518.

In accordance with one or more embodiments, the short-term public encryption key is signed by a long-term private signing key corresponding to the long-term public signing key. For example, with reference to FIG. 5, a short-term public encryption key (ST_PK_B) is signed by a long-term private signing key (LT_PK_B).

In accordance with one or more embodiments, the identity comprises at least one of an email address of the second user, a username of the second user, or a phone number of the second user. For example, with reference to FIG. 5, User Identity 2 in column 114 of identity map 108 comprises at least one of an email address of the second user, a username of the second user, or a phone number of the second user.

In accordance with one or more embodiments, the request further comprises the identity of the second user. For example, with reference to FIG. 5, request 510 further comprises the identity (e.g., User Identity 2) of the second user.

In step 604, the ledger database is validated based at least on the first digest. For example, with reference to FIG. 5, revoke API 506 provides digest 518 to database verifier 504. Database verifier 504 validates ledger database 106 based at least on digest 518. Additional details regarding validating ledger database 106 is described below with reference to FIG. 9-11.

In step 606, responsive to said validating, the at least one of the long-term public signing key or the short-term public encryption key of the second user is removed from the identity map. For example, with reference to FIG. 5, responsive to a successful validation of ledger database 106, revoke API 506 removes the at least one of the long-term public signing key (LT_PK_B) or the short-term public encryption key (ST_PK_B) of the second user stored in columns 116 and 320.

In accordance with one or more embodiments, the identity of the second user and at least one of the long-term public signing key or the short-term public encryption key of the second user is removed from the identity map. For example, with reference to FIG. 5, the identity of the second user (User Identity 2) and at least one of the long-term public signing key (LT_PK_B) or the short-term public encryption key (ST_PK_B) of the second user is removed from identity map 108.

In step 608, a second digest representative of the state of the ledger database is generated after removing the at least one of the long-term public signing key or the short-term public encryption key of the second user. For example, with reference to FIG. 5, ledger 202 generates updated digest 520 representative of the state of ledger database 106 after removing the at least one of the long-term public signing key or the short-term public encryption key of the second user.

In step 610, the first user is provided access to the second digest. For example, with reference FIG. 5, the user of computing device 502 is provided access to updated digest 520.

In accordance with one or more embodiments, the first user is provided access by at least one of publishing the second digest to a web page that is accessible to the computing device or providing the second digest to the computing device. For example, with reference to FIG. 5, database host 104 publishes updated digest 520 to a web page that is accessible to computing device 502 or provides updated digest 520 to computing device 502.

FIG. 7 depicts a block diagram of a system 700 configured to retrieve information from an identity map in accordance with an example embodiment. As shown in FIG. 7, system 700 comprises computing device 102B and DB host 104, a described above with reference to FIG. 1. DB host 104 executes ledger database 106 comprising identity map 108 and comprises ledger 202, a lookup API 702, and a database verifier 704. As also shown in FIG. 7, computing device 102B comprises long-term signing key pair 110B, digest 118B, a short-term encryption key pair 306B, and application 308B. Examples of application 308B include, but are not limited to, Microsoft Teams™ published by Microsoft Corporation of Redmond, WA, Microsoft SharePoint™ published by Microsoft Corporation and/or the like.

A user is enabled to lookup information stored in identity map 108 utilizing lookup API 702. Examples of information that may be looked up include, but are not limited, a user's identity, a long-term public signing key of a user and/or a short-term public encryption key of a user.

To lookup information from identity map 108, application 308A sends a request 710 on behalf of a user to lookup API 702. In accordance with an embodiment, request 710 comprises an identity of the user for which information being looked up and digest 118B, which is representative of a state of ledger database 106. In accordance with another embodiment, the identity and digest 118B are included in separate requests to lookup API 702. It is noted in embodiments that a plurality of digests is provided to lookup API 702 via request(s), where the plurality of digests comprises some or all of the digests previously generated by ledger 202.

Update API 702 provides digest 118B to database verifier 704. Database verifier 704 is an example of database verifier 504, as described above with reference to FIG. 5. Database verifier 704 validates ledger database 106 to determine whether ledger database 106 has been tampered with. For example, database verifier 704 generates a hierarchical hash data structure, such as a Merkle tree, based on the rows of tables (e.g., identity map 108) of ledger database 106. For instance, database verifier 704 generates a leaf node for each row of ledger database 106, where each leaf node comprises the contents of the corresponding row. Database verifier 704 then hashes each leaf node to generate a hash value for the leaf nodes. For instance, the contents of the leaf node are input into a hash function, which outputs the hash value. For each node that is not a leaf, database verifier 704 generates a hash value therefor that is based on the hash values of its child nodes. For instance, for a given node that is not a leaf, the hash values of its child nodes are input into a hash function, which outputs the hash value therefor. Database verifier 704 then generates a root hash value of the hierarchical hash data structure (e.g., a root hash value of the root node of the hierarchical hash data structure) based on the hash values of its child nodes. For instance, the hash values of its child nodes are input into a hash function, which outputs the root hash value.

Database verifier 704 then compares the determined root hash value to digest 118B received via request 710. If the determined root hash value is equal to digest 118B, then database verifier 704 determines that ledger database 106 has not been tampered with and provides a notification 712 to lookup API 702 indicating that ledger database 106 has not been tampered with.

Responsive to receiving notification 712, lookup API 702 provides a search query 706 to ledger database 106. Search query 706 comprises the identity specified by request 710. Upon locating an entry of ledger database 106 that comprises the identity, ledger database 106 returns information associated therewith (e.g., the long-term public signing key and/or the short-term public encryption key associated with the identity) to lookup API 702 via a response 708. Lookup API 701 provides the lookup information to application 308 via a response 714.

If the determined root hash value is not equal to digest 118B, then database verifier 704 determines that ledger database 106 has been tampered with and issues a notification to lookup API 702. In accordance with an embodiment, responsive to receiving the notification, lookup API 702 returns an error message to application 308B indicating that ledger database 106 has been tampered with and/or that lookup operation was not completed.

In accordance with an embodiment where some or all previously-generated digests are provided to lookup API 702, database verifier 704 verifies all such digests. This way, if an attacker manages to compromise ledger database 106 prior to the latest digest being generated and provides computing device 102B with that digest, database verifier 704 will still be able to verify that the ledger database 106 was compromised.

Accordingly, information from an identity map may be retrieved in many ways. For example, FIG. 8 shows a flowchart 800 for retrieving information from an identity map, according to an example embodiment. In an embodiment, flowchart 800 is implemented by system 700, as shown in FIG. 7, although the embodiments described herein are not so limited. Accordingly, flowchart 800 will be described with continued reference to FIG. 7. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding flowchart 800 and system 700 of FIG. 7.

Flowchart 800 begins with step 802. In step 802, a request is received from a computing device on behalf of a first user to retrieve a short-term public encryption key of a second from an identity map maintained by a ledger database and an identity of the second user. The request comprises a digest representative of a state of the ledger database and comprises an identity of the second user. For example, with reference to FIG. 7, lookup API 702 of database host 104 receives a request 710 from application 308B of computing device 102B to retrieve information from identity map 108 maintained by ledger database 106. Request 710 comprises digest 118B and comprises an identity (e.g., User Identity 1) of the second user.

In accordance with one or more embodiments, the short-term public encryption key is signed by a long-term private signing key corresponding to the long-term public signing key. For example, with reference to FIG. 7, application 308B signs the short-term public encryption key of short-term key pair 306B with the long-term private signing key of long-term key pair 110B.

In accordance with one or more embodiments, the short-term public encryption key is configured to encrypt communications from the computing device of the first user to a computing device of the second user. For example, with reference to FIG. 7, the short-term public encryption key (ST_PK_A) stored in identity map 108 is configured to encrypt communications from computing device 102B to another computing device (e.g., computing device 102A) of the second user. Additional details regarding encrypting communications utilizing short-term public encryption keys are provided below with reference to FIG. 12.

In accordance with one or more embodiments, the identity comprises at least one of an email address of the second user, a username of the second user, or a phone number of the second user. For example, with reference to FIG. 7, User Identity 1 in column 114 of identity map 108 comprises at least one of an email address of the second user, a username of the second user, or a phone number of the second user.

In step 804, the ledger database is validated based at least on the digest. For example, with reference to FIG. 7, lookup API 702 provides digest 118B to database verifier 704. Database verifier 704 validates ledger database 106 based at least on digest 118B. Additional details regarding validating ledger database 106 is described below with reference to FIG. 9-11.

In step 806, responsive to said validating, the short-term public encryption key is located in the identity map based on the identity of the second user. For example, with reference to FIG. 7, lookup API 702 provides search query 706 to ledger database 106, and ledger database 106 searches for an entry in ledger database 106 that comprises the identity. After locating the entry, ledger database 106 locates the short-term public encryption key associated with the identity in identity map 108 and provides the short-term public encryption key to lookup API 702 via response 708.

In accordance with one or more embodiments, responsive to said validating, a long-term public signing key in the identity map is located based on the identity of the second user. For example, with reference to FIG. 7, responsive to search query 706, ledger database 106 locates the long-term public signing key associated with the identity in identity map 108.

In step 808, a response is provided to the computing device that comprises the short-term public encryption key. For example, with reference to FIG. 7, lookup API 702 provides response 714 comprising the short-term public encryption key (ST_PK_A) to computing device 102B.

In accordance with one or more embodiments, the response further comprises the long-term public signing key. For example, with reference to FIG. 7, lookup API 702 provides the long-term public encryption key to computing device 102B via a response (e.g., response 708).

FIG. 9 shows a flowchart 900 for validating a ledger database, according to an example embodiment. In an embodiment, flowchart 900 is implemented by a database verifier 1000, as shown in FIG. 10. FIG. 10 depicts a block diagram of database verifier 1000 in accordance with an example embodiment. Database verifier 1000 is an example of database verifier 304, 504, or 704, as respectively described above with reference to FIGS. 3, 5, and 7. As shown in FIG. 10, database verifier 1000 comprises a hierarchical hash data structure generator 1002, a root hash determiner 1004, and a comparator 1006. An example of a hierarchical hash data structure is shown in FIG. 11. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding flowchart 900 and database verifier 1000 of FIG. 10.

Flowchart 900 begins with step 902. In step 902, a hierarchical hash data structure representative of the rows of the ledger database is generated. For example, with reference to FIGS. 10 and 11, hierarchical hash data structure generator 1002 generates a hierarchical hash data structure 1110 representative of the rows of ledger database 106. With further reference to FIG. 11, hierarchical hash data structure generator 1002 initially generates leaf nodes 1118-1132, each of which is corresponding to a respective row of rows 1102-1116 of ledger database 106. Hierarchical hash data structure generator 1002 generates a hash value for each of leaf nodes 1118-1132, which is based on the data stored in a corresponding row. For instance, the data of row 1102 is provided to a hash function (e.g., a SHA-256 based hash function) that generates a hash value H_(A), which is stored in leaf node 1118. The data of row 1104 is provided to a hash function that generates a hash value H_(B), which is stored in leaf node 1120. The data of row 1106 is provided to a hash function that generates a hash value H_(C), which is stored in leaf node 1122. The data of row 1108 is provided to a hash function that generates a hash value H_(D), which is stored in leaf node 1124. The data of row 1110 is provided to a hash function that generates a hash value H_(E), which is stored in leaf node 1126. The data of row 1112 is provided to a hash function that generates a hash value H_(F), which is stored in leaf node 1128. The data of row 1114 is provided to a hash function that generates a hash value H_(G), which is stored in leaf node 1130. The data of row 1116 is provided to a hash function that generates a hash value H_(H), which is stored in leaf node 1132.

Hierarchical hash data structure generator 1002 then generates parent nodes 1134-1140 based on the hash values of their respective children. For instance, the hash values of nodes 1118 and 1120 are provided to a hash function that generates a hash value H_(AB), which is stored in node 1134. The hash values of nodes 1122 and 1124 are provided to a hash function that generates a hash value H_(CD), which is stored in node 1136. The hash values of nodes 1126 and 1128 are provided to a hash function that generates a hash value H_(EF), which is stored in node 1138. The hash values of nodes 1130 and 1132 are provided to a hash function that generates a hash value H_(GH), which is stored in node 1140.

The foregoing process continues until a single root node is generated for all the rows of ledger database 106. For instance, as further shown in FIG. 11, hierarchical hash data structure generator 1002 then generates parent nodes 1134-1140 based on the hash values of their respective children. For instance, the hash values of nodes 1134 and 1136 are provided to a hash function that generates a hash value H_(ABCD), which is stored in node 1142. The hash values of nodes 1138 and 1140 are provided to a hash function that generates a hash value H_(EFGH), which is stored in node 1140. Hierarchical hash data structure generator 1002 then generates a parent node 1146 based on the hash values of its respective children. For instance, the hash values of nodes 1142 and 1144 are provided to a hash function that generates a hash value H_(ABCDEFGH), which is stored in node 1146. Node 1146 is the root node of hierarchical hash data structure generator 1002.

In accordance with one or more embodiments, the hierarchical hash data structure is a Merkle tree. For example, with reference to FIG. 11, hierarchical hash data structure 1100 is a Merkle tree.

In step 904, a root hash value for the root node of the hierarchical hash data structure is determined. For example, with reference to FIGS. 10 and 11, root hash determiner 1004 determines the root hash value (e.g., H_(ABCDEFGH)) of root node 1146. Root hash determiner 1104 provides the root hash value (shown as root hash value 1008) to comparator 1106.

In step 906, a determination is made that the root hash value is equal to the digest. For example, with reference to FIG. 10, comparator 1006 compares root hash value 1008 to a digest 1018 to determine whether they are equal to each other. In response to determining that they are equal to each other, comparator 1006 determines that ledger database 106 has not been tampered with and provides a notification 1012 indicating as much. Notification 1012 is an example of notifications 312, 512, and 712, as respectively described above with reference to FIGS. 3, 5, and 7. Digest 1018 is an example of digests 118A, 118B and 518, as respectively described above with reference to FIGS. 1, 3, 5, and 7.

III. Additional Embodiments

- A. Signature Chains

When a user wants to associate a new computing device's public keys to the user's identity, the new device's public keys are authorized by a previously-authorized public key (e.g., a previously-authorized public signing key digitally signs the new public keys). In other words, a new device of a user is authorized by one of the existing devices of the same user. For instance, suppose a user is provisioned a new device by the user's organization. The long-term public signing key of the user's original device is used to sign the long-term public signing key and/or short-term public encryption key of the user's new device. The foregoing technique is referred to as signature chaining, as each key in the signature chain is authorized by a previously-authorized signing key.

In accordance with an embodiment, the user obtains an initial verifiable binding between the user's identity and the user's public keys, for example, via an identity provider (e.g., Azure Active Directory™ by Microsoft Corporation). In an embodiment, the initial binding is signed by an administrator's signing key. In another embodiment, the initial binding is signed by a signing key that is already stored in identity map 108 for a different user (e.g., a manager).

At lookup time, the validity of the long-term public signing key used to sign the keys of the new device, as well as keys of the new device are verified. Such signature chains advantageously prevent an adversary from associating rogue public keys for any user in the system.

- B. Local Verification

In the embodiments described above, a database verifier (e.g., database verifiers 304, 504, and 704) executing on database host 104 verifies whether ledger database 106 has been tampered with. In accordance with one or more other embodiments, the verification is performed locally on a computing device (e.g., computing devices 102A-102N). The foregoing is achievable using proofs of the hierarchical hash data structure (e.g., Merkle proofs), which are maintained by the database host (e.g., database host 104).

For instance, as described above, a computing device obtains a digest (e.g., digest 118A-118N) from ledger database 108 and stores the digest locally. When performing a lookup operation (as described above with reference to FIGS. 7-8), the computing device provides a request (e.g., request 710) to a lookup API (e.g., lookup API 702) for a short-term public encryption key of a particular user. In response, ledger database 106 provides a response comprising the short-term public encryption key, along with a proof of membership. The proof of membership comprises all the hashes associated with the short-term public encryption key that are needed to be combined to obtain the root hash value of ledger database 106. For example, with reference to FIG. 11, suppose the requested short-term public encryption key is included in R_(C). In this example, the hash values stored in nodes 1124, 1134, and 1144 would be provided as the proof of membership, as these hash values are required to reconstruct the root hash value.

The computing device generates a hash value of the requested short-term public encryption key and provides the hash value and the received hash value of node 1124 to a hash function, which generates a hash value H_(CD). The computing device then provides hash value H_(CD)and the received hash value of node 1134 to a hash function, which generates a hash value H_(ABCD). The computing device then provides hash value H_(ABCD)and the received hash value of node 1144 to a hash function, which generates a hash value H_(ABCDEFGH). Using this technique, the computing device has generated a version of the root hash value. The computing device then compares the generated root hash value to the digest maintained thereby to determine whether they are equal. If they are equal, then the computing device determines that ledger database 106 has not been tampered with.

The computing device then verifies the validity of the short-term public encryption key by determining whether the short-term public encryption key was signed by the associated user's long-term private encryption key, as described above.

Responsive to determining that ledger database 106 has not been tampered with and validating the short-term public encryption key, the computing device determines that the short-term public encryption key is valid and uses it accordingly.

The foregoing technique advantageously enables the computing device to verify the short-term public encryption key without having to download the entire dataset of ledger database 106, thereby conserving compute resources (e.g., processing cycles, memory, storage, input/output (I/O) transactions, power, etc.).

It is noted that in accordance with one or more embodiments, the computing device stores locally (or caches) keys of other users. In this case, the computing device also compares the key to the locally-cached version of the key to determine whether they are consistent as an additional verification check.

- C. Encrypted Communications

As described herein, identity map 108 is utilized to enable encrypted communications between different parties, either belonging to the same or different organizations. In an embodiment in which parties from different organizations intend to communicate, each organization publishes the public keys of their members, and each party obtains the public keys accordingly. FIG. 12 depicts a block diagram of a system 1200 for encrypting communications between two parties from different organizations in accordance with an example embodiment. As shown in FIG. 12, system 1200 comprises an identity map 1208A, an identity map 1208B, a computing device 1202A, and a computing device 1202B. Identity maps 1208A and 1208B are examples of identity map 108 and computing devices 1202A and 1202B are examples of computing devices 102A-102C, as described above.

Identity map 1208A is maintained by a first organization, and computing device 1202A is associated with a first user of the first organization. Identity map 1208B is maintained by a second organization, and computing device 1202B is associated with a second user of the second organization. The first organization makes identity map 1208B publicly-accessible, e.g., by publishing identity map 1208A to a first website or making identity map 1208A available via ledger database 106, and the second organization makes identity map 1208B publicly-accessible, e.g., by publishing identity map 1208B to a second website or making identity map 1208A available via ledger database 106.

Computing device 1202A comprises an application 1208A, a long-term key pair 1210A, a short-term key pair 1206A, and a random session key 1204A. Computing device 1202B comprises an application 1208B, a long-term key pair 1210B, a short-term key pair 1206B, and a random session key 1204B. Applications 1208A and 1208B are examples of applications 308A and 308B, as described above with reference to FIG. 3. Long-term key pairs 1210A and 1210B are examples of long-term key pairs 110A and 110B, as described above with reference to FIG. 3. Short-term key pairs 1206A and 1206B are examples of short-term key pairs 306A and 306B, as described above with reference to FIG. 3.

Suppose the first user of computing device 1202A wants to send an encrypted communication to the second user of computing device 1202B utilizing application 1208A, which, for example, is a messaging application. In this example, the user obtains the short-term public encryption key of the second user from identity map 1208B. In the example shown in FIG. 12, the second user's short-term public encryption key corresponds to ST_PK_B. In accordance with an embodiment, the user obtains the short-term public encryption key from a website on which it is published. In accordance with another embodiment, application 1208A obtains the short-term public encryption key from ledger database 108 via lookup API 702, as described above with reference to FIGS. 7-8.

Application 1208A then obtains a random session key 1204A. For instance, as shown in FIG. 12, computing device 1202A stores random session key 1204A. Random session key 1204A is generated by a trusted or customer-controlled service. Random session key 1204 is a randomly-generated number (e.g., the service comprises a random number generator that generates session key 1204A). In accordance with an embodiment, the service executes locally on each of computing devices 1202A-1202B. In accordance with another embodiment, the service executes remotely from computing devices 1202A-1202B. In accordance with such an embodiment, session key 1204A is generated from a key generating web service, where computing devices 1202A-1202B submit a request to the service for a random session key. Responsive to receiving the request, the service generates (e.g., randomly) the random session key to the requesting computing device via a response. In accordance with an embodiment, the service is a Proof of Possession (PoP)-based service; although it is noted that the embodiments described herein are not so limited.

Application 1208A then encrypts messages to be sent to application 1208B of the second user using random session key 1204A. Application 1208A also encrypts random session key 1204A with the short-term public encryption key of the second user (e.g., ST_PK_B). Application 1208A then sends both the encrypted message (shown as encrypted message 1212) and the encrypted random session key (shown as encrypted random session key 1214) to application 1208B of the second user via one or more requests.

Application 1208B decrypts encrypted random session key 1214 using the short-term private encryption key of short-term key pair 1206B of the second user to obtain the random session key. Application 1208B then decrypts encrypted message 1212 using the decrypted random session key.

Similarly, to send an encrypted message from the second user to the first user, application 1208B obtains random session key 1204B in a similar manner as described above with reference to random session key 1204A. Application 1208B then encrypts messages to be sent to application 1208A of the first user using random session key 1204B. Application 1208B also encrypts random session key 1204B with the short-term public encryption key of the first user (e.g., ST_PK_A). Application 1208B then sends both the encrypted message (shown as encrypted message 1216) and the encrypted random session key (shown as encrypted random session key 1218) to application 1208A of the first user via one or more requests.

Application 1208A decrypts encrypted random session key 1218 using the short-term private encryption key of short-term key pair 1206A of the first user to obtain the random session key. Application 1208A then decrypts encrypted message 1216 using the decrypted random session key.

IV. Example Mobile Device and Computer System Implementation

The systems and methods described above in reference to FIGS. 1-12, may be implemented in hardware, or hardware combined with one or both of software and/or firmware. For example, system 1300 of FIG. 13 may be used to implement any of database host 104, ledger database 106, identity map 108, ledger 206, updateable ledger table 202, history table 204, applications 308A-308B, update API 302, database verifier 304, revoke API 506, database verifier 504, application 508, lookup API 702, database verifier 704, database verifier 1000, hierarchical hash data structure 1002, root hash determiner 1004, comparator 1006, hierarchical hash data structure 1100, identity maps 1208A-1208B, and/or applications 1208A-1208B, and/or any of the components respectively described therein, and flowcharts 400, 600, 800, and/or 900 may be each implemented as computer program code/instructions configured to be executed in one or more processors and stored in a computer readable storage medium. Alternatively, computing devices 102A-102N, database host 104, ledger database 106, identity map 108, ledger 206, updateable ledger table 202, history table 204, applications 308A-308B, update API 302, database verifier 304, revoke API 506, database verifier 504, application 508, lookup API 702, database verifier 704, database verifier 1000, hierarchical hash data structure 1002, root hash determiner 1004, comparator 1006, hierarchical hash data structure 1100, computing devices 1202A-1202B, identity maps 1208A-1208B, and/or applications 1208A-1208B, and/or any of the components respectively described therein, and flowcharts 400, 600, 800, and/or 900 may be implemented as hardware logic/electrical circuitry. In an embodiment, any of computing devices 102A-102N, database host 104, ledger database 106, identity map 108, ledger 206, updateable ledger table 202, history table 204, applications 308A-308B, update API 302, database verifier 304, revoke API 506, database verifier 504, application 508, lookup API 702, database verifier 704, database verifier 1000, hierarchical hash data structure 1002, root hash determiner 1004, comparator 1006, hierarchical hash data structure 1100, computing devices 1202A-1202B, identity maps 1208A-1208B, and/or applications 1208A-1208B, and/or any of the components respectively described therein, and flowcharts 400, 600, 800, and/or 900 may be implemented in one or more SoCs (system on chip). An SoC may include an integrated circuit chip that includes one or more of a processor (e.g., a central processing unit (CPU), microcontroller, microprocessor, digital signal processor (DSP), etc.), memory, one or more communication interfaces, and/or further circuits, and may optionally execute received program code and/or include embedded firmware to perform functions.

FIG. 13 depicts an exemplary implementation of a computing device 800 in which embodiments may be implemented, including any of computing devices 102A-102N, database host 104, ledger database 106, identity map 108, ledger 206, updateable ledger table 202, history table 204, applications 308A-308B, update API 302, database verifier 304, revoke API 506, database verifier 504, application 508, lookup API 702, database verifier 704, database verifier 1000, hierarchical hash data structure 1002, root hash determiner 1004, comparator 1006, hierarchical hash data structure 1100, computing devices 1202A-1202B, identity maps 1208A-1208B, and/or applications 1208A-1208B, and/or any of the components respectively described therein, and flowcharts 400, 600, 800, and/or 900. The description of computing device 1300 provided herein is provided for purposes of illustration, and is not intended to be limiting. Embodiments may be implemented in further types of computer systems, as would be known to persons skilled in the relevant art(s).

As shown in FIG. 13, computing device 1300 includes one or more processors, referred to as processor circuit 1302, a system memory 1304, and a bus 1306 that couples various system components including system memory 1304 to processor circuit 1302. Processor circuit 1302 is an electrical and/or optical circuit implemented in one or more physical hardware electrical circuit device elements and/or integrated circuit devices (semiconductor material chips or dies) as a central processing unit (CPU), a microcontroller, a microprocessor, and/or other physical hardware processor circuit. Processor circuit 1302 may execute program code stored in a computer readable medium, such as program code of operating system 1330, application programs 1332, other programs 1334, etc. Bus 1306 represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. System memory 1304 includes read only memory (ROM) 1308 and random access memory (RAM) 1310. A basic input/output system 1312 (BIOS) is stored in ROM 1308.

Computing device 1300 also has one or more of the following drives: a hard disk drive 1314 for reading from and writing to a hard disk, a magnetic disk drive 1316 for reading from or writing to a removable magnetic disk 1318, and an optical disk drive 1320 for reading from or writing to a removable optical disk 1322 such as a CD ROM, DVD ROM, or other optical media. Hard disk drive 1314, magnetic disk drive 1316, and optical disk drive 1320 are connected to bus 1306 by a hard disk drive interface 1324, a magnetic disk drive interface 1326, and an optical drive interface 1328, respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data for the computer. Although a hard disk, a removable magnetic disk and a removable optical disk are described, other types of hardware-based computer-readable storage media can be used to store data, such as flash memory cards, digital video disks, RAMS, ROMs, and other hardware storage media.

A number of program modules may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. These programs include operating system 1330, one or more application programs 1332, other programs 1334, and program data 1336. Application programs 1332 or other programs 1334 may include, for example, computer program logic (e.g., computer program code or instructions) for implementing the systems described above, including the embodiments described above with reference to FIGS. 1-12.

A user may enter commands and information into the computing device 1300 through input devices such as keyboard 1338 and pointing device 1340. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, a touch screen and/or touch pad, a voice recognition system to receive voice input, a gesture recognition system to receive gesture input, or the like. These and other input devices are often connected to processor circuit 1302 through a serial port interface 1342 that is coupled to bus 1306, but may be connected by other interfaces, such as a parallel port, game port, or a universal serial bus (USB).

A display screen 1344 is also connected to bus 1306 via an interface, such as a video adapter 1346. Display screen 1344 may be external to, or incorporated in computing device 1300. Display screen 1344 may display information, as well as being a user interface for receiving user commands and/or other information (e.g., by touch, finger gestures, a virtual keyboard, by providing a tap input (where a user lightly presses and quickly releases display screen 1344), by providing a “touch-and-hold” input (where a user touches and holds his finger (or touch instrument) on display screen 1344 for a predetermined period of time), by providing touch input that exceeds a predetermined pressure threshold, etc.). In addition to display screen 1344, computing device 1300 may include other peripheral output devices (not shown) such as speakers and printers.

Computing device 1300 is connected to a network 1348 (e.g., the Internet) through an adaptor or network interface 1350, a modem 1352, or other means for establishing communications over the network. Modem 1352, which may be internal or external, may be connected to bus 1306 via serial port interface 1342, as shown in FIG. 13, or may be connected to bus 1306 using another interface type, including a parallel interface.

As used herein, the terms “computer program medium,” “computer-readable medium,” and “computer-readable storage medium” are used to generally refer to physical hardware media such as the hard disk associated with hard disk drive 1314, removable magnetic disk 1318, removable optical disk 1322, other physical hardware media such as RAMs, ROMs, flash memory cards, digital video disks, zip disks, MEMs, nanotechnology-based storage devices, and further types of physical/tangible hardware storage media (including system memory 1304 of FIG. 13). Such computer-readable storage media are distinguished from and non-overlapping with communication media and propagating signals (do not include communication media and propagating signals). Communication media typically embodies computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wireless media such as acoustic, RF, infrared and other wireless media, as well as wired media. Embodiments are also directed to such communication media.