On 13/02/2018 5:46 PM, Tim Ruffing via bitcoin-dev wrote:
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'.
Thank you for clarifying, I should have caught that.

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.

The worst-case outcome is that ECDSA is broken before PQ addresses are rolled out. There is no reactive response to this - all the existing ECDSA addresses will be compromised. A proactive measure is required, and it should be deployed sooner rather than later.

Any two-step approach adopted now as a proactive measure will not only bloat the blockchain, it will also double the effective confirmation time - for all transactions between now and when PQ addresses are rolled out, which seems unlikely to happen in the next 5 years. The bloat will be permanent.

Either way, would you mind if I included your approach in the article, with credit? I will seek your review before publishing.

Regards,

Tristan

On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
-d...@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

_______________________________________________
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

Reply via email to