Twitter acquired Threader! Learn more

Sarah Jamie Lewis
+ Your AuthorsArchive @SarahJamieLewis Executive Director @OpenPriv. Cryptography and Privacy Researcher. @cwtch_im icyt7rvdsdci42h6si2ibtwucdmjrlcb2ezkecuagtquiiflbkxf2cqd May. 20, 2021 2 min read

Was playing around with fuzzytags this evening and realized that there were a few performance improvements that could be made when testing a tag.

Which now puts testing a single tag against a 2^-15 detection key @ ~746 μs* (down 9.6%) !

(* on an Intel i7-10700K @ 3.80GHz)

The papers Go implementation clocked in @ 1.311 ms on that benchmark (admittedly on a slightly less powerful computer).

Right now, the rust implementation clocks in @ ~840μs on my computer (~36% faster - Gotta love rust crypto.)

With tonight's hacking, it would be ~43% faster!

The main observation that the hash function H which takes in context, U, x_iU, and W could be split into 2 parts.

Precomputing applying the context, U, and W to the underlying hash, and then individually applying x_iU for each ciphertext element in the tag.

Since that hash function has to be called for every element in the detection key, it saves quite a bit of work to move part of it's computation out of the loop (though slightly sadly means reordering the hash application, which means a version bump)

New code* is here: 

Will likely cut a new version of fuzzytags once I've mulled the changed over a bit more.

(*better link)

Just realized this optimization also applies when generated tags (and perhaps more importantly..should considerably speed up generating entangled tags...)

Running the benchmark now...

Things are going well...

Optimization provides a 12% performance improvement when generating tags! Which now drops it down to ~1.16ms - (a 40% speed increase from original benchmark of 1.927ms)

Entangling benchmarks take a lot longer, but based on a few tests, a complete entangled tag that would validate true for 2 different parties would take ~9minutes (down from ~15minutes).

False entanglements of anything up to 2^-18 take less than a couple of seconds.

Will running longer benchmarks over night to get a better estimate of the fully entangled tag generation time.

Ok...I apparently got a little unlucky with the few tests I ran. First full benchmark completed and it's now down to ~100s on average...need a bit more data, but wow.

A lot of that observed improvement is likely down to the fact that this computer has double the hardware threads of the one I was originally playing with entangled tags on...combined with a 12-20% speed up on tag generation accounts for the rest.

You can follow @SarahJamieLewis.


Tip: mention @threader on a Twitter thread with the keyword “compile” to get a link to it.

Follow Threader