Re: [Cfrg] request for comments: ZSS Short Signature Scheme for SS and BN Curves

Dear Kohei Kasamatsu,

Thank you for your comment. The Cheon attacks against (variably
named) strong or static Diffie-Hellman assumption, or the
Diffie-Hellman with Auxiliary Input problem are very
interesting work. I will include the suggested references in
the I-D. However, I do not believe it poses a substantial
danger for ZSS for the following reasons:

1) Those attacks are predicated on the notion that the attacker
will have access to an oracle that will supply s^d*P for large
d to help solve the discrete log of sP for s, and there's not
sufficient reason to think that this additional information
would be available in the cases of interest.

2) Because the parameters used in the I-D (taken from the
MIKEY-SAKKE rfc) have a full sized cryptographic subgroup, even
if the attack applied, at best these attacks convert the
problem to O(Sqrt{(p-1)/d}+d) which is optimized if d<=p^(1/3),
but for the rfc parameters, this would still be an attack of
order O(p^(1/3))~=2^341, which is way worse than the standard
NSF costing.

Thanks again for your comment. Please let me know if you have
other concerns.

All the best,
Laura

-----Original Message-----
From: Kohei Kasamatsu [mailto:kasamatsu.kohei@po.ntts.co.jp] 
Sent: Thursday, July 25, 2013 4:38 AM
To: Laura Hitt
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] request for comments: ZSS Short Signature Scheme for SS and BN Curves

Dear L. Hitt

I have a comment.

The security of ZSS-signature depends on k+1 Exponent Problem.
The problem more efficiently can be computed by cheon algorithm [1,2] than Pollard's method. (cheon algorithm is not probabilistic polynomial time algorithm) Hence I think that it is needed that you analyze security against the algorithm.

[1] J.H. Cheon, Security Analysis of the Strong Diffie-Hellman Problem, EUROCRYPT 2006, LNCS 4004, pp. 1-11, Springer, 2006 [2] Y. Sakemi, G. Hanaoka, T. Izu, M. Takenaka, and M. Yasuda, "Solving a discrete logarithm problem with auxiliary input on a 160-bit elliptic curve", PKC 2012, LNCS 7293 pp. 595-608, Springer, 2012.

Best regards,
Kohei Kasamatsu

(2013/03/23 2:27), Laura Hitt wrote:
> <my apologies if this was sent twice, I saw strange behavior on my 
> end, so thought I'd try again.>
>
> I have recently submitted (as an Individual) two I-Ds and would greatly appreciate any comments you are able to offer.  They pertain to the ZSS short signature scheme from bilinear pairings on supersingular elliptic curves and on Barreto-Naerhig elliptic curves.
>
> http://www.ietf.org/internet-drafts/draft-irtf-cfrg-zss-00.txt
> http://www.ietf.org/internet-drafts/draft-irtf-cfrg-zssbn-00.txt
>
> Thank you!
> Laura Hitt
>
>
>
>
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>

--
Kohei Kasamatsu

NTT Software Corporation
E-mail: kasamatsu.kohei@po.ntts.co.jp