Recreate public key from private

[bencemali]

For some PQ algorithms one can recreate the public key from only the private key, but oqs-provider still by default attaches the public key to the serialization of the private key, which can be turned off with the NOPUBKEY_IN_PRIVKEY macro. For example in case of Kyber/ML-KEM one can do a workaround roughly like this in oqs-provider's oqsx_key_op function:

            if (strcmp(key->tls_name, "mlkem1024") == 0) {
                memcpy(key->pubkey, (char *)key->privkey + 1536,
                       key->pubkeylen);
            }

The idea for this issue is that liboqs could provide a unified interface for recreating the public key from the private key, when it is possible. For example, a function like this could be added to kem.h in liboqs:

OQS_API OQS_STATUS OQS_KEM_recreate_pub_from_priv(const OQS_KEM *kem, uint8_t *secret_key, uint8_t *public_key);

And in the OQS_KEM structure, for each algorithm a new function could be registered:

OQS_STATUS (*recreate)(const uint8_t *secret_key, const uint8_t *public_key);

Adding this functionality could reduce serialized key sizes for some algorithms. This is a rough idea and I just want to ask for the opinions of the folks involved in oqs.

[SWilson4]

I know that public key recoverability is a feature shared by many algorithms (I can't think of a modern example that doesn't support it), but I would be hesitant to add a function to the public API unless it's either (1) specified by NIST or another similar body or (2) implemented in almost all scheme APIs. Otherwise, it seems like it would introduce a maintenance overhead for us: we would have to support bespoke functions for each algorithm. I do like the idea of this being a standard feature, but I'm not sure liboqs is the place to make it one. I also don't know what the implications for the provider would be. That said, if enough people express interest (and/or are committed to help maintain the code), then I could see the support effort being worthwhile.

Thoughts @dstebila @praveksharma?

[dstebila]

This seems a bit related to the question about whether the secret key should be the seed or the full value; I haven't followed that conversation closely to know if it concluded.

[baentsch]

OK, I've not been asked but I have an opinion regardless: YOLOing taking the risk my comment gets deleted :-) here we go:

oqs-provider still by default attaches the public key to the serialization of the private key, which can be turned off with the NOPUBKEY_IN_PRIVKEY macro [...] reduce serialized key sizes for some algorithms.

This at its core seems to be a question regarding (external) key representation which is not an issue liboqs wants to deal with if I'm not mistaken, @dstebila ? I also agree with @SWilson4 that such a "key recovery" API not working for all algs adds support hassles. Also it may have some security implications we may want to think through first...

I'd be all for switching the default in oqsprovider for NOPUBKEY_IN_PRIVKEY, given this reduces key storage, though: The only reason I'm still aware of that this hasn't been done is "backwards compatibility" thinking (e.g., with the by now deprecated oqs-openssl111 fork). At some point in time, openssl also couldn't cope with (private) key representations that don't permit providing/re-creating a public key -- but AFAIK this is gone: What about you simply give this a try, @bencemali : Set NOPUBKEY_IN_PRIVKEY and run a such configured oqsprovider testing against all supported openssl versions to see what happens? Or does your application rely on the ability of retrieving a public key from a private one? If not/the test being OK, feel free to provide a PR to oqsprovider toggling the default for NOPUBKEY_IN_PRIVKEY. If someone does interop testing they should give this a go before merging the PR, though: @praveksharma : Any info on the IETF hackathon guys still using OQS(provider) for that purpose?

I also don't know what the implications for the provider would be.

Not too many at first blush: Some code changes where there's the current "NOPUBKEY_IN_PRIVKEY" guards (if there's a need to retain the pubkey-regen-from-privkey feature at user level; otherwise, none at all).

That said, if enough people express interest (and/or are committed to help maintain the code), then I could see the support effort being worthwhile.

That I absolutely concur with: Support and maintenance of OQS depends on way too few people and IMO is utterly out of whack with public impressions created.

[bhess]

NIST announced to specify a derandomized API for keygen (and other randomized functions) for the final standards. See https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Mf2kemwwreY/m/KArjoIhxAQAJ?utm_medium=email&utm_source=footer The main purpose seems to be testing and the API should be internal. However, a derandomized keygen function would be a generic way to recreate a keypair from just a seed.

[dstebila]

OK, I've not been asked but I have an opinion regardless: YOLOing taking the risk my comment gets deleted :-) here we go:

oqs-provider still by default attaches the public key to the serialization of the private key, which can be turned off with the NOPUBKEY_IN_PRIVKEY macro [...] reduce serialized key sizes for some algorithms.

This at its core seems to be a question regarding (external) key representation which is not an issue liboqs wants to deal with if I'm not mistaken, @dstebila ? I also agree with @SWilson4 that such a "key recovery" API not working for all algs adds support hassles. Also it may have some security implications we may want to think through first...

My first reaction is that, within liboqs itself, I would want to go for a representation that's as close to what NIST advises as possible. Higher level consumers of liboqs (including oqs-provider) could then decide to use a different representation if they want. For oqs-provider, I guess the question would come down to: what interoperability do consumers of OpenSSL 3 oqs-provider expect for their keys? For that matter, does the provider interface allow for different serialization formats for the same keying material? And then having made that decision, it might come back to liboqs that an additional support function is required.

[JannisFengler]

I can not state how important this feature is. Functionality for deterministic public key generation from the private key and from a random seed.

[bencemali]

Hi! @baentsch maybe I'm missing something, but from our testing when NOPUBKEY_IN_PRIVKEY is set the ability to call encapsulate on a deserialized private MLKEM (also Kyber, maybe others too) key is lost and it's not just backwards compatibility that is violated. Somehow oqsprovider's encoding tests don't catch this, maybe it is known and intended. I think the average liboqs/oqsprovider user would expect that they can call encapsulate on a deserialized private key and thus I don't think NOPUBKEY_IN_PRIVKEY could be turned on by default at this stage. If public key recreation was added to oqsprovider's deserialization this problem would go away where it is possible, that is why I started this discussion.

[baentsch]

when NOPUBKEY_IN_PRIVKEY is set the ability to call encapsulate on a deserialized private MLKEM (also Kyber, maybe others too) key is lost Somehow oqsprovider's encoding tests don't catch this, maybe it is known and intended.

Well, I wouldn't call it necessarily "intended" but rather "logical" or "consequential" and surely known (if one cannot "get" a public key from a suitably extended private key representation). So, you're right stating that enabling this by default will cause problems: Recalling the thinking of the time when adding the "NOPUBKEY_IN_PRIVKEY" build option, it was that any entity activating this has another/separate way of maintaining (and getting access to if in need of) the public key. At no moment this flag was intended to enable (dynamic) public key re-creation (from private key material only), but just to reduce private key size: From the flag's documentation:

to omit explicitly serializing the public key in a privateKey structure

Hence no tests for this.

If public key recreation was added to oqsprovider's deserialization this problem would go away where it is possible, that is why I started this discussion.

I agree: Public key material recreation from truly/purely private key material would be needed to enable this feature by default. I further think this should be a feature that liboqs would have to make available as oqsprovider strives to stay clear of any cryptographic operations: Such things should happen/be made available exclusively within (the OQS equivalent of libcrypto, namely) liboqs such as to keep "sensitive crypto operations" in one place -- and dynamic public key re-creation to me seems to qualify as such sensitive operation.

And to answer @dstebila 's question

For that matter, does the provider interface allow for different serialization formats for the same keying material?

No. It assumes there is a (one!) key serialization standard that a crypto provider needs to implement. And AFAIK there is no such standard yet. Please correct me if I'm wrong, @bencemali .

[baentsch]

Cross-reference to a related OpenSSL issue FYI