From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 50A9CC0001 for ; Tue, 16 Mar 2021 00:50:13 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 2AE684EC5B for ; Tue, 16 Mar 2021 00:50:13 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.499 X-Spam-Level: X-Spam-Status: No, score=-0.499 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, UNPARSEABLE_RELAY=0.001] autolearn=ham autolearn_force=no Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5vn8MHbC18K3 for ; Tue, 16 Mar 2021 00:50:10 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226]) by smtp4.osuosl.org (Postfix) with ESMTPS id 486764EC1D for ; Tue, 16 Mar 2021 00:50:10 +0000 (UTC) Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au) by azure.erisian.com.au with esmtpsa (Exim 4.92 #3 (Debian)) id 1lLxuP-0005l2-Q3; Tue, 16 Mar 2021 10:50:07 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Tue, 16 Mar 2021 10:50:01 +1000 Date: Tue, 16 Mar 2021 10:50:01 +1000 From: Anthony Towns To: Karl-Johan Alm , Bitcoin Protocol Discussion Message-ID: <20210316005001.GA4304@erisian.com.au> References: <202103152148.15477.luke@dashjr.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Score-int: -18 X-Spam-Bar: - Subject: Re: [bitcoin-dev] PSA: Taproot loss of quantum protections X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 16 Mar 2021 00:50:13 -0000 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. Cheers, aj