[Cfrg] Point compression that removes cofactor

Michael Hamburg <mike@shiftleft.org> Mon, 08 December 2014 22:40 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 0C9BE1A006D for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 14:40:51 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3.454
X-Spam-Level: ***
X-Spam-Status: No, score=3.454 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id TI7QSmwrBm7F for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 14:40:50 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E837E1A0062 for <cfrg@irtf.org>; Mon, 8 Dec 2014 14:40:49 -0800 (PST)
Received: from [] (unknown []) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 4E3713AA43 for <cfrg@irtf.org>; Mon, 8 Dec 2014 14:40:08 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1418078408; bh=lj8PPWpTe4Op+qNpZGnoZ4o1/ann2bRYKLDEiZNQ9So=; h=From:Subject:Date:To:From; b=FXuJlWdwbHkjIg9QnsfwKmEo1fA2rJjKEjpqa6agUKoPhHJ4I0RouoGePEftFgRAf 3DbTKZiV3IgoP2q6ALOpKlACbvztOxyFF1Lcro8HflMs5T1GWkoZ2BDBeDUY/D10Qq hbA8sLp5XUlrO8AKlABs8EBCSSk1xQk1qOx9wh1M=
From: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Message-Id: <6C2CCEB7-4421-4912-8B53-581B00C515F7@shiftleft.org>
Date: Mon, 8 Dec 2014 14:40:46 -0800
To: IRTF Crypto Forum Research Group <cfrg@irtf.org>
Mime-Version: 1.0 (Mac OS X Mail 8.1 \(1993\))
X-Mailer: Apple Mail (2.1993)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/_li8LQGHIDXXODpJSUDUDUis-Xw
Subject: [Cfrg] Point compression that removes cofactor
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: Mon, 08 Dec 2014 22:40:51 -0000


I’m trying to cook up a point compression/encoding system which removes the cofactor of cofactor-4 Edwards, twisted Edwards, Montgomery, generalized Huff and Jacobi Quartic curves.

Hypothetically, let’s suppose that the point compression format works, and it isn’t horribly complicated or easy to screw up, and it performs almost as well as the usual compression formats, and it masks the incompleteness of the a=-1 twisted Edwards formulae.

Proponents of cofactor-1 curves, would this mitigate the problems you see in those curves?  It would still require new code, both for the curve implementations and the compression format, but would you consider it to remove your protocol-level concerns?

— Mike