open-quantum-safe
Create a table of algorithm support levels
Similar to PLATFORMS.md, we should have a table indicating the support levels of the algorithms, supplementing/summarizing the information spread across the algorithm datasheets.
In order to create a table of algorithm support levels, we'll need to have some characteristics that define the different support levels. Here are some features that come to mind. Any other ideas?
- degree of standardization
- implementation characteristics
- verification
- constant-time
- platform optimizations
- degree of support from implementation maintainers
- vulnerability response
In case it helps anyone working on this in the future, I got started on this in this branch: https://github.com/open-quantum-safe/liboqs/compare/sw-alg-datasheet.
In order to create a table of algorithm support levels, we'll need to have some characteristics that define the different support levels. Here are some features that come to mind. Any other ideas?
* degree of standardization * implementation characteristics * verification * constant-time * platform optimizations * degree of support from implementation maintainers * vulnerability response
I feel confused about the need for a separate ALGORITHMS.md. There is already a set of documents under docs/kem, docs/sig, and docs/sig_stfl that record a lot of the information mentioned above, so it seems like a duplicate?
The primary concern to me is that we record accurately the state of the different algorithms, so users can make informed choices. And then secondary is that we present this information in a helpful location. The thought was that a top-level ALGORITHMS.md file would be more visible (and more concise?) than the quite detailed datasheets under the docs folder. But I also take your point about duplication.
Maybe a first step would be to get that information to the algorithm datasheets (add appropriate fields to the YML files and then update the Markdown generation). As a second step, if we have the data in the YML files, then we can also have the code generation summarize it into a top-level ALGORITHMS.md file.
The more I think about it, I doubt a separate file is needed:
What about the idea to just update the algorithms documentation in the README, simply stating which algorithm families have upstream maintenance and which ones don't? For all details, pointing to the files in the docs folder may be sufficient.
The thing we did in oqs-demos may serve as an example: Support status and maintainer is listed there for each demo, giving users an immediate hint at what they may "get into" when using a demo (algorithm in this case).
I am thinking of a table that looks like this:
| Algorithm | Security Levels | Standardization | Primary implementation | Implementation details | Optimization |
|---|---|---|---|---|---|
| ML-KEM-512 | 1 | FIPS 203 | ml-kem-native | "production grade", "actively supported", etc. | AVX2 |
| ML-DSA-44 | 2 | FIPS 204 | ml-dsa-native | "production grade", "actively supported", etc. | AVX2 |
| HQC-128 | 1 | "standard track" | PQClean | "silver grade", "not really maintained", etc. | None |
| SLH-DSA-SHA2-128-FAST | 1 | FIPS 205 | slh-dsa-c | "production grade", "actively maintained", etc. | None |
Some notes:
- I am not sure if we should put one algorithm per entry (i.e. ML-KEM-512 and 768 would be a single entry) or one parameter set per entry (i.e. ML-KEM-512 and 768 are two separate entries). Separating parameter set would allow us to specify individual NIST security level, which I think is important information
- Implementation details (e.g. large stack usage, formal verification, branching on secrets, etc) should probably be "summarized" into tier list; maintenance status (e.g. actively supported or not) and optimizations should be separate
- The summary should probably only list the primary upstream, but leave link to "alternative implementations" such as ML-KEM with CUDA
- How do we want to approach algorithms with large number of variants? SLH-DSA has 156, although FIPS 205 seemed to have listed only 12. There are also LMS with some thirty variants, and other non-standardized algorithms (classic mceliece, MAYO, etc.).
Thanks for the proposal @xuganyu96 -- I think most of these details are covered in the respective .md files in the docs folder. Hence, my preference would be to only have one entry per algorithm family, stating standardization level (link to the standards doc if appropriate) and a link to the implementation source stating its maturity and support level there: I don't think liboqs should make representations regarding "actively maintained" or "production grade" -- these statements should be plainly stated (and corresponding obligations delivered) by the upstreams. Only the term "no active maintenance" we should state (actually, by default), e.g., if there is no person we can point to wrt maintaining a specific algorithm family). And of course a link to the detail doc .md)
a link to the implementation source stating its maturity and support level there
@baentsch I am not clear about this point. Could you please clarify with a few examples?
- The primary implementation of ML-KEM is sourced from mlkem-native@048fc2a. In addition to the link, what else should we state in this summary table?
- How do we figure out which implementation source has active maintenance? Do we assume "not actively maintained" unless we have an active point of contact? Do we need to reach out to them to get consent?
Based on the comment above the table would look something like this:
| Algorithm family | Standardization | Source of implementation | Details |
|---|---|---|---|
| ML-KEM | FIPS 203 | ml-kem-native | link to mlkem.md |
| HQC | standard track | PQClean | link to hqc.md |
Do we assume "not actively maintained" unless we have an active point of contact?
That would be safest. But we may also want to check whether there's any ongoing activity in the upstream repo and reach out to the latest contributors and ask whether they want to keep up the work for the foreseeable future. In such case, maybe the status "best effort" would be a suitable maintenance description for such upstream (but again, ask the upstream contacts what they'd like to publicly represent regarding their maintenance level -- and best, provide published wording we can link to).
Do we need to reach out to them to get consent?
That would be sensible. And that person should also let us know what level of support (from "None" to "full product level" they (or their project) is willing to give -- liboqs has this reasonably formulated and I'd expect any upstream to do the same -- particularly if it aims for commercial utility, the wording should be clear (and we should be able to link there). Please note this is a long-standing issue (https://github.com/open-quantum-safe/liboqs/issues/2064) that would be really good to resolve.
Defining "standardization status"
The closest thing existing YAML data sheets under docs/algorithms to a standardization status is nist-round, which I find unsatisfactory. It seems necessary to add a top-level field to each of the data sheet named standardization-status, for which Spencer's proof-of-concept here is a good place to start:
standardization status:
- Standardized: includes FIPS 203, 204, 205, XMSS/LMS
- Selected for standardization: Falcon and HQC for sure, but does Classic McEliece count? Does Kyber count as "selected for standardization"?
- Under consideration: UOV, MAYO, CROSS, etc.
- Not selected: NTRU, etc.
With standardized algorithms we can link to the appropriate FIPS document, but what about the other ones? Should we link to their "draft" specification under each submitter's website?
I think we could include which organization(s) have standardized / selected for standardization. E.g., Classic McEliece has been selected for standardization by ISO. For ones in this category, we can link to the spec (though ISO documents are behind a paywall).
For drafts under consideration, yes, we can link to the draft specification from each submitter's website or to the version from the relevant round on NIST's website.
I am planning to add two fields to each of the YML datasheets under docs/algorithms:
standardization-statuswill be a free text field, whose values will be directly displayed on the alg support tablespec-urlwill be a link to some document or website containing the algorithm specification. Where there is a government website available, I prefer using the government link. For example, Kyber's third round submission will be linked to NIST's website instead of PQCrystal's website. edit: unless the submission team published a newer version than is not available on NIST website, such is the case with CROSS and HQC
For some examples:
# kyber.yml
standardization-status: "Selected by NIST"
spec-url: "https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Kyber-Round3.zip"
# ml_kem.yml
standardization-status: "Standardized by NIST"
spec-url: "https://csrc.nist.gov/pubs/fips/203/final"
# classic_mceliece.yml
standardization-status: "Under consideration by ISO"
spec-url: "https://classic.mceliece.org/iso-mceliece-20230419.pdf"
# ntru.yml
standardization-status: "Not selected"
spec-url: "https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/NTRU-Round3.zip"
On display, standardization-status will be wrapped in an hyperlink to spec-url:
| Algorithm family | Standardization status | Primary implementation |
|---|---|---|
| Kyber | Selected by NIST | ... |
Hmm, this plan to me seems like it's only adding the standardization level, but doesn't address the original (t)ask
indicating the support levels of the algorithms
no? This also seems to be the jist of https://github.com/open-quantum-safe/liboqs/issues/2045#issuecomment-2702163358.
In my opinion, the support level explains to users what level of support a specific algorithm implementation enjoys: The standards level does not state anything about a specific implementation on the spectrum of support: From being professionally maintained (e.g., by paid developers), or looked after every now and then (e.g.,by some researchers with more urgent publication goals at their hands) or having been completely abandoned (e.g., as the companies originally sponsoring the code have new priorities).
I do agree that compliance with a standard is indicative of an algorithm having met some functionally tested properties, but it doesn't say anything about non-functional properties, e.g., protection against side-channel attacks, constant time properties on specific hardware platforms or even more simple, willingness of implementers to respond to security reports: All these are elements of a "support level". All these can only come from/be stated/warranted by the team maintaining the implementation.
@baentsch @dstebila
Hmm, this plan to me seems like it's only adding the standardization level, but doesn't address the original (t)ask
The current plan is indeed missing "support level." I chose to limit the scope of the algorithm support table because I did not want this issue to block 0.15 release for too long. I don't yet feel confident about declaring some primary implementation to be "not supported" without making an outreach efforts first, but I am afraid that such effort could take a lot of time.
At this moment, this table will serve as a more human-readable replacement to the flat list of algorithms (and their variants) currently displayed on README.md. I realize that I've moved the goal post away from the original vision for this issue and I apologize for not communicating this more clearly.
I'm happy to change course if it is important to have support level properly documented at once. We can discuss if this should affect the timeline or scope of 0.15 release.
I agree, Michael, that the current work in updating the table is more about summarizing existing data rather than indicating the level of support, but the latter is what this issue wants. Bruce and I thought that indicating a level of support would require contacting the authors of the implementations we're using to see if our description of the support level matches their intentions, which will require some extra time. So the plan would be to replace the list of algorithms in the README with the table as described above for 0.15.0, and then add the level of support after that. This issue would be kept open until the level of support is added.
the latter is what this issue wants. [...] This issue would be kept open until the level of support is added.
dstebila closed this as completedin #228615 hours ago
doesn't quite line up for me, so re-opening.