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.)

  • 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"? – user49075 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
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.

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.