{"id":311,"date":"2008-09-19T15:40:38","date_gmt":"2008-09-19T13:40:38","guid":{"rendered":"http:\/\/www.lucas-nussbaum.net\/blog\/?p=311"},"modified":"2008-09-19T16:51:23","modified_gmt":"2008-09-19T14:51:23","slug":"looking-for-cliques-in-the-gpg-signatures-graph","status":"publish","type":"post","link":"https:\/\/www.lucas-nussbaum.net\/blog\/?p=311","title":{"rendered":"Looking for cliques in the GPG signatures graph"},"content":{"rendered":"<p>The strongly connected set of the GPG keys graph contains a bit more than 40000 keys now (yes, that&#8217;s a lot of geeks!). I wondered what was the biggest clique (complete subgraph) in that graph, and also of course the biggest clique I was in.<\/p>\n<p>It&#8217;s easy to grab the whole web of trust <a href=\"http:\/\/www.lysator.liu.se\/~jc\/wotsap\/\">there<\/a>. Finding the maximum clique in a graph is NP-complete, but there are algorithms that work quite well for small instances (and you don&#8217;t need to consider all 40000 keys: to be in a clique of <i>n<\/i> keys, a key must have at least <i>n-1<\/i> signatures, so it&#8217;s easy to simplify the graph &#8212; if you find a clique with 20 keys, you can remove all keys that have less than 19 signatures).<\/p>\n<p>My first googling result pointed to <a href=\"http:\/\/www.geocities.com\/dharwadker\/clique\/\">Ashay Dharwadker&#8217;s solver implementation<\/a> (which also proves P=NP ;). Googling further allowed me to find the <a href=\"ftp:\/\/dimacs.rutgers.edu\/pub\/challenge\/graph\/solvers\/dfmax.c\">solver provided with the DIMACS benchmarks<\/a>. It&#8217;s clearly not the state of the art, but it was enough in my case (allowed to find the result almost immediately).<\/p>\n<p>The biggest clique contains 47 keys. However, it looks like someone had fun, and injected a lot of bogus keys in the keyring. <a href=\"http:\/\/blop.info\/pub\/47-clique.txt\">See the clique<\/a>. So I ignored those keys, and re-ran the solver. And guess what&#8217;s the size of the biggest &#8220;real&#8221; clique? Yes. 42. Here are the winners:<\/p>\n<pre>CF3401A9 Elmar Hoffmann \r\nAF260AB1 Florian Zumbiehl \r\n454C864C Moritz Lapp \r\nE6AB2957 Tilman Koschnick \r\nA0ED982D Christian Brueffer \r\n5A35FD42 Christoph Ulrich Scholler \r\n514B3E7C Florian Ernst \r\nAB0CB8C0 Frank Mohr \r\n797EBFAB Enrico Zini \r\nA521F8B5 Manuel Zeise \r\n57E19B02 Thomas Glanzmann \r\n3096372C Michael Fladerer \r\nE63CD6D6 Daniel Hess \r\nA244C858 Torsten Marek \r\n82FB4EAD Timo Weing\u00c3\u00a4rtner\r\n1EEF26F4 Christoph Ulrich Scholler \r\nAAE6022E Karlheinz Geyer \r\nEA2D2C41 Mattia Dongili \r\nFCC5040F Stephan Beyer \r\n6B79D401 Giunchedi Filippo \r\n74B11360 Frank Mohr \r\n94C09C7F Peter Palfrader\r\n2274C4DA Andreas Priesz \r\n3B443922 Mathias Rachor \r\nC54BD798 Helmut Grohne \r\n9DE1EEB1 Marc Brockschmidt \r\n41CF0322 Christoph Reeg \r\n218D18D7 Robert Schiele \r\n0DCB0431 Daniel Hess \r\nB84EF12A Mathias Rachor \r\nFD6A8D9D Andreas Madsack \r\n67007C30 Bernd Paysan \r\n9978AF86 Christoph Probst \r\nBD8B050D Roland Rosenfeld \r\nE3DB4EA7 Christian Barth \r\nE263FCD4 Kurt Gramlich \r\n0E6D09CE Mathias Rachor \r\n2A623F72 Christoph Probst \r\nE05C21AF Sebastian Inacker \r\n5D64F870 Martin Zobel-Helas \r\n248AEB73 Rene Engelhard \r\n9C67CD96 Torsten Veller<\/pre>\n<p>It&#8217;s likely that this happened thanks to a very successful key signing party somewhere in germany (looking at the email addresses). <strong>[Update: It was the LinuxTag 2005 KSP.]<\/strong> It might be a nice challenge to beat that clique during next Debconf ;)<\/p>\n<p>And the biggest clique I&#8217;m in contains 23 keys. Not too bad.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The strongly connected set of the GPG keys graph contains a bit more than 40000 keys now (yes, that&#8217;s a lot of geeks!). I wondered what was the biggest clique (complete subgraph) in that graph, and also of course the biggest clique I was in. It&#8217;s easy to grab the whole web of trust there. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"0","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,13,14,12],"tags":[],"class_list":["post-311","post","type-post","status-publish","format-standard","hentry","category-jabber","category-planetdebian","category-planetgnomefr","category-planetubuntu"],"_links":{"self":[{"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=311"}],"version-history":[{"count":0,"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/311\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lucas-nussbaum.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}