3

If it is known that existing digital signature schemes like elliptic curve crypto or RSA are vulnerable to quantum computers, why haven't we already switched to Lamport signatures or something like that? Is there something that prevents people from deploying this type of signature right now?

I understand that we still believe/know that nobody has a good working quantum computer yet but why not make the switch anyway?

  • This quantum computing thing is overhyped by bloggers and YouTubers. Let these quantum computer come and prove that they really can break presently used cryptographic algorithms. Once it is proven in an experiment or a research, a new standard will arrive. – defalt Dec 22 '17 at 17:16
  • Because there are no safe candidates, The one already presented are either broken or have low performance,. – Aria Dec 22 '17 at 18:20
  • 3
    See cdc.informatik.tu-darmstadt.de/fileadmin/user_upload/Group_CDC/… slides 13 and following about the efficiency problems (key size, signature size, computational efforts..) – Steffen Ullrich Dec 22 '17 at 18:30
4

If it is known that existing digital signature schemes like elliptic curve crypto or RSA are vulnerable to quantum computers, why haven't we already switched to Lamport signatures or something like that?

Quantum computers were not a realistic threat when these algorithms became standardized and widely deployed. As indicated in the comments by @Steffen Ullrich, hash-based signatures carry some disadvantages. The size of the public/private keys and the size of the signatures can be a non-negligible downside if quantum computers aren't relevant.

Additionally, some hash-based signature schemes are stateful. Stateless schemes carry a big advantage over stateful schemes in regards to implementation simplicity.

Is there something that prevents people from deploying this type of signature right now?

I understand that we still believe/know that nobody has a good working quantum computer yet but why not make the switch anyway?

For a cryptographic algorithm to be adopted for use in the real world, it needs to be standardized.

Hash-based signature have been submitted to NISTs call for post-quantum algorithms.. It is entirely possible that hash-based signatures will become standardized and recommended for use - assuming that they survive the analysis. The deadline for submissions was just closed (November 30, 2017) and it will probably be a few years before anything is standardized.

2

This summer I attended a nice summer school about real-world cryptography and privacy. The days and presentations were passing and we saw some magnificent pieces of research. Newer, faster and more secure algorithms were presented by many PhD's and researchers. So, at some point, I just asked the same question: "Why do we still use 3DES instead of these to encrypt credit card transactions??". The answer I received and give you is this: you don't want to risk changing something that is tested, compatible with many other technologies and it's proven to work. Imagine a bank using such a new technology...

  1. They have to hire people who know how to implement this new algorithm to encrypt data - and pay them of course.

  2. Reprocess all their old data to be compatible with the latest technology they want to implement(already a pain in the ass, since they will already be somehow hashed, so you add a step, you don't replace it)

  3. Every other service sharing or getting information from you must also be compatible with your new technology (banks have dmz's for clients or governal services)

Will they be more secure? PROBABLY.

Will they be fully functional and operative? DEFINITELY NOT.

That's what they told me and you know what? I was in the akward position as a security researcher to tell them "ohh, uhhmm you are right..."

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.