Subject: [Cfrg] Review of draft-irtf-cfrg-zss*

From: Watson Ladd <[email-masked]>
Date: Tue, 24 Dec 2013 12:39:22 -0500

Dear all,
These two drafts define a signature scheme based on pairings over BN
and supersingular curves. Actually, the setting is a general pairing
of Type III, with no hashing to group required.
The signature scheme reduces to a k-DH style assumption in the ROM,
and I haven't cooked up a dirty hash that can break it. Intermediate
assumptions on the hash function to get a reduction are open. This is
not a Fiat-Shamir transform of a ZKP, so the standard heuristics are
not quite sufficient.

The standardization does not pick a curve or a hash.

There is a typo that leads to the representation of points on E' not
being defined: F_p in that section should be replaced by "any field".

Supersingular curves have small embedding degree: this forces the use
of uncompetitively large primes.

BN curves have embedding degree 12. This means a tower of degree 3,
then 4. In such a tower the discrete logarithm problem can be solved
quicker than over a prime field of the same size. I am currently
searching the literature for the exact coefficients, but I do not feel
the table in the draft is correct.

This signature scheme promises shorter signatures than schemes of
schnorr-style. However, in practice the failure to use point
compression means Ed25519 is shorter. It's also much faster to verify,
as pairings are expensive.

If the k-DH complexity and discrete log complexities can be tied down
better, I would have no objection to publishing this as an RFC.

Sincerely,
Watson Ladd