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.

  • $\begingroup$ Allow me a question of ignorance: Given 3 persons A, B and C. If both A and C are best friends of B and A and C are yet foreign to each other, i.e. not even (poor) friends, and everyone would only share secret knowledges with his best friends, how is it principally feasible to prevent secrets of A being leaked to C and vice versa? $\endgroup$ – Mok-Kong Shen Feb 12 '17 at 10:29
  • $\begingroup$ The participants would know about the network structure before sharing messages. The idea would be to allow messages to be sent to a network wider than your immediate friends, but still with a high level of trust. If I really trust my best friend, then I also trust that his friends are also somewhat trustworthy, and so on. So, the messages would not be super secretive. Besides, if B and C are really good friends, there's nothing stopping B from sharing my secret in plaintext to C (e.g. face-to-face). $\endgroup$ – maackle Feb 12 '17 at 20:55
  • $\begingroup$ If I don't err, your last sentence indicates that restricting transfer of Information to distance 1 wouldn't work in practice. But wouldn't an analogous case for distance 2 similarly fail? (A trust B's distance 1 friend C, B trust C's distance 1 friend D, wouldn't A's secret be leaked to D who is at distance 3 from him?) $\endgroup$ – Mok-Kong Shen Feb 13 '17 at 15:15
  • $\begingroup$ If C wants to share a secret with someone who's not meant to read it, outside of the encryption scheme, that just means that C is not a very trustworthy friend. Maybe B shouldn't have trusted him so much :) $\endgroup$ – maackle Feb 13 '17 at 18:31
  • $\begingroup$ But trust is in practice unfortunately not an extremely exact, objectively determinable, quantity comparable to e.g. those in mathmatics. So your last sentence would in fact give support to the question I raised IMHO. $\endgroup$ – Mok-Kong Shen Feb 14 '17 at 15:56

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.


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.