Re: [Pqc] PQ/T Hybrid Terminology - Basic Definitions

[Florence D <[e-mail]>]

Hi Guilin,

Thank you very much for your comments, they were very helpful.  I'll respond to both this email and your next one here to keep things together.  Picking up on your points one by one:

* Defining Traditional Cryptographic Algorithm rather than Traditional Algorithm sounds fine to me.  This does mean that we'll have a different convention for traditional and post-quantum algorithms, but I don't think that's a problem as the meaning of "Post-Quantum Algorithm" is already well understood.
* On expanding out the definition for traditional cryptographic algorithms to include those which are not based on integer factorisation or the discrete-log problem, do you have specific exclusions in mind here? I understand the desire not to unnecessarily constrain ourselves, but I also want to ensure that we're being as precise as we can, so it would be helpful to know what you're thinking of to motivate this change.
* On multi-algorithm schemes (from your other email) - I agree that the note may be too restrictive.  What I was aiming to get at was the idea that a scheme that includes e.g. a single signature and a single hash, is not a hybrid scheme because it includes multiple algorithms.  However, I think the current wording may be too strong, and I didn't intend to exclude the examples you give.  What do you think about:

	Multi-Algorithm Scheme: A cryptographic scheme which incorporates more than one component algorithm to achieve the same cryptographic outcome.

	For example, a multi-algorithm scheme may include multiple signature algorithms or multiple Public Key Encryption (PKE) algorithms.  Component algorithms could be all traditional, all post-quantum or a mixture of the two.

* On including a definition of hybrid scheme more generally, I don't think that this adds much given that the scope of the document is restricted to PQ/T Hybrid Schemes.  With the change to the multi-algorithm scheme described above (or something similar), is a further definition necessary?
 
Thank you again for your comments and for what I hope will be an interesting discussion,

Flo
 
Florence D
UK National Cyber Security Centre

From: Pqc <[e-mail]> On Behalf Of Wang Guilin
Sent: Sunday, April 30, 2023 4:30 PM
To: Mike Ounsworth <Mike.Ounsworth=[e-mail]>; Florence D <Florence.D=[e-mail]>; pqc <[e-mail]>
Cc: Wang Guilin <[e-mail]>
Subject: Re: [Pqc] PQ/T Hybrid Terminology - Basic Definitions

Hi, Florence, 

Basically, I supports your choices for the 3 terms listed and the reasons why to select them. 

However, here are some comments on the first term, i.e., Traditional Algorithm. 

1a) For a proper definition, Traditional Algorithm looks too general. In my opinion, it is better to define "Traditional Cryptographic Algorithm" rather than "Traditional Algorithm", though a note can be given to say that for short, "Traditional Cryptographic Algorithm" is also called "Traditional Algorithm". 

1b) It is better to define "Traditional Cryptographic Algorithm/Traditional Algorithm" in a general way, similar as what has been done to the definition for "Post-Quantum Algorithm", rather than giving a list of limited algorithms. 

1c) It seems not a good idea to (implicitly) say that RSA, DLP, EC-DLP based algoritms are the only traditional algorithms. In academic research, there are huge of cryptographic algorithms which were designed not to resist PQ attacks. So, these algorithms should also be classified as Traditional (Cryptographic) Algorithms, but they may be or may be not related to the above hard problems. 

In a summary, in my opinion, a better definition for 1 could be something like the following:

========
1. Traditional (Cryotographic) Algorithm: An asymmetric cryptographic algorithm that is believed to be secure against classic computers and not secure against quantum computers. For short, we call a traditional cryotographic algorithm as a taditional algorithm. 

Examples of traditional algorithms inlcude the cryptographic algorithms based on integer factorisation, finite field discrete logarithms or elliptic curve discrete logarithms. These are also the representatives of current standardized asymmetric algorithms (say, ...). However, due to the discovery of Shor algorithmb in 1994, all of these algorithms are potentially broken under quantum attacks. ...
========

Cheers, 

Guilin

________________________________________

Wang Guilin
Mobile: [phone]
Email: [e-mail]
From:Mike Ounsworth <Mike.Ounsworth=[e-mail]>
To:Florence D <Florence.D=[e-mail]>;pqc <[e-mail]>
Date:2023-04-28 21:02:00
Subject:Re: [Pqc] PQ/T Hybrid Terminology - Basic Definitions

Thanks Flo!

I'll add a meta-point about 3: I like "thing1 / thing2 hybrid" because it extends nicely to other things: I can talk about a "PQ/PQ hybrid", or a "PSK/Traditional hybrid", or a "PQ/QKD hybrid" and the meaning is clear. It's a nice qualification and disambiguation of the word "hybrid" which by itself can mean many different things within cryptography.

---
Mike Ounsworth

-----Original Message-----
From: Pqc <mailto:[e-mail]> On Behalf Of Florence D
Sent: Wednesday, April 26, 2023 9:14 AM
To: mailto:[e-mail]
Subject: [EXTERNAL] [Pqc] PQ/T Hybrid Terminology - Basic Definitions

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________
Hi PQUIP and friends,

At the PQUIP meeting at IETF 116 I committed to summarising the discussion on algorithm type naming that happened on the mailing list back in March [1]. The email aims to do that, as well as to provide some justification for the choices made in the draft at the moment. The aim here is to come to some consensus on the base level definitions/names in this draft, allowing us to use this terminology to build from there.

I'll focus on the following definitions:
1. Traditional Algorithm: An asymmetric cryptographic algorithm based on integer factorisation, finite field discrete logarithms or elliptic curve discrete logarithms 2. Post-Quantum Algorithm: An asymmetric cryptographic algorithm that is believed to be secure against quantum computers as well as classical computers.
3. Post-Quantum/Traditional (PQ/T) Hybrid Scheme: A cryptographic scheme made up of two or more component algorithms where at least one is a post-quantum algorithm and at least one is a traditional algorithm.

Taking these one at a time:
1. Traditional Algorithm
        - Alternative words that have been suggested are classical, conventional, pre-quantum, vintage, quantum-vulnerable. Others have suggested alternatives that describe the mathematical problems that these algorithms are based on e.g., discrete-log or integer-factorisation based.
        - The current version uses "traditional", rather than another word, for these reasons:
                a. It doesn't begin with "C" or "PQ" so can form a helpful and non-confusing acronym. Conventional/classical seem non-ideal because PQC is already taken as an acronym.
                b. Classical describes a type of computer, and PQ algorithms are run on classical computers.
                c. It is a single word and is not too long or technical. I think this is important if we want the terminology to be used.
                d. It doesn't suggest that these types of algorithms are already insecure before the existence of a CRQC (as e.g., vintage might).
        - Arguments against "traditional" include:
                a. In the long term we might expect PQ algorithms to become "traditional", so this may not age well.
                b. Traditional is one of the words highlighted as potentially biased in NIST's inclusive language guidance [2]. I believe that the usage in this document is sufficiently different to the example in the NIST guidance that it is reasonable to use the word here, but it is worth taking into consideration.

2. Post-Quantum Algorithm
        - Alternative words: quantum-safe, quantum-resistant.
        - The current version uses "post-quantum" for these reasons:
                a. It is currently the most widely used term for this algorithm type.
                b. Quantum-safe and quantum-resistant suggest properties of the security achieved by the algorithms, rather than the security goals of the algorithm. For example, SIKE is a post-quantum algorithm, but calling it a quantum-safe algorithm is (at best) highly misleading.
                c. Quantum-safe has previously been used to include both PQC and QKD (e.g. by ETSI).

3. PQ/T Hybrid Scheme
        - Obviously this decision depends on 1. and 2. above.
        - I am currently using PQ/T hybrid scheme for this concept because I believe it does a good job of describing the components, giving a technical reader who hasn't read this document has a good chance of understanding the meaning.
        - There was previously discussion on this thread about including a forward slash in the name [3], which suggested that the group preferred some separation between the two algorithm types. This does raise a question about if you pronounce the slash (I think no...).

If you have alternative suggestions for 1,2 and 3 which have fewer compromises than what we've got so far then I'd be very keen to hear them, please do post to the list or email me directly if you'd prefer. Also, if you'd like to add any more pros/cons to this discussion please do reply.

Flo