The microblog: 2018.10.12 07:10:08

2018.10.12 07:10:08 (1050614572774653953) from Daniel J. Bernstein, replying to "Pieter Wuille (@pwuille)" (1050576622854668288):

Even if we assume that the best DL algorithms cost 2^128, a cost-2^64 generic-hash attack against the Schnorr signature system would not contradict any of the ROM theorems that I've seen supposedly proving security of the system. It's important to read what the theorems say.


2018.10.11 17:08:42 (1050402818195111937) from Daniel J. Bernstein, replying to "Gregory Neven (@gregoryneven)" (1050093668089106432):

The chance of breaking 1 of N signature users with key prefixing is at most the chance of breaking a targeted user in the original system. Simple; tight; real H, not ROM; eliminates concerns about multi-user attacks. Theorems without key prefixing have questionable assumptions.

2018.10.11 18:11:15 (1050418559485136896) from "Gregory Neven (@gregoryneven)":

Sure, with key prefixing, multi-user security is implied tightly by single-user security. But single-user security for Schnorr is still under DL in ROM with Qh loss. So final security statement remains the same, with or without key prefixing.

2018.10.12 03:38:23 (1050561287070109696) from Daniel J. Bernstein, replying to "Gregory Neven (@gregoryneven)" (1050418559485136896):

No. The ROM proofs for Schnorr signatures are too weak to be useful. The _real_ argument for security is that some cryptanalysts have tried and failed to break the system. But how many cryptanalysts have tried attacking multiple Schnorr users? Key prefixing answers this question.

2018.10.12 04:39:20 (1050576622854668288) from "Pieter Wuille (@pwuille)":

Interesting viewpoint. Ultimately, the security of every scheme relies on people having tried to break it and failed. But in this instance, isn't the ROM proof really telling us that a break in the signature scheme must be due to a hash function break or DL break?