Yes I think a DHT would be a good solution. I'd prefer an existing DHT implementation since they can be somewhat complex, and not a new DHT-like social graph.  The key would be the person's pubkey (or even a hash of that to make it smaller and make it work with an existing DHT implementation).

I haven't done any work on this.