The microblog: 2018.10.12 18:02:37

2018.10.12 18:02:37 (1050778777935118336) from Daniel J. Bernstein, replying to "Gregory Neven (@gregoryneven)" (1050685524694978560):

The question at hand isn't whether the non-tight ROM proof is useless. The question is whether it's so strong that it justifies skipping key prefixing. The answer is no: key prefixing _eliminates_ multi-target attacks as a concern for auditors, while the non-tight proof doesn't.


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 11:52:04 (1050685524694978560) from "Gregory Neven (@gregoryneven)":

I agree that a tight non-ROM proof for Schnorr would be much better than a non-tight ROM proof. But in absence of that, a non-tight ROM proof is still strongly preferable (and useful) over no proof at all.