Polynomial serialization bit order differs from Falcon C reference

[mindlapse]

I noticed an issue with the bit order during key serialization (and deserialization) when compared to the Falcon C reference. Here is the reference I'm comparing against:

C reference: See 'Falcon submission package [zip] (specification, source code, scripts and test vectors)' at https://falcon-sign.info/

The current Python serialize_poly() function packs 14-bit polynomial coefficients into bytes using a different bit ordering than the Falcon C reference implementation (modq_encode). Although both implementations produce the same number of bytes and use 14-bit coefficients, they place coefficients at opposite ends of the resulting byte string.

This difference means serialized polynomials are not wire-compatible between the Python and C implementations.

In the Falcon C reference implementation (modq_encode in falcon-enc.c), coefficients are serialized as follows:

1. Start with an empty bit accumulator (acc = 0).
2. For each coefficient x[u]:
   • Shift the existing bits left by 14.
   • Insert the new coefficient into the least significant 14 bits.
   • As soon as at least 8 bits are available at the left side of the accumulator, emit one byte by taking bits from the left (most significant bits) and write them to the output.

Here's a simplified excerpt from the C reference code:

        for (u = 0; u < n; u ++) {
                acc = (acc << 14) | x[u];
                acc_len += 14;
                while (acc_len >= 8) {
                        acc_len -= 8;
                        *buf ++ = (uint8_t)(acc >> acc_len);
                }
        }

The python serialize_poly() builds the bitstream differently:

...
    BITS_PER_COEF = 14
    int_buffer = 0
    for idx in range(n):
        int_buffer ^= poly[idx] << (idx * BITS_PER_COEF)
    # The "+ 7" allows to round to the nearest higher integer.
    bytelen = (n * BITS_PER_COEF + 7) >> 3
    return int_buffer.to_bytes(bytelen)

This means that with the Python version:

• poly[0] is placed into the least significant 14 bits.
• poly[1] is placed above it (bits 14–27), and so on.

After all coefficients are placed, the integer is converted to bytes in big-endian order, meaning the most significant bytes are written first. As a result, coefficient 0 ends up near the end of the byte string, whereas in the C reference encoding it influences the earliest bytes.

I ran into this discrepancy while working on signature verification in a different language and wanted to share it in case it’s helpful. My understanding is that this difference would prevent keys produced by a C-reference-compatible implementation from being deserialized correctly by this Python implementation (and vice versa).

Please let me know if I’m missing anything or misunderstanding the intended encoding here. Thanks for your work on this implementation, and for contributing to post-quantum cryptography.