Thread by @SarahJamieLewis

After all the performance tweaks I did yesterday, I remembered today that dalek crypto has avx2 support...

Generating a tag: 689.34μs
Testing a tag: 424.31μs

https://twitter.com/SarahJamieLewis/status/1395258540764241922

With previous improvements + avx2 finding a fully entangled tag (one that will match for 2 different tagging/verification keys) now takes ~79 seconds on a consumer desktop.

That's much less than my original estimates of ~15 minutes prior to any of these optimizations - and pushes entangled tags from a curiosity into something that is potentially practical.

One potential application is as acknowledgements of honest mixing in niwl (

https://twitter.com/SarahJamieLewis/status/1394799147199262722

)

Alice could tag a message to both Bob *and* herself. Alice can then tell if a mixer and the untrusted server is honestly carrying forward her message if she receives it back.

The mixer is never in possession of the detection key and so gains no information from this process.

The routing server will observe a message for some % of participants (including Alice *and* Bob) - which could be true of *any* arbitrary message.

Encoding acks within messages themselves doesn't prove that Bob received the message, but it does show the mixer(s) decrypted and routed the messages honestly, and that the untrusted server honestly presented a message potentially for Alice, to Alice.

It's still much more expensive to generate a fully entangled tag (79s) v.s. a regular tag (>1ms) - so Alice might not want to do it for every message, but if enough parties do it at random it provides a strong check on the honesty of the whole system.