[Cfrg] Review of draft-irtf-cfrg-zss*

Watson Ladd <watsonbladd@gmail.com> Tue, 24 December 2013 17:39 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9FA331AE016 for <cfrg@ietfa.amsl.com>; Tue, 24 Dec 2013 09:39:28 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.7
X-Spam-Level:
X-Spam-Status: No, score=0.7 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
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 F-tcmOUOWSPb for <cfrg@ietfa.amsl.com>; Tue, 24 Dec 2013 09:39:27 -0800 (PST)
Received: from mail-wi0-x233.google.com (mail-wi0-x233.google.com [IPv6:2a00:1450:400c:c05::233]) by ietfa.amsl.com (Postfix) with ESMTP id DFB521ADFD4 for <cfrg@irtf.org>; Tue, 24 Dec 2013 09:39:26 -0800 (PST)
Received: by mail-wi0-f179.google.com with SMTP id z2so7497335wiv.0 for <cfrg@irtf.org>; Tue, 24 Dec 2013 09:39:22 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=OlIg6hUzfbRMDvd2VGbAZdKxTTLaPg9A2XoGnW9nvqM=; b=Mgc6zeZLTEwf1ob3cpYH2M8NcAQG9YpJ/rytzs1UZT7k9lb/I7KXcizmG1PdISF21w GsEz07XX8GY5zpnngcZZdN+LL3AhAwmN1T4Sl+2lbPem7bGWgzyUpoLvQ3vqtTTGen9n zC/i04vj+Q7S4W7Fbjz97eA4T+LC+Ak3HyCwIFNVb7ZDM+iwwq0+MTT0I+3Ov/VcAMoh kkg0U/xN0iqQYmZD9p2VZMVd2tUjIh84axt81Zbe/Jek/LTFiDyYgJKcRSzCOJtgITJ0 kLnaqDjJk5ifUOTq2vH0t6oboDP6c9b4lR4bfYfgRg8wkr2HZzwHr8DEjfr73MWzbUgk rH7Q==
MIME-Version: 1.0
X-Received: by 10.180.95.162 with SMTP id dl2mr23677506wib.17.1387906762644; Tue, 24 Dec 2013 09:39:22 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Tue, 24 Dec 2013 09:39:22 -0800 (PST)
Date: Tue, 24 Dec 2013 12:39:22 -0500
Message-ID: <CACsn0ck4owb1zF+jbBbFvSYMpZN=BZoewO_xcOcNfA_wAcSK1A@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset=UTF-8
Subject: [Cfrg] Review of draft-irtf-cfrg-zss*
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
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: Tue, 24 Dec 2013 17:39:28 -0000

Dear all,
These two drafts define a signature scheme based on pairings over BN
and supersingular curves. Actually, the setting is a general pairing
of Type III, with no hashing to group required.
The signature scheme reduces to a k-DH style assumption in the ROM,
and I haven't cooked up a dirty hash that can break it. Intermediate
assumptions on the hash function to get a reduction are open. This is
not a Fiat-Shamir transform of a ZKP, so the standard heuristics are
not quite sufficient.

The standardization does not pick a curve or a hash.

There is a typo that leads to the representation of points on E' not
being defined: F_p in that section should be replaced by "any field".

Supersingular curves have small embedding degree: this forces the use
of uncompetitively large primes.

BN curves have embedding degree 12. This means a tower of degree 3,
then 4. In such a tower the discrete logarithm problem can be solved
quicker than over a prime field of the same size. I am currently
searching the literature for the exact coefficients, but I do not feel
the table in the draft is correct.

This signature scheme promises shorter signatures than schemes of
schnorr-style. However, in practice the failure to use point
compression means Ed25519 is shorter. It's also much faster to verify,
as pairings are expensive.

If the k-DH complexity and discrete log complexities can be tied down
better, I would have no objection to publishing this as an RFC.

Sincerely,
Watson Ladd