[clug] request for comment: new keysigning protocol

Nemo Maelstrom Thorx clug at nemo.house.cx
Thu Feb 4 18:37:17 MST 2010

On Fri, Feb 05, 2010 at 06:16:41AM +1100, Paul Wayper did utter:
> > 
> > http://woozle.org/~neale/papers/tank-tread.html
> > 
> The problems with the tank tread method are that it requires a fair bit of
> space, puts pressure on the participants to tick things off and not hold the
> line up, a person can give different responses to different people (so the key
> that Eve gave me is not the same as the one she gave you, but we both sign it
> as if that's her correct key), and a few others that I can't think of off the
> top of my head.  Don't underestimate the possibilities for the organisers to
> throw something screwy in as well.
> Hope this helps,

I'll pass that back and give it some thinks, but I have to argue the
'fair bit of space'. Which isn't to say that it's not space consuming
- it clearly is. 

But it's *more* space efficient - and time efficient - than the 'folded
line' method as mentioned in both ad hoc, and Sassaman-Efficient. To
quote http://keysigning.org/methods/sassaman-efficient
 > everyone forms a long line in the same order as their keys appear in the
 > list. The head of the line then folds back on itself and the
 > participants moving back along the line inspect the ID of each
 > participant standing still.

This requires a line n participants long, which folds to become two n/2
lines in parallel, and then reduces down to 2 final participants. It's
a O(2n) process. 

Tanktread is a O(n) process. Everyone signs a key on every step (there
being no end-of-line which has to wait for the start of the line to
reach), and everyone finishes at the same time. 

The 'not holding the line up' is a valid concern - but how does this not
equally apply to the folded line method?

  ------------------------------------------ --------------------------
                                                    earth native

More information about the linux mailing list