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

[David Jacobson <[e-mail]>]

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