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

[Laura Hitt <[e-mail]>]

Hi Kohei,

The Cheon attack assumes knowledge of s^i * P for i in [0,d] in order to determine s, where d is some divisor of p-1 or p+1.  I believe you are suggesting that with d pairs of signature and message, one would obtain the necessary s^i * P.  However, if we look at the ZSS signature scheme explicitly, we shall see that is not the case.

Signature 1 = [H(m1)+x]^-1 * P
Signature 2 = [H(m2)+x]^-1 * P
...
Signature i = [H(mi)+x]^-1 * P

There is no oracle providing the necessary s^i * P for the ZSS signature scheme, so I do not believe the I-D needs to be changed to address the Cheon attacks.

Please let me know if you have further questions or concerns.

Best,
Laura

-----Original Message-----
From: Kohei Kasamatsu [mailto:[e-mail]] 
Sent: Wednesday, September 18, 2013 9:38 PM
To: Laura Hitt
Cc: [e-mail]
Subject: Re: [Cfrg] request for comments: ZSS Short Signature Scheme for SS and BN Curves

Hi Laura,


Thank you for you email and I apologise for the delay in replying to you.

I recommend ZSS signature to use elliptic curves with prime order p such that both of p+1 and p−1 have no small divisor greater than (log p)^2. This condition of prime order p prevents Cheon attack.
Detailed information on above countermeasure is given in [1].

The reason of my recommendation is that applying ZSS signature to cheon algorithm gives influence on estimation of exact security strength.
(It gives no influence on asymptotic estimation.) I think that standard NSF cannot be applied to elliptic curves and pollard-rho algorithm is best performance against ECDLP of elliptic curves at present. Although cost of cheon attack depends on value d of 
d+1 Exponent Problem (d is the number of pairs of signature and message
which attacker can obtain in the case of ZSS signature), I think that there is possibility that the cost is smaller than one of Pollard-rho algorithm which is exponential algorithm.

Please let me know if there are any mistakes.
Welcome to discussion.

Best,

[1] J.H. Cheon, Security Analysis of the Strong Diffie-Hellman Problem, EUROCRYPT 2006, LNCS 4004, pp. 1-11, Springer, 2006

(2013/08/27 4:23), Laura Hitt wrote:
> 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:[e-mail]]
> Sent: Thursday, July 25, 2013 4:38 AM
> To: Laura Hitt
> Cc: [e-mail]
> 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
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> --
> Kohei Kasamatsu
>
> NTT Software Corporation
> E-mail: [e-mail]
>
>
>


--
Kohei KASAMATSU

NTT Software Corporation
E-mail: [e-mail]