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

[Michael Hamburg <[e-mail]>]

> On May 4, 2015, at 7:15 AM, David Jacobson <[e-mail]> wrote:
> 
> 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

I agree that a randomized signatures have to be bigger than WF bits, and the same is not obviously true for deterministic ones.  But ECC signatures are usually based on zero-knowledge proofs, which are intrinsically randomized but can be derandomized.  In some sense, they’re already derandomized once to make  NIZK: the step c = hash(g^k,message) in Schnorr sigs is in place of a random challenge, which is why the hash is usually modeled as a random oracle.

I also agree that CFRG should specify a derandomized signature algorithm.  But since it does not harm interoperability (or security if done right), we should not absolutely require the nonce to be computed in the way we specify.  We should allow a different PRF to be substituted, because for example HMAC-SHA2 is a nightmare to blind against DPA.  We should allow the use of random nonces: if not in TLS, then in low-latency environments like v2v where pregenerated signature coupons could be a big win.

— Mike