Remove Public Key from the Private Key Structure

[csosto-pk]

From John

I know there have also been suggestions about including a smaller value that could help in recomputing the public key from the private key. I guess that could be an optional attribute (the [0] tag in OneAsymmetricKey) if someone decides that is better rather than including an entire public key. I actually prefer to NOT include the public key in the private key, we already have large enough PQ keys, but some application uses might need it I guess.

[csosto-pk]

From Markku

Yes, only the 32-byte "tr" variable, which is a hash of the public key, is required to create signatures and must be included in the private key. The public key is not required for this process.

The size difference between "t1" and the actual Dilithium public key is only 32 bytes (size of "rho"), so it wouldn't make much sense to be passing that variable separately.

Note 1: The "tr" hash in secret is useful for implementations since it allows one to verify that (pk,sk) forms a valid keypair just by checking a hash -- rather than going through most of the key generation process required to derive t1. A robust implementation would probably always do that hash value consistency check when supplied with a key pair.

Note 2: Unlike Dilithium, Kyber requires that public keys are entirely contained in the private keys. CCA decapsulation involves a full re-encryption step.

[csosto-pk]

From David B.

There should not be an OPTIONAL copy of the public key in DilithiumPrivateKey. Either it's part of the structure, or it isn't, with no optionality. We've already learned this lesson with ECPrivateKey; the various optional fields have had a compounding negative effect up the stack. This is also the wrong layer to define this... whatever specification we have for Dilithium, be it NIST's actual document or a fixup document in CFRG, should come with a byte string representation that we just drop into PKCS#8 unmodified and unadorned.

[csosto-pk]

From Phillip H. B.

So, does that mean for Dilithium there is no reason to ever carry the public key and the private key together because it’s literally duplicate data that’s easy to extract?

I disagree with 'never'

When dealing with a layered system, the outer layers do not understand the internals of the crypto algorithms by design. It is pretty easy to calculate the ECDH public key from the private but we never expect an implementation to do that because they are just blobs of bits.

But this looks like a different question, the PKIX encoding of private key leaves this to the individual algorithm so that approach doesn't work for PKIX. But it does for other private key encodings and so we should not make an over-broad statement here.

[csosto-pk]

As Markku brought up in the list, in Dilithium the private key includes rho, K , tr, s1, s2 , t0. In terms of public key material, only rho, tr=CRH(rho|| t1) and t0 are included in the private key, but not the t1 part of the whole t (t=(t0,t1)). t0, t1 are non-sensitive and they make the whole t value which could be looked as a public key. t1 is only included in the Dilithium public key (rho, t1) and is used for verification. That was done to optimize public key size by omitting t0. t0 is used when signing and is only stored in the private key to optimize space.

Someone can derive the public key (rho, t1) from the private key rho, K , tr, s1, s2 , t0 by performing the t := A*s1+s2 computation and getting t1 from (t1, t0) := Power2Roundq(t, d). t := A*s1+s2 is almost as expensive as key generation itself.

In other words, not including the public key (rho, t1) in the private key ASN.1 structure will require a signer that has the private key only to do a t := A*s1+s2 operation in order to get the public key (rho, t1). Given that signers usually do not use the public key to verify their own signatures and that the A*s1+s2 is not awfully expensive, it seems that not putting the whole public key in the private key structure is justified to keep the private key size smaller, prevent issues of the past by putting optional parameters.

I would expect signers to have a separate copy of their public key (rho, t1) and not only store their private key anyway. PKCS#8 could also take either of these in it. Additionally, the private and public key structures should just follow the Signature algorithm specification from NIST and not introduce additional structures that are unnecessary as David B. suggestion above.

[mjosaarinen]

In other words, not including the public key (rho, t1) in the private key ASN.1 structure will require a signer that has the private key only to do a t := A*s1+s2 operation in order to get the public key (rho, t1). Given that signers usually do not use the public key to verify their own signatures and that the A*s1+s2 is not awfully expensive, it seems that not putting the whole public key in the private key structure is justified to keep the private key size smaller, prevent issues of the past by putting optional parameters.

Note that while this can mathematically be done, no current Dilithium implementation provides this conversion functionality. You'd need to create special API calls just to facilitate this. And it would probably be outside NIST / FIPS / CAVP validation too, as it's a "derive the public key from private key" that is not covered by Signing, Verification, and Key Generation pseudocode. So it is not in any way certain that a future FIPS 140-? or NIAP Dilithium module is able to do this at all.

[csosto-pk]

Note that while this can mathematically be done, no current Dilithium implementation provides this conversion functionality. You'd need to create special API calls just to facilitate this. And it would probably be outside NIST / FIPS / CAVP validation too, as it's a "derive the public key from private key" that is not covered by Signing, Verification, and Key Generation pseudocode. So it is not in any way certain that a future FIPS 140-? or NIAP Dilithium module is able to do this at all.

ACK. I still do not consider this as a big problem because the module ought to be able to keep a copy of both the public and private key structures separately.

[csosto-pk]

From Bas W.

What about the following, more radical proposal: we simply use the seed as the private key.

Key generation is fast compared to signing. But it's even better: a big chunk of the computation for key generation is the expansion of A, which is also done for signing. So combining them is less expensive than it seems.

I modified ref and it seems to be roughly sign + keypair - matrix_expand. [1] For ref on my laptop i5, it's a slowdown of 18%, 14%, 10% for 2, 3 and 5. With avx2 on my laptop I'd expect the slowdown to be 11%, 10%, 13%. Of course these numbers are very much platform dependent.

[csosto-pk]

From Uri B.

What about the following, more radical proposal: we simply use the seed as the private key.

I like this idea.

[csosto-pk]

From Markku > The Dilithium specification contains a description of the secret key format; I'd suggest sticking with it.

There are indeed use cases for using the seed as a secret key (especially since a fully deterministic seed expansion mechanism is described in the spec). Secure, non-volatile key storage is very expensive in hardware devices, and the 256-bit Dilithium seed can be internally managed exactly like an AES key. We have semiconductor customers that want this due to the storage issue, despite the performance penalty. However, such keys are managed without any ASN.1 encodings and hence are not really of interest to LAMPS.

Clearly, converting a standard-format Dilithium key back to the seed is impossible. So you can't export the seed from an implementation that uses standard-format keys.

There is a performance penalty from using the seed, but indeed it is not horribly high on a non-protected implementation (if you completely merge the key generation with signing in the implementation) -- I'd guess ~20%?

With side-channel protections, it is a completely different matter due to the random sampling required in key generation. Side-channel attacks generally require many traces of the same operation to be effective; if key generation is only performed only once, it is less vulnerable. But if key generation is performed for every signature, as proposed, then it needs the same level of protection.

The sampling is uniform in a small range, but masked rejection sampling involves masked comparisons and a "gather" operation which are quite expensive. I'd guess the cost is 50%, but customers still want this as otherwise they would need tens of kilobytes of non-volatile storage inside the on-chip security boundary. So.. we happen to have side-channel protected determinstic Dilithium key generation even though an analogous RSA signature module would not have it. This is because signature key generation is performed "rarely" (perhaps only once, during device enrollment) and is randomized. Others may choose not to implement signature algorithm key generation in such a manner.

And Bas acknowledged

With side-channel protections, it is a completely different matter due to the random sampling required in key generation. Side-channel attacks generally require many traces of the same operation to be effective; if key generation is only performed only once, it is less vulnerable. But if key generation is performed for every signature, as proposed, then it needs the same level of protection.

This is a good argument against.

[csosto-pk]

I like the seed idea too because it simplifies the private key. But I don’t like that it basically requires keygen+sign every time you want to sign which is different to what we have traditionally been doing. Plus the side-channel concern Markku brought up. For now, let’s keep the Dilithium PrivateKey in the structure, and we can consider keeping only the seed if there is a shift and keygen+sign for a seed becomes common.