[messaging] Transparency for a key directory without publishing usernames

[Joseph Bonneau]

On Thu, Oct 9, 2014 at 12:16 AM, Trevor Perrin <trevp at trevp.net> wrote:

>
> By consistency for STHs I just meant check that a newer STH is chained
> from an older one (which might require requesting the intervening STHs
> from the server).
>

Yes of course. Sorry, I wasn't clear but I was also assuming you chain the
STH/Merkle Roots together for this reason. I just wasn't imagining you do
any consistency check otherwise.


> That's not strictly necessary, if you assume that each epoch everyone
> relying on a key will be connected to the parties monitoring that key
> through gossip.
>
> But if you check consistency for STHs, then if an attacker signs
> different STHs for the same epoch they have to do this for all future
> epochs, so gossip has a better chance of eventually detecting this.
>
>
> > Users can request proofs on demand that their desired key material is
> > correctly included every day at the hash of their username. Your software
> > can automate this. Each proof would be 1 signature plus 256*256 bits of
> > Merkle proof
>
> I think it's log(# of users) * 256 bits, since the lower part of the
> Merkle path / proof is constant.  So hopefully < 1 KB.


Yes.


> Leaking information about non-queried usernames is a concern.  A
> Merkle path would reveal if there are usernames that exist with a hash
> that shares a prefix of bits with you.  Maybe you could live with
> that
>

Can definitely live with that. Learning that some random person exists who
shares 30 bits of a 256-bit hash with you is essentially useless, right?

The sparse tree requires calculating 256 hashes to verify a Merkle
> path, but most of them just chain the previous value with a constant.
> Not a big deal, but seems like that could be optimized by just storing
> each entry at a leaf determined by its minimum unique prefix?


Yes, you could speed up verification a little by caching all of these. Very
minor savings though.


> Yeah, not sold on that.  You might want to give the log a chance to
> explain itself.  The Sword of Damocles is always there anyways, we can
> just stoping trusting the service.
>
> You also want whoever detects the inconsistency to be incentivized to
> publicize it, instead of keeping the (valuable!) private key for
> themselves.
>

That's a good point. Tagged one-time signatures are probably more
theoretically interesting than practical the more I think about them.

As an alternate idea, I wonder if there's a way to use the same techniques
so that if anything is ever signed twice, instead of the server's private
key you learn the private key to some fidelity bond of Bitcoins. So if
you're a startup, you can put a nice bug bounty there, and if you ever
double-sign in an epoch whoever finds it gets to seize the bond and maybe
you could rig this so that doing this revealed the proof that this happened.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141009/37d34efe/attachment.html>