Private contexts through blind signatures and social recovery of any application

1

Update: This is outdated. I posted a simpler solution here: Improved privacy, social recovery for apps, no need for contexts

Overview

There is a potential privacy concern when a BrightID node operator has access to the contextIds of users in multiple application contexts and also has a mapping of contextIds to profile information of those users. This could occur if the node operator is also an adminstrator of several applications, or if there has been a data leak in an application. Such an operator could create unwanted linkage of profile data: for example, that user X of chat application A is also user Y of financial application B.

Using blind signatures, we can have a system where even if a node operator and an app admin are the same, there will be no linkage between a BrightID and contextId, yet users identified by a contextId can still be verified as unique.

A solution is also presented to use BrightID’s social recovery to recover access to any application that uses BrightID.

Solution Sketch

A user commits to a contextId in a context; this is usually a self-generated unique identifier (for example, an Ethereum address). This commitment is then presented to a node as a blinded message along with a BrightID and an application name. It’s shared in that format as a BrightID node “operation.” A node processing the operation checks that the BrightID is verified as unique according to the requirements for the named application, and if so, increments a counter for the BrightID in that context. The node serving the original request then blindly signs the message and attaches the counter value and application name. Because the message was blinded, node operators don’t ever see the contextId.

The user then delivers the signed message to the application. The application opens the message and reads the application name, contextId and counter value, but it can’t see which BrightID is associated with the user. Usages of the counter value are described below.

The solution sketch for restoring access to any BrightID application through social recovery is included below.

Considerations

Verification expiration and contextId rotation

BrightID nodes don’t attach timestamps to the signed messages because these could be used to match a contextId to a BrightID. An application can instead record the fact that a contextId appeared in a signed message and disallow its reuse.

If verifications are allowed to expire (which is recommended for applications that involve more than a one-time interaction), the user should generate a new contextId when the current one expires and register it with the application (which creates a link in the application to the previously used contextId). The application should remember how many contextIds a user has registered. This can be compared to the counter value returned in the signed message. A counter value that is larger or smaller than expected could indicate a sybil attack and should disqualify the user.

Losing access to an application

A user that loses access to a contextId for an application–exhausting any recovery methods provided by that application–will be left in a situation where they can’t register a new contextId and link it to the previous one.

Restoring access through social recovery

Within an hour of social recovery, a user can ask a node to re-sign any previous blinded message, adding a new ephemeral public key submitted by the user. (This is also blinded to prevent unwanted linkages of contextIds and BrightIDs).

An application should accept any such signed message, and subsequently allow the user delivering it to register a new contextId after proving ownership of the ephemeral key. The new contextId will then be blinded and submitted to a BrightID node to be signed as usual, allowing the user to regain access to the application.

ContextIds must be unique

An application must not register a contextId that has been registered before as this could be used to hijack another user’s account through social recovery.

Avoiding accidental resubmission of a contextId

BrightID nodes can store blinded messages and reject ones they have seen previously to avoid incrementing a counter inappropriately.

Avoiding linkage through timing

Clients can wait a random amount of time to send signed messages to applications to avoid the linkage of BrightIDs to contextIds by node operators that also serve as application administrators.

2 Likes
2

Sponsoring

Sponsoring would use blind signatures in the opposite direction. The user’s client would create a blind message containing their BrightID and present it to an application. The application would sign it (after the user had done the pre-required actions to get sponsored) and submit it to a BrightID node which could open it and record that the user had been sponsored.

3

Super interesting solution. I think following this approach can revolutionize privacy of BrightID.

I think our current solution to store operation hashes to avoid re-submitting operations can prevent this and there is no need to store blinded messages independently.

Waiting for a random amount of time to send signed messages to apps seems not to be proper solution for contexts that do not have lots of links, but I hope we will be able to find solutions for that.

1 Like
4

A cryptographic question that I have is that is not this photographically possible that a node operator that is admin for the app, to iterate over all blinded messages for each contextId and find out which message generated for that specific contextId?
In fact how the blinded message is generated from the original message? Having the original message is not enough to recover which blinded message from a list belongs to that original message?
Looking at this example:


It seems having original message is not enough for generating blinded message and a random number is used by client to create that. But I like to have a confirmation from an expert about this.
5

@mahdi

The reason to store them is so they can be signed (again) right after social recovery so the user can recover an old account (contextId) with an app. The blinded messages are already going to be included in the operation parameters and permanently stored on the blockchain. Since social recovery of an account should be rare, they could be looked up on the blockchain if you’re worried that storing them locally would take up too much space. As far as checking to see whether a contextId has already been used, I think this only works if the user always sends blinded messages to the same node, unless we can use something like Rerandomizable Threshold Blind Signatures. In any case, either the operation hash or the blinded message could be used.

No. Only the client has the ability to blind and unblind.

No. That’s the whole point of blind signatures.

Yes and then the client uses the same random number to unblind the signature and provides the unblinded signature with the original message to the application requesting it.

This is just for the library you linked to which uses RSA. There are probably other implementations.

A few more notes

In this new scheme, linking between contextIds from the same person (which is necessary for sybil resistance) is moved from the BrightID nodes to the applications–where it belongs.

The biggest strength of the new scheme is it removes the requirement for there to be a mapping anywhere of contextIds to BrightIDs. The “context” concept is removed from BrightID nodes completely. A “context” only exists with applications. Applications choose what set of identifiers (contextIds) they find acceptable and whether or how to link them to other applications.

There is no longer a notion of certain nodes serving certain contexts. All nodes would know about all apps and could receive the same information. Apps could still audit various nodes to decide which should be trusted to sign verifications.

The blinded message can only be meant for one node to sign–unless there’s a way to support multiple signers for one blinded message. The other nodes viewing the operation would only increase the counter for the BrightID under the app. I think this also means that for social recovery of a contextId, only the node that originally signed the blinded message could help with recovery. Maybe to have a better chance of success for a future recovery, a user could generate three separate blinded messages and send them to three nodes. Then apps would have to require three signatures for every contextId otherwise the user could link three different contextIds (one for each message) and create a sybil attack that way. There could be other options in the way of Rerandomizable threshold blind signatures.

6

I skipped the step that the blind signature would have to go back to the client to be unblinded and then submitted to the BrightID network. The operation could plainly show the user’s BrightID and wouldn’t have to be encrypted.

Each node could check the signature itself using the known public key for the app that signed it. All nodes could process all sponsorship requests by BrightID; there would be no sponsoring by contextId.

7

The BBS+ Signature Scheme used in Linked Data Proofs and Verifiable Credentials could be useful for this.

8

The public part of the ephemeral key pair needs to be recorded (either publicly or by the application) and not allowed to be reused so that the account can’t be stolen by an attacker who obtains the ephemeral private key.

9

I’ve posted a simpler solution here: Improved privacy, social recovery for apps, no need for contexts