Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

[Michael Hamburg <[e-mail]>]

> On May 3, 2015, at 2:00 PM, David Jacobson <[e-mail]> wrote:
> 
> On 5/3/15 9:50 AM, Mihir Bellare wrote:
>>  If someone was foolish enough to do encrypt and sign, then there would be a need to make identical plaintext not have identical signatures.  If anyone feels that we need to accommodate this, then it would be good to allow an optional random
>> 
>> The usual goal is that one wants IND-CPA privacy. The attack one is trying to prevent here is loss of IND-CPA due to the ability to detect repeats, meaning an adversary knowing messages M1,M2 and their ciphertexts C2,C2 can test whether or not M1=M2. Signature randomization does not help prevent this, because signatures are verifiable given the public key and this can be used to detect repeats even with randomization. So this would not appear to be a good reason to keep randomization in the signature. 
>> 
>> Mihir
>> 
>> 
>> 
>> 
> 
> Mihir is right.  
> 
> In addition, I have a suspicion based on information theory that if a signature allows randomization, the size of size of the signature will need to be larger.  Here is an intuitive argument.  Suppose that the size of the signature is 256 bits.  Somehow the message and the private key map somewhat uniformly onto those 256 bits.  For any given message and key, only one signature value is correct.  Now, I we add 256 bits of randomness, and them mix in in the obvious way.  Now for a fraction of about (1-1/e) of the signature space, there is a value of the input randomness that could have generated it.  That means that the verifier can't reject most signature values.  To avoid this, we have to have a larger signature, so valid values (for a given message and key) are sparse.  Consider that ECDSA with P-256 has 512 bit signatures.
> 
> For this reason, I think allowing optional randomness as in proposal #4 is not just not helpful, but forces larger signatures.  For many uses, small signature are desirable.  So I retract my original support for #4.  Now I'm only supporting #2.
> 
>   --David Jacobson

Do you actually have a 2*WF ECC signature scheme in mind?  The only ones I know of use pairings, and the 3*WF and 4*WF ones I know of are all randomized (but can and should be derandomized).

— Mike Hamburg