[PALOMA] C Source Code for PALOMA Ver.1.2

[Minji Kim]

Dear all,

We are pleased to announce the release of the C source code for PALOMA Ver.1.2.

You can download it from the official PALOMA website: [PALOMA Website]

This version introduces several key updates compared to the Round 2 (Ver.1.1) code.

The changes are summarized below:

=======================================================================

[GenKeyPair]

1. Computation of parity-check matrix

 - Ver.1.1: Naive matrix multiplication

 - Ver.1.2: Polynomial evaluation-based matrix multiplication

2. Row-Column switching during RREF Generation

 - Ver.1.1: Naive method

 - Ver.1.2: Bit mask method for matrix transpose

=======================================================================

[Decap]

1. Decap: Polynomial multiplication

 - Ver.1.1: Textbook multiplication

 - Ver.1.2: Karatsuba multiplication

2. Decap: Polynomial modular multiplication

 - Ver.1.1: Textbook multiplication, then naive reduction

 - Ver.1.2: Textbook multiplication and naive reduction with fixed polynomial length (for constant time)

3. Decap: Computation of modular inverse of polynomial

 - Ver.1.1: Extended Euclid algorithm

 - Ver.1.2: Modular exponentiation (for constant time)

4. Decap: Finding error vector from error locator polynomial σ(X)

 - Ver.1.1: Exhaustive search using polynomial evaluation

 - Ver.1.2: Gao-Mateer additive FFT

5. Decap: Get degree of polynomial

 - Ver.1.1: Naive method

 - Ver.1.2: Bit operation (for constant time)

6. Decap: Checking if Hamming weight is t

 - Ver.1.1: -

 - Ver.1.2: If the degree of σ(X) is not t, the extended Patterson decoder returns a zero vector in constant time.

7. Decap: In the case where g12(X) = 1

 - Ver.1.1: -

 - Ver.1.2: Extended Patterson returns a zero vector.

=======================================================================

[Others]

1. Tables for field arithmetic are now hard-coded.

2. Memory management has been optimized (shifted from stack to heap), and the current code can run with a 200KB stack.

=======================================================================

In addition, PALOMA team has revised the specification.

This update includes a proof that PALOMA’s extended Patterson decoder does not encounter a situation where g12(X) = 1 for valid syndromes, i.e., those corresponding to error vectors with a Hamming weight of t.

For further details, please refer to Section 2.5 of the revised specification.

Best regards,

Kim Minji, PALOMA team

[D. J. Bernstein]

I tried TIMECOP on the new PALOMA-128 code with one compiler, after some
small changes to the new code for the SUPERCOP API. TIMECOP reported the
following issues:

* "tmp = shuffled_list[j]" in utility.c: This is part of a
Fisher--Yates shuffle, which can be converted into constant-time
code (see my email dated 18 Apr 2024 19:45:58 +0200), but using a
sorting-based shuffle would be faster.

* "(*(mat_ABC + PARAM_N*i + j))" in genkeypair.c: This is a buffer
overread rather than a timing issue.

* "if (t1 & 0x1000)" and "gf2m_tables->mul00_tab[int1low][int2low]"
in gf2m.c: These are part of the variable-time multipliers
discussed in my email dated 26 Apr 2024 22:49:08 +0200.

* "Word err = (LL[L[i]] == 1)" in decoding.c: Similar issue to the
Fisher--Yates shuffle, but simpler in that replacing this with
sorting code doesn't require any changes to the specification.

* "deg ^= ((deg ^ i) & g_mask[((tmp | -tmp) != 0)])" in gf2m_poly.c:
The g_mask lookup can be changed to negation, but it's safer to do
crypto_int32_nonzero_mask(tmp) using "crypto_int32.h".

---D. J. Bernstein