Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose there are 3 persons, Alice, Bob and Peter.

They are identified by their pseudonyms (public RSA keys).

Alice has a key Alice, Bob has Bob-Work and Bob-Friends. Peter has Peter.

Peter knows Alice. Alice expresses trust to Bob-Work.

Peter knows Bob-Friends.

The question is, How can Bob-Friends prove to Peter, that Bob-Work he's being trusted by Alice (and therefore Bob-Friends too), without revealing that Bob-Work and Bob-Friends belong to the same person, and/or plausibly deny such a fact?

  • NOTE: We do not discuss timing attacks here (such as "Please express trust to THAT pseudonym and I'll see who will appear as trusted to me afterwards")

  • I have a possible solution involving a "credit system", where participants emit "trust tokens" which can then be transferred by their recipients. But, this has a downside of having to support a LONG credit transfer history. Is there a solution that does not need it?

P.S. Please retag this question appropriately (reputation, trust etc) - I can't create new tags yet :)

share|improve this question
The goal is not really clear - what exactly does Bob want to prove to Peter? That Bob-Friends is (somehow) trusted by Alice? – Paŭlo Ebermann Feb 5 '12 at 21:34
Yes. Not necessary by Alice, "by someone who Peter knows" would be enough. – wizzard0 Feb 5 '12 at 23:03
Probably doable as a proof of equality of two logarithms, if expressed/implemented with credentials systems from the book: Stefan Brands, "Rethinking PKI", see pdfs on – Vadym Fedyukovych Nov 18 '15 at 13:21
up vote 10 down vote accepted

You are probably looking for what is called "anonymous credentials".

An anonymous credentials system relates three types of parties: authorities, users, and verifiers. An authority (Alice) can issue a credential to a user (Bob), that certifies that the user satisfies some property (in your case, that would be "is trusted"). Credentials are unforgeable. Then, that user (Bob) can prove to a verifier (Peter) that it possesses the credential, without revealing anything about himself other than the possession of the credential (anonymity), even if the verifier colludes with other verifiers and/or the authority.

The way anonymous credentials systems are typically implemented is that a user has a single private key sk, and multiple corresponding public keys pk, pk', etc. (pseudonyms) that can be generated on the fly as randomized commitments on sk. Then, the credential issuing protocol is a special kind of signature scheme that produces a signature on the value inside the commitment; in that way, Bob can obtain a credential from Alice via his pseudonym Bob-Work, and prove possession of it under his pseudonym Bob-Friends, in such a way that the two pseudonyms cannot be linked to each other.

A good general introduction to anonymous credentials is Anna Lysanskaya's Ph.D. thesis, especially chapter 3.

Since 2002, there has been quite a bit of research and progress on anonymous credentials, so we have efficient instantiations supporting additional features like revocation or delegation.

share|improve this answer
Reading... Seems that this is it) – wizzard0 Feb 6 '12 at 16:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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