[Cryptography] graph theory and sybil attack

[Jerry Leichter]

>> ...Finding cliques is NP-complete.  This very strongly suggests that the problem you suggest is as well.
> 
> Most NP complete problems have approximate or near optimal solutions that are merely polynomial...
However, some NP-complete problems are not approximable - a celebrated result a number of years back.  Unfortunately, the clique problem is one of them.  (http://www.cs.umd.edu/~srin/PS/clique-jou.ps <http://www.cs.umd.edu/~srin/PS/clique-jou.ps> has a discussion if you really want to get into the details).

>> There are going to be a lot of naturally-occurring, legitimate (closed) groups of nodes in a network of buyers....
> 
> Legitimate fans are likely to be fans of other musicians as well, and likely to have genuine interactions with fans of other musicians.
Only experiment will determine if this is really true, and to what degree - but my guess is you'll have plenty of false positives.  In the end this will be a ROC problem - you have to trade off among sensitivity, specificity, and so on.  Since we're talking about an active opponent here, not random noise ... expect this to be very hard.
                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20190711/90ad8296/attachment.htm>