Re: [bitcoin-dev] Transition to post-quantum

From: Tim Ruffing <tim.ruffing@mmci•uni-saarland.de>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Transition to post-quantum
Date: Tue, 13 Feb 2018 07:46:14 +0100	[thread overview]
Message-ID: <1518504374.9878.24.camel@mmci.uni-saarland.de> (raw)
In-Reply-To: <CAFEpHQHYdE3m2GUtN=ijvtYUudwtcG52rRxzH66VFbgO1KEihw@mail.gmail.com>

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 <bitcoin
> -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
> 
> 