Re: [Cfrg] request for comments: ZSS Short Signature Scheme for SS and BN Curves
Kohei Kasamatsu <kasamatsu.kohei@po.ntts.co.jp> Thu, 19 September 2013 02:39 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 236CF11E817F for <cfrg@ietfa.amsl.com>; Wed, 18 Sep 2013 19:39:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.51
X-Spam-Level: **
X-Spam-Status: No, score=2.51 tagged_above=-999 required=5 tests=[BAYES_50=0.001, 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 d-uqiCVP8Yy6 for <cfrg@ietfa.amsl.com>; Wed, 18 Sep 2013 19:38:59 -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 13AEA11E80D7 for <cfrg@irtf.org>; Wed, 18 Sep 2013 19:38:58 -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 r8J2crKB000118; Thu, 19 Sep 2013 11:38:53 +0900 (JST)
Received: (from root@localhost) by sadoku34.silk.ntts.co.jp (8.13.8/NTTSOFT) id r8J2crpg002771; Thu, 19 Sep 2013 11:38:53 +0900 (JST)
Received: from ccmds32.silk.ntts.co.jp [10.107.0.32] by sadoku34.silk.ntts.co.jp with SMTP id MAA02770; Thu, 19 Sep 2013 11:38:53 +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 r8J2crWK014850; Thu, 19 Sep 2013 11:38:53 +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 r8J2cmfx031753; Thu, 19 Sep 2013 11:38:48 +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 r8J2cmFw031750; Thu, 19 Sep 2013 11:38:48 +0900
Message-ID: <523A6393.60407@po.ntts.co.jp>
Date: Thu, 19 Sep 2013 11:38:11 +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: Laura Hitt <lhitt@21ct.com>
References: <04920BD67C651C469D0387704CD7692A74B0844B94@21ct-exg07.21technologies.com> <51F0F1E6.5080505@po.ntts.co.jp> <04920BD67C651C469D0387704CD7692A801128D84A@21ct-exg07.21technologies.com>
In-Reply-To: <04920BD67C651C469D0387704CD7692A801128D84A@21ct-exg07.21technologies.com>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
X-CC-Mail-RelayStamp: CC-Mail-V4.3-Client
X-CC-Mail-RelayStamp: CC-Mail-V4.3-Server
Content-Transfer-Encoding: quoted-printable
X-MIME-Autoconverted: from 8bit to quoted-printable by ccmds32.silk.ntts.co.jp id r8J2crWK014850
Cc: "cfrg@irtf.org" <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: Thu, 19 Sep 2013 02:39:03 -0000
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: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 > > > -- Kohei KASAMATSU NTT Software Corporation E-mail: kasamatsu.kohei@po.ntts.co.jp
- [Cfrg] request for comments: ZSS Short Signature … Laura Hitt
- Re: [Cfrg] request for comments: ZSS Short Signat… Igoe, Kevin M.
- Re: [Cfrg] request for comments: ZSS Short Signat… Kohei Kasamatsu
- Re: [Cfrg] request for comments: ZSS Short Signat… Laura Hitt
- Re: [Cfrg] request for comments: ZSS Short Signat… Kohei Kasamatsu
- Re: [Cfrg] request for comments: ZSS Short Signat… Laura Hitt
- Re: [Cfrg] request for comments: ZSS Short Signat… Kohei Kasamatsu