Subject: [bitcoindev] Re: Proposal for Quantum-Resistant Cryptography in Bitcoin - BIP Submission

From: Ian Quantum <[email-masked]>
Date: Thu, 12 Dec 2024 18:07:28 -0800 (PST)

Some contributions of my own to add to this conversation.
FALCON wasn't approved by NIST because the security of the  algorithm is 
directly linked to the randomness of the input parameters. There was a 
similar concern over RSA about 25 years ago, and the question of the 
exponent related to the operation as a matter of security. They weren't 
sure if the exponent should be high, random or irrelevant to the security. 
Turns out that it was irrelevant, so the cryptography community relaxed and 
selected the exponent 3 for RSA for performance reasons with no cost to 
security. When a parameter is so relevant to the security of FALCON it is 
alarming, and the algorithm may be unsuitable for blockchain. 

I would suggest NTRU Prime by Daniel Bernstein as a solid contender for 
secure Lattice. Critically to a heterogenous environment, it is not 
susceptible to side channel attacks so the keys cannot be stolen through 
magnets next to a thumb drive. Daniel Bernstein managed to perform side 
channel attacks 10 out of 10 times on multiple NIST PQ standards.

A quantum network runs 45x faster than the same qubits assigned to a single 
machine. https://arxiv.org/abs/2211.15465
Quantum networks also require less wiring, and a 6000 node network of 1152 
qubit machines can crack bitcoin in 10 minutes on 
average. https://arxiv.org/abs/2306.08585 The qubit count is expected to go 
down by at least 30% by 2027 due to general improvement in the algorithm. 
Litinski explained his algorithm at Crypto conference, and included further 
optimizations to lower the qubit count and increase 
performance. https://www.youtube.com/watch?v=AumHpDRS5iI

The scaling of some machines and algorithms is indeed 
linear https://arxiv.org/abs/1808.02892 but this is not always true. With 
Active Volume, an 3x increase in nodes causes a 7x increase in performance.

Due to Grover's it is critical that 256 bit addresses be used. 160 bits is 
simply too small to be future proof.

With the advent of quantum networks, the hardware is more achievable. Mass 
production becomes the new paradigm, not IBM's flagship for gathering news 
attention. PSI Quantum has solved mass 
production https://arxiv.org/html/2404.17570v1 and has completed the entire 
system end to end. https://www.youtube.com/watch?v=A1tD4VXzswU 

A reasonable estimate would be PSI Quantum breaking secp256k1 in 2027. 
Hopefully we will get a 'canary warning' by breaking ECC-32 but to increase 
scale to break ECC-256 would only be a 4x increase in total qubits.

Other candidates for mass production are:
Oxford Ionics, who produces 256 qubit machines that run at room 
temperature. The trapped ion system is cooled and operates using lasers and 
magnets. 
Riverlane, who produces rapid components but is mostly focused on high 
performance. Targeting 1 mil qubits in 2027 is a reasonable extrapolation 
of their roadmap. (100k qubits in 2026 after 10k qubits in 
2025.) https://www.riverlane.com/newsroom
Intel, who produces electron spin wafers with an unknown but extremely 
large number of qubits per wafer. These devices are produced fully 
autonomously and without intervention. 15 wafers are produced per day, per 
manufacturing and testing device. More devices will probably be produced 
soon, and they could potentially produce billions of qubits per week with 
20 machines. They do not have any reports of algorithm on chip, networking, 
or complete computing capabilities at this 
time. https://www.intc.com/news-events/press-releases/detail/1693/intel-takes-next-step-toward-building-scalable 

I hope that we can make significant progress in getting Bitcoin quantum 
safe.

Ian Smith
@IanSmith_HSA

On Tuesday, October 22, 2024 at 12:38:44 AM UTC+9 Jon Atack wrote:

> Hi Agustin,
>
> Good to see!
>
> Have you seen the work-in-progress BIP draft at 
> https://github.com/bitcoin/bips/pull/1670?  It may be good to review each 
> other (and possibly collaborate).
>
> Discussions/references to that draft:
> * https://groups.google.com/g/bitcoindev/c/Aee8xKuIC2s/m/cu6xej1mBQAJ (Mailing 
> list discussion)
> * https://delvingbitcoin.org/t/proposing-a-p2qrh-bip-towards-a-quantum-
> resistant-soft-fork/956?u=cryptoquick (Delving Bitcoin discussion)
> * https://bitcoinops.org/en/newsletters/2024/06/14/ (Bitcoin Optech 
> newsletter)
> * https://bitcoinops.org/en/podcast
> /2024/06/18/#draft-bip-for-quantum-safe-address-format (Bitcoin Optech 
> discussion transcript)
>
> Best regards,
> Jon
>
> On Thursday, October 17, 2024 at 5:06:34 PM UTC-6 Agustin Cruz wrote:
>
> Dear Bitcoin Developers, 
> I would like to propose a Bitcoin Improvement Proposal (BIP) that aims to 
> introduce quantum-resistant cryptography to the Bitcoin protocol. With the 
> rapid advancement in quantum computing, this proposal outlines the 
> integration of post-quantum cryptographic algorithms (SPHINCS+ and 
> Dilithium) to safeguard Bitcoin’s long-term security.
>  
> The key points of the proposal are: 
> - Introduction of quantum-resistant signature algorithms (SPHINCS+ and 
> Dilithium). 
> - New Bech32-based address formats for quantum-resistant addresses. 
> - Modifications to transaction structures and script opcodes to support 
> larger signature sizes. 
> - A transition mechanism through a soft fork to ensure backward 
> compatibility with existing Bitcoin addresses and transactions. 
>
> The full BIP draft is available here 
> https://github.com/chucrut/bips/blob/master/bip-xxxx.md for your review 
> and feedback. I look forward to the community's input and am open to 
> suggestions on how to improve the proposal. 
>
> Best regards,
> Agustín Cruz
>
>

-- 
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/d142e67b-a0b1-49a0-9593-82053d55e3a5n%40googlegroups.com.