From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 24821BB6 for ; Tue, 13 Feb 2018 06:46:22 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from jupiter.mpi-klsb.mpg.de (jupiter.mpi-klsb.mpg.de [139.19.86.15]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4314F180 for ; Tue, 13 Feb 2018 06:46:21 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=mmci.uni-saarland.de; s=mail200803; h=Content-Transfer-Encoding:Mime-Version:Content-Type:References:In-Reply-To:Date:To:From:Subject:Message-ID; bh=WAKhMVW5tUJ13rdbieQ+aW60F8l9PqyFLcR4czK+AwI=; b=B9A337I1lPx3xKvtW1HO4rmUuLnvw/0nzhWpRB6lUEjxNYc1oQIXmkSlNSwve2Tqi+Xbjx/k6hsH9SaZxB17+PHi7TbTANR0jcs4pqwSwPI2vp1uubgXmtdCWCpFDZamYeYs7SGZ/M4Te1RnafzV6oQ4AOfAbJRLblSyGdqE7pQ=; Received: from srv-00-61.mpi-klsb.mpg.de ([139.19.86.26]:39504 helo=sam.mpi-klsb.mpg.de) by jupiter.mpi-klsb.mpg.de (envelope-from ) with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) id 1elUM5-0000Ia-0Q for bitcoin-dev@lists.linuxfoundation.org; Tue, 13 Feb 2018 07:46:19 +0100 Received: from [46.183.103.17] (port=2854 helo=tonno) by sam.mpi-klsb.mpg.de (envelope-from ) with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) id 1elUM3-00006p-NX for bitcoin-dev@lists.linuxfoundation.org; Tue, 13 Feb 2018 07:46:16 +0100 Message-ID: <1518504374.9878.24.camel@mmci.uni-saarland.de> From: Tim Ruffing To: Bitcoin Protocol Discussion Date: Tue, 13 Feb 2018 07:46:14 +0100 In-Reply-To: References: <1518450650.7829.87.camel@mmci.uni-saarland.de> Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.26.5 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-MPI-Local-Sender: true X-Spam-Status: No, score=-4.3 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Transition to post-quantum X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 13 Feb 2018 06:46:22 -0000 On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote: > In a post-quantum world, your second "d" type transaction is > completely forgeable, which means it is vulnerable to front-running. > An adversary capable of breaking ECDSA needs only listen for these > transactions, obtain "classic_sk" and then use a higher fee (or > relationship with a miner) to effectively turn your original "d" > transaction into a double-spend, with the forged transaction sending > all your funds to the adversary. That's not true. The d(ecommit) transaction, or better let's call it "decommit step" of a two-step transaction does not specify the effects (output script). This is what I denote by "tx" in the writeup, and it's already fixed by the c(ommit) step. So yes, if the user finally reveals d = classic_pk||Sign(classic_sk, tx) a quantum attacker can indeed forge d' = classic_pk||Sign(classic_sk, tx') for tx' != tx of his choice. But that won't help him, because the first valid c step in the chain is for tx and not for tx'. > The other issue with your approach is that if it is rolled out today, > it will effectively double transaction volumes - this is what I tried > to solve in solutions 2 and 3 in my article by instead modifying the > address generation process. Yep, it needs two entries in the blockchain, and that does not mean that it doubles the data. It will need some more bytes in the blockchain but also proper PQ-transactions could need more bytes in the blockchain, so I don't think that's the major issue. > > Regards, > > Tristan > > On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev -dev@lists.linuxfoundation.org> wrote: > > Hi Tristan, > > > > Regarding the "Post-Quantum Address Recovery" part (I haven't read > > the > > other parts), you may be interested in my message to the list from > > last > > month and the rest of the thread: > > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar > > y/015659.html > > > > This is an approach which aims to avoid the issues that you've > > mentioned in your blog post. > > > > Best, > > Tim > > > > On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev > > wrote: > > > Hi all, > > > > > > Recently I've been exploring what a post-quantum attack on > > Bitcoin > > > would actually look like, and what options exist for mitigating > > it. > > > > > > I've put up a draft of my research here: https://medium.com/@tris > > tanh > > > oy/11271f430c41 > > > > > > In summary: > > > 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are > > > scalable > > > 2) This is a rapidly advancing space and committment to a > > specific > > > post-quantum DSA now would be premature > > > 3) I've identified a strategy (solution 3 in the draft) that > > > mitigates against the worst case scenario (unexpectedly early > > attack > > > on ECDSA) without requiring any changes to the Bitcoin protocol > > or > > > total committment to a specific post-quantum DSA that will likely > > be > > > superseded in the next 3-5 years > > > 4) This strategy also serves as a secure means of transferring > > > balances into a post-quantum DSA address space, even in the event > > > that ECDSA is fully compromised and the transition is reactionary > > > > > > The proposal is a change to key generation only and will be > > > implemented by wallet providers. > > > > > > Feedback would be most appreciated. > > > > > > Regards, > > > > > > Tristan > > > _______________________________________________ > > > bitcoin-dev mailing list > > > bitcoin-dev@lists.linuxfoundation.org > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > >