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

[David Leon Gil <[e-mail]>]

4, 2

--

I'm not sure I understand David's argument about 4. See Koblitz and
Meneze's rather dull recent paper for the details of how to do this:
http://eprint.iacr.org/2015/140

(And, indeed, OpenSSL and Go use similar constructions, both of which
predate the KM paper.)

--

Also, there is a need for encrypt-and-sign under some circumstances:
Suppose that (as for encrypted email in some cases) you want a mail server
to verify that mail is signed under an authorized public key, but not be
able to decrypt the mail.

In this case, it is easy to ensure unlinkability by an adversary who does
not know the public key by encrypting the message under the signature.
(Robert Ransom is credited for the observation that this should be
blindingly obvious in Bernstein's Elligator paper.)

In fact, one can achieve a slightly stronger goal with, e.g.:

h = hash(publickey || message || r)
p = hash(publickey || message)

sig' = (r || s) ^ p

where `hash` is an indifferentiable hash function with sufficient output
length, and `r` is the public nonce. (A slightly different construction is
needed for PRFs.)

In this case, an adversary must know *both* the public key and the message
to decrypt the signature.[*]

And the cost of achieving unlinkability is a single XOR.

--

Many thanks to Payman Mohassel and Juan Garay for very helpful
conversations on this and some related constructions.

Prior cites appreciated.

- David

[*] Note, however, that a construction like:

p = mac(publickey, hash(message))
h = mac(r, s)

does not achieve as strong as a goal. (This should be clear if you consider
the first construction as an AONT of the public key and message with the
signature.)
On Sun, 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
>
>
>
>
>
>  _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>