Return-Path: 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 4D3501204EB for ; Mon, 1 Apr 2019 11:30:38 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.6 X-Spam-Level: X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no 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 PAeZQMQW8yR3 for ; Mon, 1 Apr 2019 11:30:35 -0700 (PDT) Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EA3F51204CE for ; Mon, 1 Apr 2019 11:30:34 -0700 (PDT) Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs214cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 01 Apr 2019 14:30:33 -0400 Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT102CNC.rim.net ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0415.000; Mon, 1 Apr 2019 14:30:33 -0400 From: Dan Brown To: "Blumenthal, Uri - 0553 - MITLL" , "Paterson Kenneth" , Marek Jankowski , "yonezawa@lepidum.co.jp" CC: CFRG Thread-Topic: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt Thread-Index: AQHU2Yg9d9ockWZnDkeyn6LWng9bQKYLg1EAgAA63ACABtxrAIACXiwAgAwGegCAAD6YAP//creAgADJWQCAAabZAIAAENIAgARbhvA= Date: Mon, 1 Apr 2019 18:30:32 +0000 Message-ID: <810C31990B57ED40B2062BA10D43FBF501DB4A31@XMB116CNC.rim.net> References: <155231848866.23086.9976784460361189399@ietfa.amsl.com> <737ea2b3-74e3-d02e-a44d-c44cca5db036@lepidum.co.jp> <7AE82BE8-768D-4B70-B7F1-EAF6894E428E@ll.mit.edu> <9CABDAD4-AAB7-46BF-BED7-6A917F828F11@inf.ethz.ch> <27F5D9B6-A44D-4A12-B81D-C4FB01052113@ll.mit.edu> In-Reply-To: <27F5D9B6-A44D-4A12-B81D-C4FB01052113@ll.mit.edu> Accept-Language: en-US, en-CA Content-Language: en-US X-MS-Has-Attach: yes X-MS-TNEF-Correlator: x-originating-ip: [10.65.160.251] Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=2.16.840.1.101.3.4.2.1; boundary="----=_NextPart_000_01B0_01D4E897.75828220" MIME-Version: 1.0 Archived-At: Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 01 Apr 2019 18:30:39 -0000 ------=_NextPart_000_01B0_01D4E897.75828220 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable The topic of non-PQ crypto's value applies to other CFRG drafts, such as = PAKEs, VRFs, Oblivious functions, etc., so maybe this discussion should = be taken outside this thread? Non-PQ crypto still seems worthwhile to me, mainly because I estimate = the chance of a practical ECC-breaking quantum computer to be low, e.g. = 2^(-10), yet still high enough to warrant a hybrid of PQ and non-PQ = crypto, e.g. McEliece + ECC. (See further below.) > -----Original Message----- > From: Cfrg On Behalf Of Blumenthal, Uri - 0553 = - > MITLL >=20 > It doesn=E2=80=99t but we did already discuss that, and good arguments = were put forth > for continuing the work despite this. (See the mail archive, I guess.) >=20 > So far I=E2=80=99ve found this (which IMHO doesn't look like a set of = good arguments): >=20 > > 1) Pairing-based crypto threw open the doors to lots of nice new = crypto > possibilities, enabling stuff that we couldn't do before > > 2) Gradually post-quantum crypto is catching up and demonstrating > capabilities that mirror some (but not all) of these achievements > > 3) Post-quantum crypto depends on hard problems that it will take = time to > develop full confidence in, even in regard to attacks from non- > quantum computers > > 4) In the meantime (and that could be quite a long time) it makes = perfect > sense to proceed with the development and standardization > > of non-quantum safe methods. > > 5) In the year x out pops a quantum computer. However in the year = x-1 out > popped well-developed and well-understood > > post-quantum crypto replacements in which we can have complete > confidence. >=20 > Re. (1): sure, it would do great stuff, but for how long? = What=E2=80=99s the expected > lifetime of an algorithm/protocol/approach that would justify efforts = spent on > formalizing, implementing, and deploying it? What application field or = use case > would support it? >=20 > Re. (2) and (3): sure, but irrelevant with regard to the main question = - is it > worth developing (for deploying later, as there's an inevitable lag) = non- > quantum-resistant crypto now? It would be smart to answer these types questions with quantified = support, but all I get so far is the na=C3=AFve estimates below. = (Presumably, experts have already documented more sophisticated = reasoning, maybe see ia.cr/2015/1018). For simplicity, consider any crypto as broken or not (at some attack = cost and success rate), and then compare 3 alteratnives: ECC, McEliece = (McC), and their hybrid (in the strongest link sense). Define five event probabilities, but please replace my personal = (ultra-low-confidence) estimates with your own: Break ECC classically: e ~ 2^-40 Break ECC quantumly: E =3D 1 [Shor] Build quantum computer: Q ~ 2^-10 [(Mosca's estimate =3D 1/2) ^ = (my_grain_of_salt ~ see also cold fusion:)] Break McC classically: m ~ 2^-20=20 Break McC quantumly: M ~ 2^-20 Assuming e,E,Q,m,M independent (in the usual sense that their products = are the probabilities of intersection of corresponding events), deduce 3 = event probabilities: Break ECC: X =3D e+Q-eQ. Break McC: Y =3D m+MQ-mMQ. Break hybrid ECC+McC: Z =3D mX+Y-m =3D em+mQ+MQ-emQ-mMQ. For brevity, I omit the tedious derivations. Assuming X,Y,Z correct: If Q=3D1, then X=3D1 and Z=3DY, so ECC is essentially redundant (out = with old...). If Q=3D0, then X=3De and Z=3DXY, which means that hybrid is generally = better (see * below) than either individual crypto, and the lower of X = and Y (ECC in my estimation) can be considered as the main contributor = to the lowness of Z. (*) Assume 0 < X,Y < 1. Ignore the issue of declining returns for very = low probabilities, e.g. X=3D2^-128 might be just as good as Z=3D2^-256 = (who needs new?). For 0 < Q < 1, then the conclusions smoothly vary between the two = extremes (Q=3D0) and (Q=3D1) above. =20 My (e,Q,m,M) estimates lead to an estimate (X,Y,Z) ~ 2^-(10,-20,-30). I = admit to using my (biased?) intuition for the ordering X