MAL-BIND-K-CT and MAL-BIND-K-PK Security

[Dustin-Ray]

Notions beyond IND-CCA:

Schmieg proves here that misbinding properties can occur due to the way private keys are serialized and fixed by using a single seed to generate the private key, and thus ML-KEM-768 (generalized to other variants as well) is not MAL-BIND-K-CT or MAL-BIND-K-PK secure. This conclusion is drawn from this paper which introduces the MAL-BIND security notions which extend beyond IND-CCA.

NIST is now proposing the following modification to the FIPS 203 IPD:

"We propose ML-KEM uses a single 32-byte seed as decapsulation key, from which rho, sigma, and z are expanded.

This is smaller and simpler. Simpler, because we do not need to think about decapsulation key formatting or validation. In particular, it ensures that ML-KEM is MAL-BIND-K-CT and MAL-BIND-K-PK"

Proposed update to FIPS 203 IPD:

The IPD currently specifies that key expansion is unpacked before decapsulation, also precomputing $A$:

"packed"          unpack        ready-to-use                      keygen
decaps key:     -------->       decaps key:           <---------  64 byte seed
s, ek, H(ek), z                 s, ek, H(ek), z, A                d, z

NISTs proposal is to simplify this process:

"packed"       unpack=keygen        ready-to-use
decaps key:       -------->         decaps key:
g                                   s, ek, H(ek), z, A

With the caveat:

To be clear, we do not propose that FIPS 203 specifies this two-step approach. It merely should not preclude it.

Implementation Routes:

Two possible means of applying the proposed update are suggested:

Solution 1: brief:

1. Rename K-PKE.KeyGen to K-PKE.ExpandPrivate; remove lines 1, 2; and add rho and sigma as arguments.
2. Rename ML-KEM.KeyGen to ML-KEM.ExpandPrivate; add a 32-byte g as argument; call K-PKE.ExpandPrivate instead of K-PKE.KeyGen on line 2 passing rho and sigma; and replace line 1 by: $(\rho, \sigma, z) = J(g)$
3. Define a new ML-KEM.KeyGen as:

g <$- B^32
ek, dk = ML-KEM.ExpandPrivate(g)
return (ek, g)

4. Change ML-KEM.Decaps to take a 32-byte g as argument instead of dk. Add before line 1:

_, dk = ML-KEM.ExpandPrivate(g)

Solution 2: tight integration and readability, closer to implementations in practice:

1. Rename K-PKE.KeyGen to K-PKE.ExpandPrivate; remove lines 1, 2, 20, and 21; add rho and sigma as arguments; and return (^A, ^t, ^s).

2. Add a new function ML-KEM.UnpackPrivate that takes a 32-byte seed dk as argument, and acts as follows:

SHAKE-256:
$(\rho, \sigma, z) = J(dk)$

^A, ^t, ^s = K-PKE.ExpandPrivate(rho, sigma)
ek = ByteEncode_12(^t) || rho
return (^A, ^t, ^s, ek, H(ek), z)

3. Change ML-KEM.KeyGen to:

dk <$- B^32
(^A, ^t, ^s, ek, h, z) = ML-KEM.UnpackPrivate(dk)
ek = ByteEncode_12(^t) || rho
return (ek, dk)

4. Change K-PKE.Encrypt to accept ^A, and ^t directly instead of ek_PKE, removing lines 2–8.
5. Change K-PKE.Decrypt to accept ^s as argument directly instead of dk_PKE, removing line 5.
6. Change ML-KEM.Decaps to accept the shortened 32-byte dk. Replace lines 1-4 by

(^A, ^t, ^s, ek, h, z) = ML-KEM.UnpackPrivate(dk)

and pass ^s instead of dk_PKE to K-PKE.Decrypt (line 7); and ^A, ^t instead of ek_PKE to K-PKE.Encrypt (line 8).

8. Change ML-KEM.Encaps to include the lines 2–8 removed from K-PKE.Encrypt before the call to K-PKE.Encrypt, to which ^A and ^t are passed instead of ek_PKE.

Thoughts

What are the feelings around this? Is this update needed currently? This announcement is recent but I thought it would be worth bringing up sooner than later.

[Dustin-Ray]

@tarcieri Ive been seeing your posts in the NIST pqc forum. Is this issue still needed or is it something you have a better idea of how to solve than I do? I raised this when the debate was strong on this topic, but now that fips 203 is published, wondering if we still need this or not

[tarcieri]

#53 seems like the way forward here