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