Re: [Pqc] [Ext] [WG last call] IETF WG state changed for draft-ietf-pquip-pqt-hybrid-terminology

[Wang Guilin <[e-mail]>]

Dear Peter,

Thanks for your very interesting comments, Please see my feedback below.

>I don't believe the term "traditional cryptographic algorithm" is intended to be the exact opposite of "post-quantum algorithm".
>My understanding is that it is only supposed to cover quantum-vulnerable public-key algorithms that are in widespread use today, not new or niche algorithms.
>If someone found a quantum attack on Falcon, for example, it shouldn't become a "traditional cryptographic algorithm".

My feedback:

1) If "traditional cryptographic algorithm" and "post-quantum algorithm" are not the opposite in logic to each other, how should call the things they overlap or the things neither of them covers?

2) According to your concept of "traditional cryptographic algorithm", you mean it is "in widespread use today, not new or niche algorithms". However, it is hard to qualtify "widespread use, new or niche". For examples, given algorithms used in an organization, in a sector of a country, or a country, which one can be treated as "widespread used"? Similar, given algorithms designed in 1983, 1993, 2003, 2013, and 2023, which of them are "new" and which are not "new"? It is the same case for "niche".

In my understanding, here "traditional" means the approache used to design the scheme, i.e, based on hard math question and targeted to achieve security against classic comptuers. It does not really matter if the algorithm is widespread used or not, new or not, niche or not, even secure or not (for some quite long time, this may be not clear).

3) So, back to your Falcon example, if someone found a quantum attack on Falcon,  it can become a "traditional cryptographic algorithm", in my understanding, though it has been considered as PQC algorithm. Similar case happened in classification of plans and animals. Some species may be classified in category A, latter to category B, once people have learn more about the
species.

4) Now come back to the definition of "traditional cryptographic algorithm", there is no scientific evidence showing that they can be constructed only from factoring or DL and the relevant math questions. So, how can we just simply exclude the possility (the existence) of PKC schemes that are targeting quantum threat? We do not need such a risk in logic.


> I don't think the Algebraic Eraser(TM) is a good argument for expanding the definition either.
> This was claimed to be post-quantum (see section 2.2 of the AEAKP paper), but several versions have been broken classically (see the "known attacks" section of the Wikipedia article).

5) Good points! Yesterday, I also read the AEAKP introduction paper. It did mention that no known quantum attacks on AEAKP (as the authors know).

But there are several schemes proposed  before AEAKP, which are based braid or relevant problems and seem not targeting to achelieve security against quantum computers. So, these can be examples.

Of course, any other more popular example will be better, if anyone know.

Cheers,

Guilin

________________________________

Wang Guilin
Mobile: [phone]
Email: [e-mail]

From:Peter C <[e-mail]<mailto:[e-mail]>>
To:Wang Guilin <Wang.Guilin=[e-mail]<mailto:Wang.Guilin=[e-mail]>>;Flo D <Flo.D=[e-mail]<mailto:Flo.D=[e-mail]>>;pqc <[e-mail]<mailto:[e-mail]>>
Cc:Wang Guilin <[e-mail]<mailto:[e-mail]>>
Date:2024-03-05 18:39:31
Subject:RE: [Pqc] [Ext] [WG last call] IETF WG state changed for draft-ietf-pquip-pqt-hybrid-terminology

Guilin,

I don't believe the term "traditional cryptographic algorithm" is intended to be the exact opposite of "post-quantum algorithm". My understanding is that it is only supposed to cover quantum-vulnerable public-key algorithms that are in widespread use today, not new or niche algorithms. If someone found a quantum attack on Falcon, for example, it shouldn't become a "traditional cryptographic algorithm".

I don't think the Algebraic Eraser(TM) is a good argument for expanding the definition either. This was claimed to be post-quantum (see section 2.2 of the AEAKP paper), but several versions have been broken classically (see the "known attacks" section of the Wikipedia article).

Peter

> -----Original Message-----
> From: Pqc <[e-mail]<mailto:[e-mail]>> On Behalf Of Wang Guilin
> Sent: Monday, March 4, 2024 11:18 AM
> To: Flo D <Flo.D=[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
> Cc: Wang Guilin <[e-mail]<mailto:[e-mail]>>
> Subject: Re: [Pqc] [Ext] [WG last call] IETF WG state changed for draft-ietf-
> pquip-pqt-hybrid-terminology
>
> [Some people who received this message don't often get email from
> wang.guilin=[e-mail]<mailto:[e-mail]>. Learn why this is important at
> https://aka.ms/LearnAboutSenderIdentification ]
>
> Dear Flo and all,
>
> I am happy to support adoption of draft-ietf-pquip-pqt-hybrid-terminology.
>
> I have read the draft several times and also given my feedback. So, from my
> viewpoint, the content seems quite good now.
>
> ======================
> About this version, my detailed comment is still on the definition of
> *Traditional Cryptographic Algorithm*. Namely, it seems still too narrow, not
> exactly the opposite of *Post-Quantum Algorithm*.
>
> Here is the current definition:
>
> "*Traditional Cryptographic Algorithm*: An asymmetric cryptographic
> algorithm based on integer factorisation, finite field discrete logarithms,
> elliptic curve discrete logarithms, or related mathematical problems."
>
> Happy to see this definition has been extended as asymmetric cryptographic
> algorithm based on factoring, DL or related mathematical problems, not just
> schemes based on factoring and DL problems, after communication with Flo.
> However, it seems still narrow. Namely, in logic, how can we show or conclude
> that Traditional Cryptographic Algorithms have only been built and also will
> be built only on factoring and DL related mathematical problems? A more
> natural definition may be something like the following (using similar
> expression for defining *Post-Quantum Algorithm* in [draft-ietf-pquip-pqt-
> hybrid-terminology]):
>
> *Traditional Cryptographic Algorithm*: An asymmetric cryptographic
> algorithm that is designed to secure against attacks using classical computers,
> but not quantum computers. The representatives are
> cryptographic algorithms based on integer factorisation, finite field discrete
> logarithms, elliptic curve discrete logarithms, or related mathematical
> problems. For example, RSA, ECDSA, ECDH.
>
> In fact, this is similar for us not saying that Post-Quantum Algorithms just
> belong to five categories, as this is just what we have seen now. So, in future,
> some categories of Post-Quantum Algorithms may appear. Actually, this could
> happen to Traditional Cryptographic Algorithm as well. Namely, it is possible
> that someone may propose some totally new Traditional Cryptographic
> Algorithm based some new hard problem in the future.
>
> Another way to justify why the concept may need to be extended as the
> above is to show the existence of at least Traditional Cryptographic Algorithm,
> which is not based on factoring, DL or related mathematical problems.
> Especially, it will be even better if the algorithm is a standard or has been
> considered for standardization.
>
> For this purpose, I have checked this issue with a number of professors. Then,
> such an algorithm comes out: It is Algebraic Eraser (AE) Key Agreement
> Protocol (AEKAP). According to my quick check, I think AEKAP is a Traditional
> Cryptographic Algorithm, but not based on factoring, DL or related
> mathematical problems.
>
> Below is some related from WiKi and other sources for reference (I am not an
> expert on AEKAP and the related mathematical prolems):
>
________________________________

> 1) Info from
> https://en.wiki/
> pedia.org%2Fwiki%2FAlgebraic_Eraser&data=05%7C02%7CPeter.C%40ncsc.go
> v.uk%7C6adac9ac61a04bbf7ba208dc3c3cc6a9%7C14aa5744ece1474ea2d734f
> 46dda64a1%7C0%7C0%7C638451479193416871%7CUnknown%7CTWFpbGZs
> b3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn
> 0%3D%7C0%7C%7C%7C&sdata=02uv7Al3cySHxOgZVdN0I%2FWdNNN6Oo3zf
> yLA81JZhHI%3D&reserved=0:
>
> "Algebraic Eraser (AE)[note 1] is an anonymous key agreement protocol that
> allows two parties, each having an AE public-private key pair, to establish a
> shared secret over an insecure channel.[1] This shared secret may be directly
> used as a key, or to derive another key that can then be used to encrypt
> subsequent communications using a symmetric key cipher. Algebraic Eraser
> was developed by Iris Anshel, Michael Anshel, Dorian Goldfeld and Stephane
> Lemieux. SecureRF owns patents covering the protocol[2] and unsuccessfully
> attempted (as of July 2019) to standardize the protocol as part of ISO/IEC
> 29167-20,[3] a standard for securing radio-frequency identification devices
> and wireless sensor networks.
>
> The security of AE is based on the Generalized Simultaneous Conjugacy
> Search Problem (GSCSP)[4] within the braid group. This is a distinct and
> different hard problem than the Conjugacy Search Problem (CSP), which has
> been the central hard problem in what is called braid group cryptography.[5]
> Even if CSP is uniformly broken (which has not been done to date), it is not
> known how this would facilitate a break of GSCSP."
>
> 2. AEAKP once considered in IETF.
> Using Algebraic Eraser (AEDH) in OpenPGP
> https://datatra/
> cker.ietf.org%2Fdoc%2Fhtml%2Fdraft-atkins-openpgp-algebraic-eraser-
> 05&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7C6adac9ac61a04bbf7ba208d
> c3c3cc6a9%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C6384514
> 79193424679%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQ
> IjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=tD
> HXr0joVmVFTX%2BN2evBQbmMVo98R3gOGj31nNjhbqU%3D&reserved=0
>
> 3. A paper on AEAKP
> Algebraic EraserTM: A lightweight, efficient asymmetric key agreement
> protocol for use in no-power, low-power, and IoT devices.
> https://csrc.nis/
> t.gov%2Fcsrc%2Fmedia%2Fevents%2Flightweight-cryptography-workshop-
> 2015%2Fdocuments%2Fpapers%2Fsession8-atkins-
> paper.pdf&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7C6adac9ac61a04bbf7
> ba208dc3c3cc6a9%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C6
> 38451479193430540%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwM
> DAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&s
> data=fFMi4mEl6gKVJSB9KGI7Zn%2FdwDkJQ0Y%2BznmLN99RNrQ%3D&reserv
> ed=0
>
________________________________

> ======================
>
> Guilin
>
> -----Original Message-----
> From: Pqc <[e-mail]<mailto:[e-mail]>> On Behalf Of Flo D
> Sent: Monday, 4 March 2024 4:53 pm
> To: [e-mail]<mailto:[e-mail]>
> Subject: Re: [Pqc] [Ext] [WG last call] IETF WG state changed for draft-ietf-
> pquip-pqt-hybrid-terminology
>
> Hi PQUIP,
>
> Thanks Paul and Sofía for this last call. I'd like to second Paul's call to the
> group to use this as an opportunity to review the draft. Even if you don't
> think the draft still needs more time, I think it's vital that we "bank" some of
> the definitions sooner rather than later. We need to do that so that the
> protocol drafts that refer to this draft, and that will start to get published once
> NIST have finalised their standards, can rely on the definitions that are
> included here.
>
> Thanks in advance,
> Flo
>
> -----Original Message-----
> From: Pqc <[e-mail]<mailto:[e-mail]>> On Behalf Of Paul Hoffman
> Sent: Friday, March 1, 2024 5:57 PM
> To: [e-mail]<mailto:[e-mail]>
> Subject: Re: [Pqc] [Ext] [WG last call] IETF WG state changed for draft-ietf-
> pquip-pqt-hybrid-terminology
>
> A strong nudge that this document is in WG Last Call and needs a bunch more
> reviews, even if they just say "that's all fine".
>
>
> On Feb 21, 2024, at 07:31, Sofía Celi <[e-mail]<mailto:[e-mail]>> wrote:
>
> > Hi,
> >
> > This email starts the working group last call for "Terminology for Post-
> Quantum Traditional Hybrid Schemes" I-D, located here:
> >
> >
> https://datatra/
> cker.ietf.org%2Fdoc%2Fdraft-ietf-pquip-pqt-hybrid-
> terminology%2F&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7C6adac9ac61a
> 04bbf7ba208dc3c3cc6a9%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C
> 0%7C638451479193435579%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wL
> jAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%
> 7C&sdata=duA%2BYwYH4Y3m3E2Tf7NS7qbEVIyBLGPTmem6uDJiLHI%3D&res
> erved=0
> >
> > The WG Last Call will end 6th March 2024 @ 2359 UTC.
> >
> > Please review the I-D and submit any comments to the [e-mail]<mailto:[e-mail]> mailing
> list.
>
>
> --
> Pqc mailing list
> [e-mail]<mailto:[e-mail]>
> https://www.ie/
> tf.org%2Fmailman%2Flistinfo%2Fpqc&data=05%7C02%7CPeter.C%40ncsc.gov.
> uk%7C6adac9ac61a04bbf7ba208dc3c3cc6a9%7C14aa5744ece1474ea2d734f4
> 6dda64a1%7C0%7C0%7C638451479193440039%7CUnknown%7CTWFpbGZsb
> 3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0
> %3D%7C0%7C%7C%7C&sdata=furpJv7SPgtKxuPU43gED1Y4OBBKaDHo8LaV61
> EvNXE%3D&reserved=0
>
> --
> Pqc mailing list
> [e-mail]<mailto:[e-mail]>
> https://www.ie/
> tf.org%2Fmailman%2Flistinfo%2Fpqc&data=05%7C02%7CPeter.C%40ncsc.gov.
> uk%7C6adac9ac61a04bbf7ba208dc3c3cc6a9%7C14aa5744ece1474ea2d734f4
> 6dda64a1%7C0%7C0%7C638451479193444108%7CUnknown%7CTWFpbGZsb
> 3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0
> %3D%7C0%7C%7C%7C&sdata=3rXSA6PwEb3t1riO2OFpfeT7pP1ihcPmOv2Heh
> Fsr3A%3D&reserved=0
>
> --
> Pqc mailing list
> [e-mail]<mailto:[e-mail]>
> https://www.ie/
> tf.org%2Fmailman%2Flistinfo%2Fpqc&data=05%7C02%7CPeter.C%40ncsc.gov.
> uk%7C6adac9ac61a04bbf7ba208dc3c3cc6a9%7C14aa5744ece1474ea2d734f4
> 6dda64a1%7C0%7C0%7C638451479193448764%7CUnknown%7CTWFpbGZsb
> 3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0
> %3D%7C0%7C%7C%7C&sdata=aXVhH1c5YeWO6frbPbBAqFhE%2BEYSysKSCKB
> GdboC5Co%3D&reserved=0