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?

user1936752
  • 143
  • 3
  • 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 https://www.cdc.informatik.tu-darmstadt.de/fileadmin/user_upload/Group_CDC/Documents/Lehre/SS16/PQC/hash2.pdf slides 13 and following about the efficiency problems (key size, signature size, computational efforts..) – Steffen Ullrich Dec 22 '17 at 18:30
  • @defalt I know its been a few years, but its my understanding that RSA can be broken if large integers can be factored. The D-Wave quantum computers, even though not general purpose, are able to factor N bit integers using N^2 quantum bits. So if they can get to the 1~10M quantum bit range they can break existing RSA keys. They are currently at 2048 bits and scaling at a More's Law like pace. As long as there are no unforeseen problems with scaling up, there is a reasonable chance they might be there in 10 years or so. – user4574 Nov 18 '21 at 02:09

2 Answers2

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.

Community
  • 1
Ella Rose
  • 293
  • 2
  • 10
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..."

Chris Tsiakoulas
  • 1,777
  • 1
  • 11
  • 9