Protecting Authenticity of Documents against Breaking of Encryption Scheme by Quantum Computing

IonQ published a blueprint for breaking 256-bit elliptic curve signatures used in blockchain technology including Bitcoin (press release). Unlike prior work, they "compiled every operation down to the actual error-correction primitives our architecture runs. Today's paper proved - rather than assumed - a lower bound on the probability that the full computation succeeds." They estimated that solution of 256-bit ECDLP (elliptic curve discrete logarithm problem, the classically intractable mathematical problem underlying elliptic curve cryptography) on secp256k1 (parameters specifying a specific elliptic curve on which mathematical operations are done) takes 25.7 days per attempt, by using 19397 quantum bits (qubits) implementing 1457 logical qubits and 39 million Toffoli gates (means operating on qubits). (Use of quantum states necessitates complicated error correction schemes, which inflates the number of physical qubits required to implement logical qubits.)

I was reminded of an issue of potentially compromising authenticity of documents by their remark, "The cryptographic exposure this work describes relates to authentication and integrity rather than to confidentiality."

The threat to confidentiality is already quietly underway through a strategy known as "Harvest Now, Decrypt Later" (my blogpost). On the other hand, breaking of the signature scheme does not allow tampering with a document already signed with the scheme. Instead, it allows an attacker to derive a private key from a public key, which means that the attacker can put an authentic digital signature to a forged document. Suppose there is a digitally signed document stating "The President is very unpopular." Even with the knowledge of the private signature key, the attacker cannot falsify it to read "The President is very popular." Instead, however, it will be possible to create a new document stating "The President is very popular." and put a digital sign to authenticate it.

The same applies for digital timestamping because digital timestamping works by putting a digital signature to a combination of a hash of a document and a timestamp by a trusted timestamping authority to prove that the document was present at the time indicated by the timestamp. If the signature scheme is broken as of 2030, the attacker can create a document stating "The President is very popular." and add to it a valid timestamp of 2026.

Experts are aware of the issue and one (cenceptually) simple solution is timestamp renewal, whereby a document with a timestamp as a whole is wrapped in another layer of digital timestamping with a new (e.g., quantum-resistant) signature scheme. But this renewal need to be done before the original signature scheme is broken.