Is there an asymmetric scheme where keys form a graph and a message can only be decrypted across a certain degree of separation?

Question

Consider a network of trust, where each user u specifies some other set of users whom u "trusts". This forms a graph with users as nodes and declarations of trust as directed edges.

Each user may push encrypted data out to the network along with a maximum "degree of decryption", e.g. if the degree is 2, only direct friends (degree 1) and friends of friends (degree 2) should be able to decrypt the message.

Ideally this restriction could be implemented in the encryption scheme itself. The scheme would have the following properties:

1. Ability to encrypt a message M = c || d
   • where c is the message content and d is the max degree
2. The ability to generate a new key from another private key which can still decipher M (this corresponds to an edge on the graph of trust)
3. A generated key can only decipher M if it is less than d levels of derivation away from the original key used to create M
4. No key can be easily derived from a generated key

To spell it out more plainly, when user A trusts user B, A derives a new key from her private key and shares it with B, so B can now decrypt her messages of d >= 1. B does the same and generates a new key from A's shared key, which B shares with C. Now C can read messages from A of degree d >= 2. And so on. (Actually, when B decides he trusts C, he would pass on to C generated keys for every person B trusts.)

I'm wondering if anything like this exists, or if anyone can point me in that direction, or can provide intuitions as to whether this is even feasible. I am new to cryptography and can't even tell whether this is likely to be already done, doable, or impossible.

Answer 1

This looks like a new research to be done. I believe this is doable starting from graph characteristic polynomial as introduced at iacr 2008/363 and CECC 2009 (shameless). "Trusted" relationship would mean knowing secrets associated with neighbor nodes. Having secrets of trusted network of neighbors, sender would produce characteristic polynomial such that any trusted node can divide, that is, produce zero remainder polynomial. There might be a variant of ElGamal encryption designed from probabilistic test (Schwartz-Zippel) for zero remainder condition, which would likely complete this design. Considering (verifying) characteristic polynomials over a ring modulo random linear polynomial (no such ring at 363 preprint yet) might be a practical solution. Welcome.