I am aiming to find out if this problem/puzzle can be solved with cryptography at all. Say there are these two parties:

  • Subject S which has a master private/public key pair (MPriv, MPub) and a set of key pairs derived from MPriv. Each of the derived pairs has its own public ID, and the private keys are merely the concatenation of MPriv and the ID (this appears to be achievable);
  • Trusted party T which issues proofs/certificates to subjects like S. These proofs are linked to the subjects' public keys and are used to demonstrate to the whole world that whoever has the corresponding private key is such-and-such-and-such (which T would have verified by appropriate means before issuing the proof; let's call this proof content).

So, say S has obtained a proof from T for one of his public keys (either MPub or one of the derived ones). Is there a way for S to "relay" the proof to another derived key from the same set? That said, could S, without going to T again, somehow use the proof he has already got to derive a proof of the same content for another key in the same set? From the point of view of the public, the original proof and the derived proof would appear unrelated — apart from that they have the same content and are issued by T.

  • $\begingroup$ The normal way of doing this kind of thing is a certificate chain. Imagine that T has signed $MPub$. Then what S does for a new keypair $(sk, pk)$ is signs $pk$ with $MPriv$ and hands both signatures to whoever will verify them. The verifier sees that $MPub$ is signed by T, so they trust that it belongs to S and they also see that $pk$ is signed by the owner of $MPub$ so they can infer that this belongs to S too. $\endgroup$
    – user2552
    May 9 '18 at 20:42
  • $\begingroup$ @Bristol the crux of the puzzle is that the verifier must not learn that MPub and pk belong to the same owner. This is the whole point of creating derived keys/identities. $\endgroup$
    – Greendrake
    May 10 '18 at 0:02
  • 1
    $\begingroup$ In that case I think what you want is some form of Direct Anonymous Attestation (DAA). The basic idea is that T issues a blind signature on $MPub$ and S proves in zero-knowledge that they know a keypair on which there is a signature from T. (DAA also comes with an optional linkability property, but you can ignore that by only using the variant where the "basename" is random.) You might also want to look at the FIDO protocol as they do something similar. $\endgroup$
    – user2552
    May 10 '18 at 6:22
  • $\begingroup$ @Bristol Thank you, that paper looks interesting. I would be willing to pay someone for looking into this question more deeply, and, if the puzzle is found solvable, for producing a proof of concept according to spec I would provide. If you or anyone you recommend would be interested could I please be reached out at eugene[at]greendrake.info. $\endgroup$
    – Greendrake
    May 10 '18 at 11:47

Your Answer

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

Browse other questions tagged or ask your own question.