Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id E2033C000A for ; Fri, 16 Apr 2021 03:47:55 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id B6FF040273 for ; Fri, 16 Apr 2021 03:47:55 +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 1h33V55fRYde for ; Fri, 16 Apr 2021 03:47:54 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-40138.protonmail.ch (mail-40138.protonmail.ch [185.70.40.138]) by smtp2.osuosl.org (Postfix) with ESMTPS id 78286400B8 for ; Fri, 16 Apr 2021 03:47:54 +0000 (UTC) Date: Fri, 16 Apr 2021 03:47:45 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1618544870; bh=yCns9u5XV0FbOt/GinUI8qBVw1/242iaBlI2zOQF630=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=oSoQO0KGaGOAKH3JIxiznkgviGXr34lSrn5XT0VcLE+hc2QcFPnavBEX38eqTVOGR nHiAPAuI4nkIU0FjZMuLP1g9LxTQWpG+98g6QyZqMQgsR7+cHJpIDov5iG4VV9rpMF JtiGATp0qPSCIwxh954Y0jhWZrPBhB/NBsYkQUTI= To: Lloyd Fournier , Bitcoin Protocol Discussion From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <202103152148.15477.luke@dashjr.org> <20210316002401.zlfbc3y2s7vbrh35@ganymede> 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: Fri, 16 Apr 2021 03:47:56 -0000 Good morning LL, > On Tue, 16 Mar 2021 at 11:25, David A. Harding via bitcoin-dev wrote: > > > I curious about whether anyone informed about ECC and QC > > knows how to create output scripts with lower difficulty that could be > > used to measure the progress of QC-based EC key cracking.=C2=A0 E.g., > > NUMS-based ECDSA- or taproot-compatible scripts with a security strengt= h > > equivalent to 80, 96, and 112 bit security. > > Hi Dave, > > This is actually relatively easy if you are willing to use a trusted setu= p. The trusted party takes a secp256k1 secret key and verifiably encrypt it= under a NUMS public key from the weaker group. Therefore if you can crack = the weaker group's public key you get the secp256k1 secret key. Camenisch-D= amgard[1] cut-and-choose verifiable encryption works here. > People then pay the secp256k1 public key funds to create the bounty. As l= ong as the trusted party deletes the secret key afterwards the scheme is se= cure. > > Splitting the trusted setup among several parties where only one of them = needs to be honest looks doable but would take some engineering and analysi= s work. To simplify this, perhaps `OP_CHECKMULTISIG` is sufficient? Simply have the N parties generate individual private keys, encrypt each of= them with the NUMS pubkey from the weaker group, then pay out to an N-of-N= `OP_CHECKMULTISIG` address of all the participants. Then a single honest participant is enough to ensure security of the bounty= . Knowing the privkey from the weaker groups would then be enough to extract = all of the SECP256K1 privkeys that would unlock the funds in Bitcoin. This should reduce the need for analysis and engineering. Regards, ZmnSCPxj