Supporting "seed" private key format

[baentsch]

OQS uses the expanded private key format as made available by the reference implementation and as mandated for use by NIST. IETF has other preferences. Question to the team as to which format to support/prioritize. Given OQS history as supporting the NIST competition I'm leaning towards NIST for now. Other input welcome.

Several issues seem to have a reading on the private key format to support for some algorithms (mostly pertaining to ML-KEM): #1206, #1802, #2030 and open-quantum-safe/oqs-provider#613. edit/add: Particularly see #1994.

Background information: https://datatracker.ietf.org/meeting/121/materials/slides-121-pquip-fips-issues-with-deploying-ml-kem-and-ml-dsa-04 and https://www.youtube.com/watch?v=uETYyGwD3gA&t=2221s.

[dstebila]

I think the NIST API from the reference implementations is of less relevance these days, and more of relevance is the APIs specified by the FIPS documents and other standards like IETF. If the IETF working groups are all moving towards private keys as seeds, as Mike Ounsworth's presentation says, then it seems reasonable for liboqs and oqs-provider to support that. And we have received multiple PRs over time indicating willingness to make that change happen. I am unsure whether those discussions are sufficiently mature at this point to pull the trigger, and input on this would be useful. Some care would be needed in keeping implementation complexity low, and preferably upstreams that we rely would be providing the seed-based API as well rather than us patching it in here.

[baentsch]

input on this would be useful

https://openssl-corporation.org/files/blog/Request_to_Extend_IETF_WGLC_for_PQ_Key_Specifications.pdf

[mraksoll4]

the only viable option here is to use the seed as the input for keygen, since in most algorithms keys are always generated in pairs. But honestly, I don’t fully understand their ban on the seed derivation tree. For example, if you use SHA3 or SHAKE256, considering that in some parts of the algorithms, the seed is actually inputed to this algos and processed through multiple "rounds" until "short polynomials" are generated.

if derivation is necessary, there is no other way to do it except through manipulation of the seed and hashing with a strong hashing algorithm , which is much better than directly adding path bytes to the seed.

although, again, a lot depends on where to use signature and encapsulation algorithms.

[bifurcation]

In addition to LAMPS, I would note that some form of key pair derivation (i.e., deterministic generation) is required for MLS. MLS consumes KEMs by means of the HPKE KEM API, and in particular relies on the DeriveKeyPair method.

With regard to implementation approach, it seems like it would be fairly straightforward to do something like:

--- a/scripts/copy_from_upstream/src/kem/family/kem_family.h
+++ b/scripts/copy_from_upstream/src/kem/family/kem_family.h
@@ -9,9 +9,11 @@
 #if defined(OQS_ENABLE_KEM_{{ family }}_{{ scheme['scheme'] }}) {%- if 'alias_scheme' in scheme %} || defined(OQS_ENABLE_KEM_{{ family }}_{{ scheme['alias_scheme'] }}){%- endif %}
 #define OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_length_public_key {{ scheme['metadata']['length-public-key'] }}
 #define OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_length_secret_key {{ scheme['metadata']['length-secret-key'] }}
+#define OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_length_seed {{ scheme['metadata']['length-seed'] }}
 #define OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_length_ciphertext {{ scheme['metadata']['length-ciphertext'] }}
 #define OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_length_shared_secret {{ scheme['metadata']['length-shared-secret'] }}
 OQS_KEM *OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_new(void);
+OQS_API OQS_STATUS OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_derive_keypair(uint8_t *public_key, uint8_t *secret_key, uint8_t *seed);
 OQS_API OQS_STATUS OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_keypair(uint8_t *public_key, uint8_t *secret_key);
 OQS_API OQS_STATUS OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_encaps(uint8_t *ciphertext, uint8_t *shared_secret, const uint8_t *public_key);
 OQS_API OQS_STATUS OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_decaps(uint8_t *shared_secret, const uint8_t *ciphertext, const uint8_t *secret_key);
@@ -21,6 +23,7 @@ OQS_API OQS_STATUS OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_decaps(uint8_t *s
 #define OQS_KEM_{{ family }}_{{ scheme['alias_scheme'] }}_length_ciphertext OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_length_ciphertext
 #define OQS_KEM_{{ family }}_{{ scheme['alias_scheme'] }}_length_shared_secret OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_length_shared_secret
 OQS_KEM *OQS_KEM_{{ family }}_{{ scheme['alias_scheme'] }}_new(void);
+#define OQS_KEM_{{ family }}_{{ scheme['alias_scheme'] }}_derive_keypair OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_derive_keypair
 #define OQS_KEM_{{ family }}_{{ scheme['alias_scheme'] }}_keypair OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_keypair
 #define OQS_KEM_{{ family }}_{{ scheme['alias_scheme'] }}_encaps OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_encaps
 #define OQS_KEM_{{ family }}_{{ scheme['alias_scheme'] }}_decaps OQS_KEM_{{ family }}_{{ scheme['scheme'] }}_decaps

... and the corresponding changes in the templates. I presume there's a way one could add a default implementation for schemes that don't implement deterministic keypair generation, and for the schemes that do to expose it through this API.

I have a very preliminary PR started on this, which I could push forward with if folks think this is a promising approach. I would appreciate a coauthor who has more knowledge of the code base, though.

[bifurcation]

The reasoning behind that implementation idea would be: Seeds are a precursor to "expanded" private keys. So if libOQS exposes the deterministic generation function as well as the randomized one, a consumer that wants to think in terms of seeds can just add a call to the deterministic generation function at the appropriate moments. The _decaps functions can continue to use expanded keys.

Given that integration with OpenSSL is a priority for this project, I would note that this is consistent with the OpenSSL HPKE API. That API exposes the RFC 9180 DeriveKeyPair function as a call to OSSL_HPKE_keygen with a non-NULL ikm parameter. Right now, that method would have to throw an error if called with a non-NULL ikm parameter; with the proposed change, it would just switch to calling _derive_keypair.

[mraksoll4]

the problem of key derivation in schemes like seed + chain id, loss of entropy, also a questionable gain in storage since we still have to cache already generated keys, the only option is to use the combination sha3 + shake in hmac similar schemes, but almost any scheme leads to loss entropy for a long chain

I only realized this now when I started trying to do something like this

in case if we want optimal derivation compact storage + performance.