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

[David Jacobson <[e-mail]>]

On 5/3/15 3:09 PM, Michael Hamburg wrote:
>
>> On May 3, 2015, at 2:00 PM, David Jacobson <[e-mail] 
>> <mailto:[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
No, I have no scheme in mind.  This was just an intuitive argument that 
allowing an entropy input requires that the minimum signature size be 
larger.  After I wrote that, I got to thinking about formalizing my 
argument, probably involving an oracle that transforms messages and 
public-private keypairs to a set of possible signatures, one of which is 
selected by the supplied randomness. But I've not got anything to post.

    --David