Post-quantum cryptography inquiry

[tucnak]

Hello,

Thank you for this fantastic library! I very much enjoyed toying with the available primitives, thinking of applications. The taxi case on its own is an inspiration.

Now, post-quantum cryptography. I believe there's great value in discussing if and if yes, then how—this library is going to adopt PQ cryptography and all the baggage that comes along with it. Granted I understand the big picture of how this package works, it seems to me that most of the higher-level stuff will be incompatible with future PQ primitives, whatever they may be. (NIST doesn't rush it, and they are probably right not to.)

There is no doubt that everyone who will come across this thread would be thrilled to hear what the cryptographers involved in the project would have to say about PQ.

I myself need to build an open decentralised identity database, and unfortunately, as always it's a timely matter. I would love to use Ed25519 for it straight away, but I fear that in 5 years time, the network of identities could be unraveled, which would be a catastrophe, defying the very purpose of the project.

With all due respect, Ian

[ineiti]

There is another project from the LDS lab that will probably be used for future projects at DEDIS:

https://github.com/ldsec/lattigo

This one is based on lattice-based crypto, which are supposed to be quantum-resistent. DEDIS itself is thinking about making a hash-based quantum-resistent library. But I don't think that this will be compatible with the dedis/kyber/Group interface.

Nitpicking on "post-quantum cryptography": I have to point out that it doesn't really mean anything. The term "quantum-resistent" is much clearer.

[tucnak]

Hello Linus!

Thank you for you answer, and your time.

It's funny, because lattigo is the one library with the taxi example, I was confused in the OP, apparently. Crazy how nobody knows anything (locations) yet they still can make it happen (locate the closest driver)... This sounds like technology that HAS to be commodified to the point it's everywhere, but to be honest, I'm struggling to bring up cases for it.

It's sad that the Group interface would have to go, when PQ comes along. Do you see how it can be re-rewritten? To be completely honest with you, DEDIS is much-much more well-documented and clearer to understand. Maybe it's because lattices are much more complicated on their own, I have no idea because I first of all, don't really understand lattices. DEDIS makes sense and I can see how it can easily be integrated into any other system, I just don't see lattigo doing this...

Do you think the new hash-based PQ-resistent library, which is going to be capable of signatures, I presume, could be used to re-wire the higher-level primitives, such that Group brings? And last, but not least, how exactly would you define "quantum resistant", i.e. what would be the criteria for it?

P.S. Sorry for bombarding you with questions like that. I'm just incredibly impressed with DEDIS, and I want to have a clearer understanding of the long-term game.

[ineiti]

No problem - thanks for the questions. Some more nomenclature: DEDIS is the lab, kyber is the library. So I guess you want to write that you're impressed by the documentation of the kyber library, not the lab. Anyway, thank you very much!

Perhaps you could to fit lattigo into the group interface, but it would be very sub-optimal because lattice-based crypto can put more than one value in a vector, operate on all these values simultaneously, have better homomorphic properties, but needs some care-taking now and then. I'll let the lattigo-people know that they should do some more documentation ;)

The hash-based crypto library is currently only an idea. As far as I understand it, the main problem with hash-based crypto libraries is the handling of the state of your private key: every private key can only be used once (to encrypt or to sign), and has to be derived from a 'master' private key. So probably not possible to put into a Group interface, neither.

With regard to the definition of quantum-resistant cryptographic algorithms, you're better off asking google/wikipedia/crypto.se than me ;) But, in short, when trying to break a quantum resistant cryptographic algorithm, qubits don't give you an advantage over classical processors. Which is true for hash-based encryption, symmetric encryption, but not public-key cryptography (RSA, ed25519, p256, ...)

It seems that you need about 20 million noisy qubits to crack ed25519. Google actually has 56. If you double that every year (which I highly doubt), in about 20 years you could be there. But the problems quantum computing face look much worse than silicon-problems to me. But all I have is 40 years of computer history ;)

Anyway, for more discussion you would need to move to https://crypto.stackexchange.com/ - I'm closing this issue.