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

[Kohei Kasamatsu <[e-mail]>]

Hi Laura,


Thank you for your email.
I explain my opinion against your comments below.

In first, I explain relation between ZSS signature and hardness of k-CAA
and k-wCDHP.
Theorem 3 of [1] showed that If q_s-CAA is hard ZSS signature satisfies
standard security required by signature, where q_s is the number of
pairs of signature and message which adversary can obtain.
Theorem 4 of [1] showed (k-1)-wCDHP and k-CAA are polynomial time
equivalent. That is, if there exists algorithm which can solve k-CAA
there exists algorithm which can solve (k-1)-wCDHP and vice versa.
([2] proved the theorem 4)

(k-1)-wCDHP is as follows.
input: P, yP, y^2 P, ..., y^k P
output: y^{-1} P
Hence we can apply cheon algorithm to (k-1)-wCDHP and improve its
efficiency to solve this problem.
it also means improvement of efficiency to solve k-CAA problem because
of theorem 4.

Next, I explain my opinion against what you pointed out by mapping above
explanation into real world.
(If my response is beside away from your point, please let me know. )
The adversary can transform k-CAA problem based on signature 1...k into
(k-1)-wCDHP by reduction algorithm of [2] and apply it to cheon
algorithm to obtain a secret key.
Hence I think that we can apply cheon algorithm to ZSS signature.

I would like to leave it to you whether adding the description on cheon
algorithm into your draft or not because cheon algorithm cannot break
ZSS signature in the sense of asymptotic security.
Of course, please let me know if you have further questions or concerns.


[1] Fangguo Zhang, Reihaneh Safavi-Naini, and Willy Susilo. Public Key
     Cryptography, volume 2947 of Lecture Notes in Computer Science,
     page 277-290. Springer, (2004)

[2] S. Mitsunari, R. Sakai and M. Kasahara, A new traitor tracing,
     IEICE Trans. Vol. E85-A, No.2, pp.481-484, 2002.

Best,
Kohei KASAMATSU

(2013/09/24 5:57), Laura Hitt wrote:
> 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