From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 20 Aug 2025 17:07:37 -0700 Received: from mail-qv1-f58.google.com ([209.85.219.58]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uosq8-0008Cn-K9 for bitcoindev@gnusha.org; Wed, 20 Aug 2025 17:07:37 -0700 Received: by mail-qv1-f58.google.com with SMTP id 6a1803df08f44-70a88ddec70sf5392326d6.0 for ; Wed, 20 Aug 2025 17:07:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1755734850; x=1756339650; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=KvufrdRN4bMH7NNzQS7PDAtG2tbx3nYlqoV0M2UoldE=; b=OFSZey5SvdSJN5QmXixQQs5IDFl8U9CWc3JZZV6kdR/OdBT1ThDlfwEmTc78dXzHpu X6Yp2baWneYGZyixsMUOr9StsX2fiYaOUC973U0RUUUoNLX+k8daLUvnrcw42i7wEu8Q x1L8ufYeWe2gLYZUVE1S8RpJ7jz3CKUgk/ojKgg7rbzVdInp5wxI936yDYsCw9K+WZvs e+nuy8GSk1GGH4sZjnkL2MjL1Dt9BKU2MGIEp03zzkfcx1+eixyAr/P6DP85+EmbPhAW GaeyXw6EG12wg2Is2ZSfSapSC3WClj66At0Qtjdr8PVAe6iHkGgESHp9qXzT56L8C3S8 wIxg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1755734850; x=1756339650; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=KvufrdRN4bMH7NNzQS7PDAtG2tbx3nYlqoV0M2UoldE=; b=jQhMi1DMffSnPbczZlm4ZnNQmOBO5c76yrZrdTZrxPVjp3xRRQow+D3Pn3BYQPsAKp /IdjPaQ7ZX6LPQ0BLNT7j7yTMEj92W8lU198RtRZgh8R9ASVsGhcmUAI1d8whtHgd3n8 zOCbtGT5/FpYHqCJW7D8KkC2SDkbdBpkDTP/JKKF24KKN5M2rzL1V2gS2ObfK69iPsj0 /npsO3oIPqimfpQDsu65O42hW7DjfLc8KwF0GGBGZ1t0MegITLaid53bgAci1jHR2/z2 +kINZ3kQNiNWVZ8sdD4uwe3K9Sz2kjxJwZ+95z7wQUGgI7hPfJrG5rKo3kgxI6XfI5l0 HsLQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1755734850; x=1756339650; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=KvufrdRN4bMH7NNzQS7PDAtG2tbx3nYlqoV0M2UoldE=; b=Rf5WXQd9/j2rNZDeKV016FcwqwtGkFq/1r0IwysCdQ8nOpPi0Ngmgr7UWEX0Ecu4bk uzy+zW22I5cF1GgWwTao1Vh8vy6ri/GRr0EdoPrHkbwgncJ/K4DJHu1GTA1g2wzdaScy nTji8Ei9YVg3cTNIHcMVjS7CKsB+HiUaAGyTmlBROwZWQ3/pv8HhT85MPjDDIce8T/g9 NabUYN1Wbji6Q4oDFOyT0+0ej5mr9avBBn2oZu/LX69IOWt7aE1kNwMPLn5XixuUENmX FaUwow5JMat3Hiww2h6f+V7s3Nw8hdZtsuPK3j5STVSUrzjM9YHhLipLj/SPZEWqcuI2 rZQA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCVlieU1K9V62aVyFUyDmTtuUy3EfNtex6O9C8PGPS14ZOcU8y580J3cl9x7np371ZZ6MWeumIIeLufB@gnusha.org X-Gm-Message-State: AOJu0YwT5AQYZy5F/+ARRtCYhOag07zqm1jABvQhc8aBIKxQtl28pDJh 12BYMSrQxM0osVbGr8fyGfvZ4kNry8sGNjSciQzvdkpKdx5Ums3/DwWL X-Google-Smtp-Source: AGHT+IE2/vp3mQ9A1NHJoQIOlCxTXsIVFA9EM35jyF6oe6cioSw2+e3irrFzo+z7lpitFPvkHHoKQg== X-Received: by 2002:a05:6214:f2a:b0:709:e44c:991e with SMTP id 6a1803df08f44-70d88e6c4c8mr7080566d6.23.1755734849952; Wed, 20 Aug 2025 17:07:29 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZeRulVG3ajr2a80yLLnSXzsDpWx+dJAht6VVGHe+tCXJQ== Received: by 2002:ad4:5c66:0:b0:6ff:16c9:4229 with SMTP id 6a1803df08f44-70d85bf163els6495586d6.1.-pod-prod-05-us; Wed, 20 Aug 2025 17:07:26 -0700 (PDT) X-Received: by 2002:a05:6214:76a:b0:70d:7f6d:ae44 with SMTP id 6a1803df08f44-70d88fdec52mr7062766d6.39.1755734845905; Wed, 20 Aug 2025 17:07:25 -0700 (PDT) Received: by 2002:a05:690c:26c7:b0:71f:9f84:d07 with SMTP id 00721157ae682-71fb11b75eems7b3; Wed, 20 Aug 2025 13:07:39 -0700 (PDT) X-Received: by 2002:a05:690c:4507:b0:71f:b944:104f with SMTP id 00721157ae682-71fc8b186abmr1329957b3.50.1755720458945; Wed, 20 Aug 2025 13:07:38 -0700 (PDT) Date: Wed, 20 Aug 2025 13:07:38 -0700 (PDT) From: Alex Pruden To: Bitcoin Development Mailing List Message-Id: <80005f10-e9af-4b4f-a05f-de2bd666d8ccn@googlegroups.com> In-Reply-To: <1LDO_bQOdcKkNoKyyjfqLXAPUBVXSL667nAKDCNUfN2D7HEpDAkuFQrMubklIi1QdDI6BXdgB674g4uWYRlyQ5f-dlztDtnoEbIAlmrCg5M=@protonmail.com> References: <4d6ecde7-e959-4e6c-a0aa-867af8577151n@googlegroups.com> <6532d72c-fc2b-485a-9984-a9ade31e1760n@googlegroups.com> <1LDO_bQOdcKkNoKyyjfqLXAPUBVXSL667nAKDCNUfN2D7HEpDAkuFQrMubklIi1QdDI6BXdgB674g4uWYRlyQ5f-dlztDtnoEbIAlmrCg5M=@protonmail.com> Subject: Re: [bitcoindev] Re: [Draft BIP] Quantum-Resistant Transition Framework for Bitcoin MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_62510_312448924.1755720458582" X-Original-Sender: ap@projecteleven.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.7 (/) ------=_Part_62510_312448924.1755720458582 Content-Type: multipart/alternative; boundary="----=_Part_62511_8793440.1755720458582" ------=_Part_62511_8793440.1755720458582 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I consider the recent work by Mosca et al to be the most up-to-date in=20 terms of research estimation:=20 https://www.sciencedirect.com/science/article/pii/S0167739X24004308 The estimate he provides is approximately an order of magnitude less work= =20 required to break ECDSA (P-256) vs RSA-2048. Ironically, the longer=20 bit-lengths of RSA seem to actually contribute to post-quantum security,=20 even though the motivation for moving from RSA-1024 was to protect against= =20 NFS and other classical attacks against shorter RSA instances.=20 Note that the resource estimation in the paper doesn't account for Gidney's= =20 speedup, which was 20x reduction in qubits required. It's unclear whether= =20 that same improvement factor could be applied here; as the Gidney paper=20 showed, the earliest CRQCs will probably be hardwired for certain circuits= =20 for performance reasons. E.g. Gidney's circuit layout works for RSA-2048=20 and that's it. But the ideas he presents around error correction (e.g. the= =20 yoked surface code) might apply more broadly, it's hard to say.=20 Also note that many of his assumptions are based on a superconducting=20 architecture, which generally have faster runtimes but lower stability (so= =20 scaling is harder) Other architectures like this one https://arxiv.org/pdf/2506.20660 from the= =20 neutral atom community have slower runtimes but greater stability. But even= =20 if you scale, it probably only works for targeted, long-range attacks vs=20 specific PKs as a CRQC. Lots of variables to consider here in terms of estimating the timeline for= =20 a CRQC, but the proactive approach is probably the right one, because (to= =20 quote Gidney in his conclusion) we should "*prefer security to not be=20 contingent on progress being slow.*" On Tuesday, August 12, 2025 at 3:04:32=E2=80=AFAM UTC-6 ArmchairCryptologis= t wrote: > > An astute observation. To clarify the quantum computing landscape:=20 > Google's current quantum processors do not possess 50 logical qubits, and= =20 > even if they did, this would be insufficient to compromise ECDSA - let=20 > alone RSA-2048, which would require approximately 20 million noisy physic= al=20 > qubits for successful cryptanalysis [0]. > > > That paper is pretty old. There is a recent paper from a couple of months= =20 > ago by the same author (Craig Gidney from Google Quantum AI) claiming=20 > that you could break RSA-2048 with around a million noisy qubits in about= a=20 > week.=20 > > Paper: https://arxiv.org/pdf/2505.15917 > Blog post:=20 > https://security.googleblog.com/2025/05/tracking-cost-of-quantum-factori.= html > > I can't say for sure whether this approach can be applied to ECDSA; I hav= e=20 > seen claims before that it has less quantum resistance than RSA-2048, but= =20 > I'm unsure if this is still considered to be the case. And while these=20 > papers are of course largely theoretical in nature since nothing close to= =20 > the required amount of qubits exists at this point, I haven't seen anyone= =20 > refute these claim at this point. These is still no hard evidence I'm awa= re=20 > of that a quantum computer capable of breaking ECDSA is inevitable, but= =20 > given the rate of development, there could be some cause of concern. > > Getting post-quantum addresses designed, implemented and activated by 203= 0=20 > in accordance with the recommendations in this paper seems prudent to me,= =20 > if this is at all possible. Deactivating inactive pre-quantum UTXOs with= =20 > exposed public keys by 2035 should certainly be considered. But I still= =20 > don't feel like deactivating pre-quantum UTXOs without exposed public key= s=20 > in general is warranted, at least until a quantum computer capable of=20 > breaking public keys in the short time between they are broadcast and=20 > included in a block is known to exist - and even then, only if some=20 > scheme could be devised that still allows spending them using some=20 > additional cryptographic proof of ownership, ZKP or otherwise. > > -- > Best, > ArmchairCryptologist > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 80005f10-e9af-4b4f-a05f-de2bd666d8ccn%40googlegroups.com. ------=_Part_62511_8793440.1755720458582 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I consider the recent work by Mosca et al to be the most up-to-date in term= s of research estimation:=C2=A0https://www.sciencedirect.com/science/a= rticle/pii/S0167739X24004308

The estimate he provides is app= roximately an order of magnitude less work required to break ECDSA (P-256) = vs RSA-2048. Ironically, the longer bit-lengths of RSA seem to actually con= tribute to post-quantum security, even though the motivation for moving fro= m RSA-1024 was to protect against NFS and other classical attacks against s= horter RSA instances.=C2=A0

Note that the resource estimati= on in the paper doesn't account for Gidney's speedup, which was 20x reducti= on in qubits required. It's unclear whether that same improvement factor co= uld be applied here; as the Gidney paper showed, the earliest CRQCs will pr= obably be hardwired for certain circuits for performance reasons. E.g. Gidn= ey's circuit layout works for RSA-2048 and that's it. But the ideas he pres= ents around error correction (e.g. the yoked surface code) might apply more= broadly, it's hard to say.=C2=A0

Also note that many = of his assumptions are based on a superconducting architecture, which gener= ally have faster runtimes but lower stability (so scaling is harder)
<= br />Other architectures like this one=C2=A0https://arxiv.org/pdf/2506.20660 from the neutral atom co= mmunity have slower runtimes but greater stability. But even if you scale, = it probably only works for targeted, long-range attacks vs specific PKs as = a CRQC.

Lots of variables to consider here in te= rms of estimating the timeline for a CRQC, but the proactive approach is pr= obably the right one, because (to quote Gidney in his conclusion) we should= "prefer security to not be contingent on progress being slow."

On Tuesday, August 12, 2025 at 3:04:32=E2=80=AFAM UTC-= 6 ArmchairCryptologist wrote:

=20 An astute observation. To clarify the quantum computing landscape: Google's current quantum processors do not possess 50 logical qubits, and even if they did, this would be insufficient to compromise ECDSA - let alone RSA-2048, which would require approximately 20 million noisy physical qubits for successful cryptanalysis [0].

=
That paper is pretty old. There is a recent paper from a = couple of months ago by the same author (Craig Gidney=C2=A0fro= m=C2=A0Google Quantum AI) claiming that you could break RSA-20= 48 with around a million noisy qubits in about a week.=C2=A0


I can't say for sure whether this approach can be applied to=20 ECDSA; I have seen claims before that it has less quantum resistance than R= SA-2048, but I'm unsure if this is still considered to be the case. And= while these papers are of course largely theoretical in nature=20 since nothing close to the required amount of qubits exists at this=20 point, I haven't seen anyone refute these claim at this point. These is= still no hard evidence I'm aware of that a quantum computer capable of= breaking ECDSA is inevitable, but given the rate of development, there cou= ld be some cause of concern.

Getting post-qu= antum addresses designed, implemented and activated by 2030 in accordance w= ith the recommendations in this paper seems prudent to me, if this is at al= l possible. Deactivating inactive=C2=A0pre-quantum UTXOs with = exposed public keys by 2035 should certainly be considered. But I still don= 't feel like deactivating pre-quantum UTXOs without exposed public keys= in general is warranted, at least until a quantum computer capable of brea= king public keys in the short time between they are broadcast and included = in a block=C2=A0is known to exist=C2=A0- and even then, only i= f some scheme could be devised that still allows spending them using some a= dditional cryptographic proof of ownership, ZKP or otherwise.
<= div>
--
Best,
ArmchairCryptologist

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/80005f10-e9af-4b4f-a05f-de2bd666d8ccn%40googlegroups.com.
------=_Part_62511_8793440.1755720458582-- ------=_Part_62510_312448924.1755720458582--