Re: [Cfrg] Compression of tori in draft-irtf-cfrg-pairing-friendly-curves-02

Yumi Sakemi <yumi.sakemi@lepidum.co.jp> Fri, 27 March 2020 11:39 UTC

Return-Path: <yumi.sakemi@lepidum.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 BD6FE3A0827 for <cfrg@ietfa.amsl.com>; Fri, 27 Mar 2020 04:39:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=lepidum-co-jp.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id V38QOSB-LbSS for <cfrg@ietfa.amsl.com>; Fri, 27 Mar 2020 04:39:53 -0700 (PDT)
Received: from mail-lj1-x231.google.com (mail-lj1-x231.google.com [IPv6:2a00:1450:4864:20::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1002D3A07AE for <cfrg@irtf.org>; Fri, 27 Mar 2020 04:39:52 -0700 (PDT)
Received: by mail-lj1-x231.google.com with SMTP id f20so9880663ljm.0 for <cfrg@irtf.org>; Fri, 27 Mar 2020 04:39:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lepidum-co-jp.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=q1XfoOK/hcEY0XQvoiY+qsgXhtUCRR5ei/J1batkm9I=; b=XutUkgDCchxOm1bNxQ+DjnNX9UXKgkC+v9Se/4dIR+Tn76r/hDgYFtIPhyLWHX+0SX F1+CaFklM5WCaAB6GOwo0wkhCEJ7Ayol1Wm2SZ4ntaoFlpCFxeG0F2s1RgIS5G09mSBC 7p37oS0FDnuGN19pmqczwzO6CjMwV1ZOjNr8rkEvm/FvPKEjPEjHmqYpvlzi91ep5IAb 5CTTP/mtDL5+jsMPcD2KTw62TZNGOk3v7X1S9KxL8uv3EBk2y1KhHLQQ1ExBDPGAlEwg Ex0TXMnVm1Q88leRFgLZ8eb9psnmmHVJRXKc+0gg9SVdXVDTTZ8Uly3r/WQRvf5vuJjo peUg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=q1XfoOK/hcEY0XQvoiY+qsgXhtUCRR5ei/J1batkm9I=; b=N0drV/1JG0uIdIshtep78OvH/4+pUdIBc1ZoOCDlw0tlaMPJHjcM63WBKTIPBd74At pitNFBId6cYCAkfWQWNTHX8f95/GoN+ANcN8o7mq3wKD0ofJ7k4XgHfcBS2+r9fTaGo7 T/hp1B64RXTTb1bwsRxhtCgrBb+6ckILzzhXNDmuJkBQIhgMwSjekgWhIpBnZCi6oWuJ mtsBeUw3o/2QH1SMVb81BAwbqn/ST7CRZxA2SDeo4hkzr27FX3X6U+0clSG2Xrgiqh+1 9BL/161yZHhoKoJ2FrybAQg6s7whlVCBEflhD6WGhB+csRCcaPxlTpyJ5NF8UP5h5gpp mVhQ==
X-Gm-Message-State: AGi0PuZ9pnIY/kRPmjlaibvSOb1iKgKcyAi412VsB3VP1Pa1hfQsunt5 UMhonXNBsHo0vJV64UvrMhXpUyFDIDP5+7F1iF8Fxg==
X-Google-Smtp-Source: ADFU+vuXEeSMcKUTAln5AUe637afs2ELgwmObTvsICbRFZh781dLvvu5ydnriyRTLKE80dEqywbTMiYV/HyL14LprqQ=
X-Received: by 2002:a2e:9e16:: with SMTP id e22mr8575824ljk.220.1585309190878; Fri, 27 Mar 2020 04:39:50 -0700 (PDT)
MIME-Version: 1.0
References: <CAN2QdAEe+sduY8nUnPDCTUQa=06QB1Zwavo_=-kA5opBNL6_Yg@mail.gmail.com> <CAA4D8KawB4mni+dan==bYV+=KRs0m4J_kjsESzOyxLKE14m8rQ@mail.gmail.com>
In-Reply-To: <CAA4D8KawB4mni+dan==bYV+=KRs0m4J_kjsESzOyxLKE14m8rQ@mail.gmail.com>
From: Yumi Sakemi <yumi.sakemi@lepidum.co.jp>
Date: Fri, 27 Mar 2020 20:39:40 +0900
Message-ID: <CAA4D8KbpU8Thfm8HsU4=-vvZj9Ym3hBRVfDY1X5gtYfp3f98Jg@mail.gmail.com>
To: Watson Ladd <watson=40cloudflare.com@dmarc.ietf.org>
Cc: cfrg@irtf.org, Tetsutaro Kobayashi <tetsutaro.kobayashi.dr@hco.ntt.co.jp>, SAITO Tsunekazu <tsunekazu.saito.hg@hco.ntt.co.jp>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/9nZrR2LNRJI6hOGt7OMeiQRitXc>
Subject: Re: [Cfrg] Compression of tori in draft-irtf-cfrg-pairing-friendly-curves-02
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 27 Mar 2020 11:39:55 -0000

Dear Dr. Watson,

Thank you for your comment!
We submitted revised version.
https://mailarchive.ietf.org/arch/msg/cfrg/n45h0G-rVI4lcXuIQKDOMceqBds/

There are many ways to represent an element in extension fields.
Among them, focusing on "interoperability", we adopted Rene's
representation convention as a standard and efficient method.
His method is published as I-D at
"https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-09".

On the other hand, we understand that your recommended compression
method is more effective when application communicates elements in
extension fields.
So, we added about compression method as useful information to
developers in sec 2.5 of our draft.

Best regards,
Yumi

2020年3月21日(土) 16:29 Yumi Sakemi <yumi.sakemi@lepidum.co.jp>jp>:
>
>
> Dear Dr. Watson,
>
> Thank you for your comments.
> I'm glad you to read our draft!!
>
> The compress techniques are very interesting for us.
> According to your comments, I will discuss with co-authors and
> update our draft.
>
> Best regards,
> Yumi
>
> ---
> Yumi Sakemi, Ph. D.
> Lepidum Co. Ltd.
> E-Mail: yumi.sakemi@lepidum.co.jp
>
> 2020年3月20日(金) 6:09 Watson Ladd <watson=40cloudflare.com@dmarc.ietf.org>rg>:
>>
>> Dear all,
>>
>> In the latest draft I see that F_{p^k} is represented directly as
>> polynomials modulo an irreducible of degree k, and GT is encoded
>> accordingly. This is space inefficient.
>>
>> In most cases k is even. Let q=p^(k/2) Consider F_q[x]/(x^2+d), the
>> quadratic extension of F_{q }, and now consider the result of a
>> pairing in it. As in https://eprint.iacr.org/2004/032.pdf, it is clear
>> that the result satisfies a quadratic equation: a^2-db^2=1, where the
>> element is a+bx.
>>
>> Therefore we can send only a, which is much smaller, and ecode b as a
>> single bit.
>>
>> This technique is very useful in any protocol where an element of GT
>> must be sent.
>>
>> Sincerely,
>> Watson Ladd
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg



-- 
Yumi Sakemi, Ph. D.
Lepidum Co. Ltd.
E-Mail: yumi.sakemi@lepidum.co.jp