Add support for a post-quantum signature algorithm

[ethanfrey]

Maybe something like http://tbuktu.github.io/ntru/?

[rigelrozanski]

cool we can maybe use Cgo on their C implementation https://github.com/tbuktu/libntru or just port - looks like an active project

[adrianbrink]

We should also look at these guys since it is an active project and they have many choices.

https://github.com/open-quantum-safe/liboqs

[jaekwon]

See what these guys found: https://theqrl.org/roadmap.html . Their coin, QRL, is trading on the market.

I don't think it would be hard to make Tendermint quantum proof. As long as we can find a deterministic quantum proof signature scheme, which are probably cited from theqrl.org's whitepaper.

bounty

[mattdf]

If you're going to use NTRU for signatures, be mindful of the key recovery attacks: http://homepages.cwi.nl/~ducas/NTRUSign_Cryptanalysis/DucasNguyen_Learning.pdf

Also, NTRU is still relatively patent encumbered, depending on the codebase/features you use, not sure if the dynamic perturbations are under patent or not.

QRL just uses XMSS: https://eprint.iacr.org/2011/484.pdf

Maybe you can have some fun and implement signatures over supersingular isogeny elliptic curves or implement McEliece signatures?

The simplest options with the lowest-risk crypto are probably either XMSS or Lamport Signatures + hash trees.

Also, liboqs seems to mostly be about key exchange algorithms, extending those to signatures is nontrivial. Regarding signatures, as far as existing codebases go QRL's demo XMSS implementation is probably the closest you'll get.

[jaekwon]

Related: https://twitter.com/jaekwon/status/877228321121083392

[ethanfrey]

Hey @mattdf are you working on this? That's awesome.

I have minimal knowledge of the practical differences of these experimental algorithms. If it is not used by ssh or bitcoin, ethereum, I probably have not looked at it.

All I would ask is that whatever algorithm implement the go-crypto interfaces:

PrivKey, PubKey, and Signature. They abstract away the creating and verification steps. If one can expose and algorithm with those interfaces, then it becomes super easy to drop it into tendermint and basecoin.

[odeke-em]

I recently started working on a Haraka v2 https://eprint.iacr.org/2016/098.pdf port to Go, where the reference implementation in the paper is at https://github.com/kste/haraka, we might be releasing it soon. Its effectiveness is for hashing short inputs i.e 32 and 64 byte inputs. However, the adoption/popularity of the algorithm amongst other cryptocurrency and blockchain systems will determine which algo to pick. And yes @ethanfrey, great suggestion to stick to implementing PrivKey, PubKey and Signature :)

[MikeSofaer]

The solution to quantum computer attacks, should one ever be needed, is a bit of a stretch goal for Cosmos, I think. There's a lot to focus on first :)

[ebuchman]

Closing this for now . We can revisit maybe later this year ...