Subject: Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

From: ZmnSCPxj <[email-masked]>
Date: Tue, 16 Mar 2021 02:38:55 +0000

Good morning aj,

> On Tue, Mar 16, 2021 at 08:01:47AM +0900, Karl-Johan Alm via bitcoin-dev wrote:
>
> > It may initially take months to break a single key.
>
> From what I understand, the constraint on using quantum techniques to
> break an ECC key is on the number of bits you can entangle and how long
> you can keep them coherent -- but those are both essentially thresholds:
> you can't use two quantum computers that support a lower number of bits
> when you need a higher number, and you can't reuse the state you reached
> after you collapsed halfway through to make the next run shorter.
>
> I think that means having a break take a longer time means maintaining
> the quantum state for longer, which is harder than having it happen
> quicker...
>
> So I think the only way you get it taking substantial amounts of time to
> break a key is if your quantum attack works quickly but very unreliably:
> maybe it takes a minute to reset, and every attempt only has probability
> p of succeeding (ie, random probability of managing to maintain the
> quantum state until completion of the dlog algorithm), so over t minutes
> you end up with probability 1-(1-p)^t of success.
>
> For 50% odds after 1 month with 1 minute per attempt, you'd need a 0.0016%
> chance per attempt, for 50% odds after 1 day, you'd need 0.048% chance per
> attempt. But those odds assume you've only got one QC making the attempts
> -- if you've got 30, you can make a month's worth of attempts in a day;
> if you scale up to 720, you can make a month's worth of attempts in an
> hour, ie once you've got one, it's a fairly straightforward engineering
> challenge at that point.
>
> So a "slow" attack simply doesn't seem likely to me. YMMV, obviously.

What you describe seems to match mining in its behavior: probabilistic, and scalable by pushing more electricity into more devices.

>From this point-of-view, it seems to me that the amount of energy to mount a "fast" attack may eventually approach the energy required by mining, in which case someone who possesses the ability to mount such an attack may very well find it easier to just 51% the network (since that can be done today without having to pour R&D satoshis into developing practical quantum computers).

Regards,
ZmnSCPxj