Methods, systems, and media for recovering identity information in verifiable claims-based systems

A system for restoring user credentials, the system comprising:

• a hardware processor of a computing device that is configured to:
• receive a request to locally restore a digital wallet of a holder associated with a digital wallet application executing on the computing device;
• determine that restoring the digital wallet includes reconstructing a graph of interdependencies between a plurality of issuers and a plurality of claims for the holder;
• restore a root credential;
• in response to restoring the root credential, transmit a plurality of messages that are each signed with the root credential to a plurality of backup providers, wherein each of the plurality of backup providers has a divided portion of the graph of interdependencies between the plurality of issuers and the plurality of claims for the holder stored in a storage device and wherein the graph of interdependencies is unable to be reconstructed from the divided portion;
• receive a plurality of graph portions from at least a portion of the plurality of backup providers in response to each of the portion of the plurality of backup providers determining that the root credential is a correct root credential corresponding to the holder;
• and
• in response to receiving each of the plurality of graph portions, reconstruct the graph of interdependencies between the plurality of issuers and the plurality of claims for the holder using the plurality of received graph portions.

A non-transitory computer-readable medium containing computer executable instructions that, when executed by a processor, cause the processor to perform a method for restoring user credentials, the method comprising:

• receiving, using a computing device, a request to locally restore a digital wallet of a holder associated with a digital wallet application executing on the computing device;
• determining that restoring the digital wallet includes reconstructing a graph of interdependencies between a plurality of issuers and a plurality of claims for the holder;
• restoring a root credential;
• in response to restoring the root credential, transmitting a plurality of messages that are each signed with the root credential to a plurality of backup providers, wherein each of the plurality of backup providers has a divided portion of the graph of interdependencies between the plurality of issuers and the plurality of claims for the holder stored in a storage device and wherein the graph of interdependencies is unable to be reconstructed from the divided portion;
• receiving a plurality of graph portions from at least a portion of the plurality of backup providers in response to each of the portion of the plurality of backup providers determining that the root credential is a correct root credential corresponding to the holder;
• in response to receiving each of the plurality of graph portions, reconstructing the graph of interdependencies between the plurality of issuers and the plurality of claims for the holder using the plurality of received graph portions.