Re: New version of NTS-KEM

[Kenny Paterson]

Dear All,

We would like to announce a new version of NTS-KEM that addresses some issues that have emerged during further development and review of the scheme. The main changes are as follows:

-- We have added a re-encapsulation step during decapsulation, in order to fix a subtle issue in the ROM security proof for NTS-KEM. This issue was identified by Varun Maram from ETH Zurich. This change necessitates the inclusion of the public key as part of the private key and increases the running time of decapsulation. Fortuitously, this change facilitates a QROM proof for NTS-KEM which we plan to make public soon.

[In more detail: our proof did not fully address the possibility that certain adversarially generated ciphertexts not output by encapsulation might decapsulate correctly. This is due to possible behaviour of the decoder, including the Berlekamp-Massey algorithm, when operating beyond its natural decoding capacity. Adding the re-encapsulation step ensures that only correctly generated ciphertexts lead to valid decapsulations; other ciphertexts are implicitly rejected. Our new security proof still tightly relates breaking IND-CCA security of (the new version of) NTS-KEM to breaking one-wayness of the McEliece scheme with the same parameters. We also stress that we are not aware of any concrete attack arising from the issue identified in our proof. Since re-encapsulation makes use of the public key, we now include the public key as part of the private key; an alternative whose cost can be amortised over many invocations of decapsulation is to regenerate the public key from the private key when needed.]

-- We have made the use of the SHA-3 hash function fully consistent throughout the specification and implementation. This addresses inconsistencies between the two that were found by Jan Gilcher from ETH Zurich.

-- We have fixed further implementation bugs also found by Jan Gilcher.

The new version of the specification, new KATs and new reference code can all be found at:

https://nts-kem.io/

We look forward to receiving further analysis of NTS-KEM from the community.

Sincerely,

The NTS-KEM team