1

Background

A registration process to acquire an anonymous, verified account goes like this:

  • Registrant provides proof of individuality to a Registrar.
  • Registrar verifies proof, ensures no prior registration, and directs Registrant to a Teller.
  • Teller provides Registrant with anonymous account credentials.

At this point, the Registrant has an account, and only one account. The Registrant hereinafter is a Registered User (simply, User).

Problem

A User can lose (accidentally, or deliberately) their anonymous credentials.

Question

How can:

  • the anonymity of a User's account remain cryptographically secure (even to third-parties who have complete database and source code access), such that discovering either the anonymous account or the registration credentials will not reveal that they belong to the same individual;
  • registration of duplicate accounts be prevented; and
  • a User retrieve their lost (or misplaced) account credentials, and only theirs?

I thought homomorphic encryption might be useful here, but I've read it is currently too computationally intensive.

Related

Related questions:

(If this would be better suited for Crypto SE, please migrate it.)

Community
  • 1
Dave Jarvis
  • 269
  • 1
  • 11
  • How is it possible to proof individuality without also compromising anonymity? You would need some kind of information which every person in the world only has once, which can not be forged and which is also not linked in any way to their identity. I couldn't think of anything like that. – Philipp Feb 26 '15 at 21:12
  • What is the difference between "authorization credentials" and "the registration credentials"? –  Feb 26 '15 at 21:25
  • The *Registrar* knows the individual. The *Teller* doesn't. Imagine a real-world scenario where you walk into an office, hand over your credentials, then are directed into another room. The *Teller* is a machine in that room and has one job: print out unique authentication papers upon request. Once the *Registrar* verifies you, the *Registrar* signals the *Teller*. – Dave Jarvis Feb 26 '15 at 21:25
  • @DaveJarvis OK, so the registrar knows the users identity. Then why can't the registrar order the teller to give the user the same credentials they gave to them before? They will have to give some kind of identification token to teller and user anyway so the registrants can proof to the teller that they were authorized by the registrar. – Philipp Feb 26 '15 at 21:30
  • @Philipp: The *Registrar* doesn't have to prove to the *Teller* that the *User* is authorized. The *User* is not allowed into the room with the *Teller* until after authorization is granted. If the *User* walks into the room, it is safe to assume they are allowed to be there (to obtain their anonymous credentials). – Dave Jarvis Feb 26 '15 at 21:36
  • @DaveJarvis Wait... so you are talking about a physical system, not an electronic system? – Philipp Feb 26 '15 at 21:40
  • @Philipp: Yes, for now. How they get their anonymous credentials is a bit beside the point. The problem is that once they have anonymous credentials, is there a way for that individual to retrieve their anon creds in the event that their anon creds are lost. And can this be accomplished while retaining anonymity? – Dave Jarvis Feb 26 '15 at 21:48
  • Should "or the" be replaced with "and the"? If no, how do you make sense of "they belong to the same individual"? –  Feb 26 '15 at 21:51

1 Answers1

2
  1. The registrar verifies the identity of the user (in a comment you said that the user is not anonymous towards the registrar). Identification means that each user has some kind of unique identifier. That could be their social security number, their real name + birthday + birthplace or something like that. The registrar uses a cryptographically secure hash function to create a hash from that identifier + a secret pepper only known to the registrar.
  2. The registrar signs the hash with its private key to proof that they generated that hash. Then they give the hash + signature to the user
  3. The user presents hash + signature to the teller. The teller checks that the signature is valid using the registrars public key. Then they use the hash plus another secret pepper only known to the teller as input to create another cryptographically secure hash and then derive the users credentials from that hash.

Retrieving lost credentials

Should the user lose their credentials, they repeat the procedure. Their personal information won't have changed, so the hash by the registrar will be the same as before which means the credentials generated by the teller based on the hash will also be the same.

Possible attack vectors

The largest possible attack vector on this system would be a malicious registrar. When the registrar is evil, they could generate an infinite number of bogus hashes and present them to the teller to generate an infinite number of anonymous identities. Or they could give them the hash of a known identity to obtain the credentials of that user. When the teller knows the registrar, the registrar could still do this by conspiring with another person unknown to the teller and use that person as a proxy. However, you already trust the registrar to identify your users personally, so you must place a very large amount of trust in them anyway.

The abuse potential could be reduced (but not completely removed) by having multiple registrars and require a signature from multiple ones. That way multiple registrars need to conspire to break the system.

Philipp
  • 49,017
  • 8
  • 127
  • 158
  • How would this prevent third-parties, who have access to the database, from generating hashes (e.g., massive rainbow tables) to figure out the credentials? – Dave Jarvis Feb 26 '15 at 23:06