path: root/4b/68028693bf0933e833b3e75a9dd47fef5ef8b4

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 <bitcoindev+bncBD7JPLP3QABRBPWGTHCQMGQEFR5TGJY@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <ap@projecteleven.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
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>
 <fff86606-d6ce-4319-a341-90e9c4eba49dn@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: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
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=A0<a href=3D"https://www.sciencedirect.com/sci=
ence/article/pii/S0167739X24004308">https://www.sciencedirect.com/science/a=
rticle/pii/S0167739X24004308</a><br /><br />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<br /><div><br />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<div><br /></div><div>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 /><=
br />Other architectures like this one=C2=A0<a href=3D"https://arxiv.org/pd=
f/2506.20660">https://arxiv.org/pdf/2506.20660</a> 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.<br /><div><br /></div><div>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=
 "<b>prefer security to not be contingent on progress being slow.</b>"</div=
><div><br /></div></div></div><div class=3D"gmail_quote"><div dir=3D"auto" =
class=3D"gmail_attr">On Tuesday, August 12, 2025 at 3:04:32=E2=80=AFAM UTC-=
6 ArmchairCryptologist wrote:<br/></div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); pad=
ding-left: 1ex;"><div style=3D"font-family:Arial,sans-serif;font-size:14px"=
><div><br>
        <blockquote type=3D"cite">
           =20
An astute observation. To clarify the quantum computing landscape:
Google&#39;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].<br></blockquote><div><br>=
</div></div></div><div style=3D"font-family:Arial,sans-serif;font-size:14px=
"><div><div><span>That paper is pretty old. There is a recent paper from a =
couple of months ago by the same author (<span>Craig Gidney</span>=C2=A0fro=
m=C2=A0<span>Google Quantum AI</span>) claiming that you could break RSA-20=
48 with around a million noisy qubits in about a week.=C2=A0<span><br></spa=
n></span><div><span><br></span></div><div><span>Paper:=C2=A0<a rel=3D"noref=
errer nofollow noopener" href=3D"https://arxiv.org/pdf/2505.15917" target=
=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;=
q=3Dhttps://arxiv.org/pdf/2505.15917&amp;source=3Dgmail&amp;ust=3D175580508=
7126000&amp;usg=3DAOvVaw2bLrcxCBoyk8INjFbTSM3X">https://arxiv.org/pdf/2505.=
15917</a><br></span></div><div>Blog post:=C2=A0<span><a rel=3D"noreferrer n=
ofollow noopener" href=3D"https://security.googleblog.com/2025/05/tracking-=
cost-of-quantum-factori.html" target=3D"_blank" data-saferedirecturl=3D"htt=
ps://www.google.com/url?hl=3Den&amp;q=3Dhttps://security.googleblog.com/202=
5/05/tracking-cost-of-quantum-factori.html&amp;source=3Dgmail&amp;ust=3D175=
5805087126000&amp;usg=3DAOvVaw039DcUJOm7b9UWOEsWyAvN">https://security.goog=
leblog.com/2025/05/tracking-cost-of-quantum-factori.html</a></span></div><d=
iv><br></div><div>I
 can&#39;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&#39;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&#39;t seen anyone refute these claim at this point. These is=
 still no hard evidence I&#39;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.</div><div><br></div><div><span>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=A0<span>pre-quantum </span>UTXOs with =
exposed public keys by 2035 should certainly be considered. But I still don=
&#39;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=A0<span>is known to exist</span>=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.</span></div><=
div><span><br></span></div><div><span>--</span></div><div><span>Best,</span=
></div><div><span>ArmchairCryptologist</span></div></div></div></div></bloc=
kquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/80005f10-e9af-4b4f-a05f-de2bd666d8ccn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/80005f10-e9af-4b4f-a05f-de2bd666d8ccn%40googlegroups.com</a>.<br />

------=_Part_62511_8793440.1755720458582--

------=_Part_62510_312448924.1755720458582--