From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 5163BC000A for ; Tue, 16 Mar 2021 02:39:12 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 384F142FFC for ; Tue, 16 Mar 2021 02:39:12 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.599 X-Spam-Level: X-Spam-Status: No, score=-1.599 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=pass (1024-bit key) header.d=protonmail.com Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id V_H_aNHIRyqR for ; Tue, 16 Mar 2021 02:39:11 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-40140.protonmail.ch (mail-40140.protonmail.ch [185.70.40.140]) by smtp2.osuosl.org (Postfix) with ESMTPS id C69B642FA9 for ; Tue, 16 Mar 2021 02:39:10 +0000 (UTC) Date: Tue, 16 Mar 2021 02:38:55 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1615862346; bh=YWlaboKjefd9J12duZ2r9+sP6U4nk/p8WZD5VI59Hgo=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=cdGT6b/Tlwf6igNAstIhqc5s4ichVuIfd6ljC44rhIMw/w3rDVet+d0YzcOSuvoBh oFlABSOYTCacWdwiB6DcOZUOPyiVi5MHzPDEog4Ei0mHp3wg4rs3F0vyVPk9eUptAa hKjTFnCJUMI4wRRwF1YAIu0QCOCfQmlisGy5gN5Q= To: Anthony Towns , Bitcoin Protocol Discussion From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: <20210316005001.GA4304@erisian.com.au> References: <202103152148.15477.luke@dashjr.org> <20210316005001.GA4304@erisian.com.au> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable 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 02:39:12 -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 pe= r > 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 w= hich case someone who possesses the ability to mount such an attack may ver= y 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 comp= uters). Regards, ZmnSCPxj