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

Kohei Kasamatsu <kasamatsu.kohei@po.ntts.co.jp> Wed, 09 October 2013 07:52 UTC

Return-Path: <kasamatsu.kohei@po.ntts.co.jp>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7278221F9E48 for <cfrg@ietfa.amsl.com>; Wed, 9 Oct 2013 00:52:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.399
X-Spam-Level: *
X-Spam-Status: No, score=1.399 tagged_above=-999 required=5 tests=[BAYES_05=-1.11, HELO_EQ_JP=1.244, HOST_EQ_JP=1.265]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pJQEDLSe0EIg for <cfrg@ietfa.amsl.com>; Wed, 9 Oct 2013 00:52:19 -0700 (PDT)
Received: from mail12.ics.ntts.co.jp (mail12.ics.ntts.co.jp [210.232.35.65]) by ietfa.amsl.com (Postfix) with ESMTP id 1E9A521E80F2 for <cfrg@irtf.org>; Wed, 9 Oct 2013 00:52:18 -0700 (PDT)
Received: from sadoku34.silk.ntts.co.jp (sadoku34 [10.7.18.34]) by mail12.ics.ntts.co.jp (8.14.4/8.14.4/NTTSOFT) with ESMTP id r997qDNt027728; Wed, 9 Oct 2013 16:52:13 +0900 (JST)
Received: (from root@localhost) by sadoku34.silk.ntts.co.jp (8.13.8/NTTSOFT) id r997qD7K002018; Wed, 9 Oct 2013 16:52:13 +0900 (JST)
Received: from ccmds32.silk.ntts.co.jp [10.107.0.32] by sadoku34.silk.ntts.co.jp with SMTP id SAA02017; Wed, 9 Oct 2013 16:52:13 +0900
Received: from mail147.silk.ntts.co.jp (ccmds32.silk.ntts.co.jp [127.0.0.1]) by ccmds32.silk.ntts.co.jp (8.14.3/8.14.3) with ESMTP id r997qCcc003523; Wed, 9 Oct 2013 16:52:12 +0900
Received: from mail147.silk.ntts.co.jp (localhost.localdomain [127.0.0.1]) by mail147.silk.ntts.co.jp (8.14.5/8.14.5/NTTSOFT) with ESMTP id r997q9d8008160; Wed, 9 Oct 2013 16:52:09 +0900
Received: from ccmds32 (mail145.silk.ntts.co.jp [10.107.0.145]) by mail147.silk.ntts.co.jp (8.14.5/8.14.5/NTTSOFT) with SMTP id r997q9H7008157; Wed, 9 Oct 2013 16:52:09 +0900
Message-ID: <52550B15.80806@po.ntts.co.jp>
Date: Wed, 09 Oct 2013 16:51:49 +0900
From: Kohei Kasamatsu <kasamatsu.kohei@po.ntts.co.jp>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8
MIME-Version: 1.0
To: lhitt@21ct.com
Content-Type: text/plain; charset=ISO-2022-JP
Content-Transfer-Encoding: 7bit
X-CC-Mail-RelayStamp: CC-Mail-V4.3-Client
X-CC-Mail-RelayStamp: CC-Mail-V4.3-Server
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] request for comments: ZSS Short Signature Scheme for SS and BN Curves
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 09 Oct 2013 07:52:29 -0000

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:kasamatsu.kohei@po.ntts.co.jp]
> Sent: Wednesday, September 18, 2013 9:38 PM
> To: Laura Hitt
> Cc: cfrg@irtf.org
> 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