Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path

From: Ian Quantum <[email-masked]>
Date: Wed, 1 Jan 2025 16:43:46 -0800 (PST)

FALCON failed the NIST vetting. Since 2022 they have said they will fix it 
next year. Same answer in 2024 when they formalized CRYSTALS-Dilithium, 
CRYSTALS-KYBER and SPHINCS+. At the end they again say, " NIST is also 
developing a FIPS that specifies a digital signature algorithm derived from 
FALCON as an additional alternative to these standards." 
https://csrc.nist.gov/News/2024/postquantum-cryptography-fips-approved

If it takes 1.5-3 years to get the entire ecosystem of software updated, 
tested, implemented and then allow users to migrate to quantum safety, then 
Bitcoin code is future proofed. It will still require months (if BTC blocks 
normal transactions) to years (as a supported address type but not 
required) in order to migrate the wallets to safety. The longer the quantum 
resistant upgrade is delayed, the harsher the migration will need to 
become. 

Alice and Bob recently announced a new algorithm that breaks ECC-256 in 9 
hours with 127k qubits. 
https://alice-bob.com/blog/computing-256-bit-elliptic-curve-logarithm-in-9-hours-with-126133-cat-qubits/ The 
algorithms will continue to improve and the costs will continue to go down. 
While some people are very confident what the quantum hardware will look 
like in 3 years, can they be so confident about the algorithms? We have 
switched from supercomputer to network node method of growing quantum 
calculations. Parallel instead of Serial. Fault tolerant algorithms that 
prefetch results. Can we really be as confident about the algorithms as 
people seem to be about the hardware not being ready? Most people in 
quantum computing aren't aware of how much their competition has 
progressed, how can devs who don't read 10 or 50 new quantum computing 
papers per week be more confident than the people who do?

On Wednesday, January 1, 2025 at 1:25:24 PM UTC+1 David A. Harding wrote:

> On 2024-12-16 12:20, Tadge Dryja wrote:
> > An on-chain proof of quantum computer (PoQC I guess :) ) would be a
> > way to reduce the damage of activation forks. One way to build it:
> > Create a NUMS point pubkey - something like described in BIP341. Send
> > some coins to that address, then watch if it gets spent. [...]
> > Nodes can then have code which
> > watches for such a proof and changes consensus rules based on it.
>
> I think this could be even more useful if combined with a previous idea 
> far creating a NUMS[1][3] (or trust minimized[2]) pubkey compatible with 
> Bitcoin but with a security strength less than 128 bits. That way 
> someone might claim the bounty of the key with (say) 96 bits security 
> potentially months or years before QC advances made regular keys 
> insecure and tempted operators of QCs into stealing from regular user 
> addresses.
>
> -Dave
>
> [1] 
>
> https://gnusha.org/pi/bitcoindev/[email-masked]/ 
> <https://gnusha.org/pi/bitcoindev/[email-masked]/>
> [2] 
>
> https://gnusha.org/pi/bitcoindev/aRiFFJKz5wyHFDi2dXcGbNEHZD2nIwDRk7gaXIte-N1BoOEOQ-ySYRnk0P70S5igANSr2iqF2ZKV1dWvipaQHK4fJSv9A61-uH7w4pzxKRE=@protonmail.com/
> [3] 
>
> https://gnusha.org/pi/bitcoindev/[email-masked]/ 
> <https://gnusha.org/pi/bitcoindev/[email-masked]/>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/eaca24fe-b1ee-4309-ae88-ae8e4c82c003n%40googlegroups.com.