To reject or not reject - that is the question. The case of BIKE post quantum KEM

NIST post-quantum cryptography standardization project just entered its final Round 4, where three KEMs are evaluated for standardization, as alternatives. BIKE is one of them. This paper deals with several considerations around building an isochronous and constant-time implementation of the errors-vector generation (EVG) that is used by BIKE. The starting point is the Round 3 BIKE (Ver. 4.2), where a recently published timing attack motivated some changes toward the Round 4 submission. The easiest mitigation simply redefines the EVG to be isochronous. This approach was readily available (already in June 2022) in [1]. It requires only minor changes in the Round 3 specification and reference code, with no changes to the KATs. However, BIKE chose a different, newly proposed EVG method (with new KATs). It was integrated into the definition and reference code of the first Round 4 submission (Ver. 5.0) but turned out to be erroneous. We alerted NIST and the BIKE team about the problems, and proposed solutions. This responsible disclosure allowed the BIKE team to revisit the design decision per one of our solutions, modify the specifications document and the associated proof and submit a revised Round 4 submission (Ver. 5.1). NIST gracefully accepted the fixed specification as the submission. In this paper, we explore the problems, review and compare some engineering aspects associated with different approaches, present more alternatives and conclude with our critique and recommendations.