ML-KEM polynomial operations (FIPS 203). More...

#include "lcx_mlkem.h"
#include "lcx_sha3.h"
#include "cx_mlkem_poly.h"
#include "cx_mlkem_util.h"

Include dependency graph for cx_mlkem_poly.c:

Macros
#define	MLKEM_QINV 62209U

#define	MLKEM_BARRETT_V 20159

#define	MLKEM_BARRETT_SHIFT 26

#define	MLKEM_MONT_FACTOR 1353

#define	MLKEM_INVNTT_SCALE 1441

#define	MLKEM_COMPRESS_CONST_D1 1290168U

#define	MLKEM_COMPRESS_CONST_D4 1290160U

#define	MLKEM_COMPRESS_CONST_D5 1290176U

#define	MLKEM_COMPRESS_CONST_D10_11 2642263040ULL

Functions
int16_t	MLKEM_POLY_montgomery_reduce (int32_t a)
	Montgomery reduction of a 32-bit integer.

int16_t	MLKEM_POLY_fqmul (int16_t a, int16_t b)
	Multiplication in the NTT domain followed by Montgomery reduction.

int16_t	MLKEM_POLY_barrett_reduce (int16_t a)
	Barrett reduction of a coefficient modulo q.

int16_t	MLKEM_POLY_signed_to_unsigned_q (int16_t c)
	Maps a signed representative to an unsigned one in [0, q-1].

void	MLKEM_POLY_reduce (poly *r)
	Applies Barrett reduction to all coefficients and map to [0, q-1].

void	MLKEM_POLY_tomont (poly *r)
	Converts a polynomial to Montgomery domain.

void	MLKEM_POLY_add (poly r, const poly b)
	Adds polynomial b to polynomial r in place.

void	MLKEM_POLY_sub (poly r, const poly b)
	Subtracts polynomial b from polynomial r in place.

void	MLKEM_POLY_ntt (poly *p)
	Computes the NTT of a polynomial in place.

void	MLKEM_POLY_invntt_tomont (poly *p)
	Computes the inverse NTT and multiply by Montgomery factor.

void	MLKEM_POLY_basemul_acc_montgomery (poly r, const poly a, const poly *b, int32_t first)
	Pointwise multiplication of two polynomials in NTT domain with accumulation.

void	MLKEM_POLY_tobytes (uint8_t r, const poly a)
	Serializes a polynomial to bytes (12 bits per coefficient).

void	MLKEM_POLY_frombytes (poly r, const uint8_t a)
	Deserializes a polynomial from bytes (12 bits per coefficient).

uint8_t	MLKEM_POLY_scalar_compress_d1 (int16_t u)
	Scalar compression with d=1.

uint8_t	MLKEM_POLY_scalar_compress_d4 (int16_t u)
	Scalar compression with d=4.

int16_t	MLKEM_POLY_scalar_decompress_d4 (uint8_t u)
	Scalar decompression with d=4.

uint8_t	MLKEM_POLY_scalar_compress_d5 (int16_t u)
	Scalar compression with d=5.

int16_t	MLKEM_POLY_scalar_decompress_d5 (uint8_t u)
	Scalar decompression with d=5.

uint16_t	MLKEM_POLY_scalar_compress_d10 (int16_t u)
	Scalar compression with d=10.

int16_t	MLKEM_POLY_scalar_decompress_d10 (uint16_t u)
	Scalar decompression with d=10.

uint16_t	MLKEM_POLY_scalar_compress_d11 (int16_t u)
	Scalar compression with d=11.

int16_t	MLKEM_POLY_scalar_decompress_d11 (uint16_t u)
	Scalar decompression with d=11.

void	MLKEM_POLY_compress_d4 (uint8_t r, const poly a)
	Compresses a polynomial with dv=4 and serialize to bytes.

void	MLKEM_POLY_decompress_d4 (poly r, const uint8_t a)
	Decompresses a polynomial from bytes with dv=4.

void	MLKEM_POLY_compress_d5 (uint8_t r, const poly a)
	Compresses a polynomial with dv=5 and serialize to bytes.

void	MLKEM_POLY_decompress_d5 (poly r, const uint8_t a)
	Decompresses a polynomial from bytes with dv=5.

void	MLKEM_POLY_compress_d10 (uint8_t r, const poly a)
	Compresses a polynomial with du=10 and serialize to bytes.

void	MLKEM_POLY_decompress_d10 (poly r, const uint8_t a)
	Decompresses a polynomial from bytes with du=10.

void	MLKEM_POLY_compress_d11 (uint8_t r, const poly a)
	Compresses a polynomial with du=11 and serialize to bytes.

void	MLKEM_POLY_decompress_d11 (poly r, const uint8_t a)
	Decompresses a polynomial from bytes with du=11.

void	MLKEM_POLY_frommsg (poly r, const uint8_t msg)
	Decodes a 32-byte message into a polynomial.

void	MLKEM_POLY_tomsg (uint8_t msg, const poly a)
	Encodes a polynomial into a 32-byte message.

Variables
static const int16_t	zetas [MLKEM_N/2U]

Detailed Description

ML-KEM polynomial operations (FIPS 203).

Implements polynomial arithmetic (NTT, inverse NTT, base multiplication, Barrett/Montgomery reduction), serialization, compression/decompression, message encoding/decoding, and sampling routines.

Definition in file cx_mlkem_poly.c.

Macro Definition Documentation

◆ MLKEM_BARRETT_SHIFT

#define MLKEM_BARRETT_SHIFT 26

Barrett right-shift amount.

Definition at line 36 of file cx_mlkem_poly.c.

◆ MLKEM_BARRETT_V

#define MLKEM_BARRETT_V 20159

Barrett multiplier for q = 3329.

Definition at line 35 of file cx_mlkem_poly.c.

◆ MLKEM_COMPRESS_CONST_D1

#define MLKEM_COMPRESS_CONST_D1 1290168U

Compression multiplier for d = 1.

Definition at line 44 of file cx_mlkem_poly.c.

◆ MLKEM_COMPRESS_CONST_D10_11

#define MLKEM_COMPRESS_CONST_D10_11 2642263040ULL

Compression multiplier for d = 10 and 11.

Definition at line 48 of file cx_mlkem_poly.c.

◆ MLKEM_COMPRESS_CONST_D4

#define MLKEM_COMPRESS_CONST_D4 1290160U

Compression multiplier for d = 4.

Definition at line 45 of file cx_mlkem_poly.c.

◆ MLKEM_COMPRESS_CONST_D5

#define MLKEM_COMPRESS_CONST_D5 1290176U

Compression multiplier for d = 5.

Definition at line 46 of file cx_mlkem_poly.c.

◆ MLKEM_INVNTT_SCALE

#define MLKEM_INVNTT_SCALE 1441

128^{-1} * 2^{16} mod q (inv-NTT scale).

Definition at line 38 of file cx_mlkem_poly.c.

◆ MLKEM_MONT_FACTOR

#define MLKEM_MONT_FACTOR 1353

2^{32} mod q (to-Montgomery factor).

Definition at line 37 of file cx_mlkem_poly.c.

◆ MLKEM_QINV

#define MLKEM_QINV 62209U

q^{-1} mod 2^{16} (Montgomery inverse).

Definition at line 34 of file cx_mlkem_poly.c.

Function Documentation

◆ MLKEM_POLY_add()

void MLKEM_POLY_add	(	poly *	r,
		const poly *	b
	)

Adds polynomial b to polynomial r in place.

Parameters

[in,out]	r	Accumulator polynomial.
[in]	b	Polynomial to add.

Definition at line 107 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_barrett_reduce()

int16_t MLKEM_POLY_barrett_reduce ( int16_t a )

Barrett reduction of a coefficient modulo q.

Parameters

[in] a Input coefficient.

Returns: Reduced coefficient.

Definition at line 80 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_basemul_acc_montgomery()

void MLKEM_POLY_basemul_acc_montgomery	(	poly *	r,
		const poly *	a,
		const poly *	b,
		int32_t	first
	)

Pointwise multiplication of two polynomials in NTT domain with accumulation.

Parameters

[in,out]	r	Accumulator polynomial (set or accumulated depending on `first`).
[in]	a	First input polynomial.
[in]	b	Second input polynomial.
[in]	first	If non-zero, overwrite r; otherwise accumulate into r.

Definition at line 159 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_compress_d10()

void MLKEM_POLY_compress_d10	(	uint8_t *	r,
		const poly *	a
	)

Compresses a polynomial with du=10 and serialize to bytes.

Parameters

[out]	r	Output byte array.
[in]	a	Polynomial to compress.

Definition at line 342 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_compress_d11()

void MLKEM_POLY_compress_d11	(	uint8_t *	r,
		const poly *	a
	)

Compresses a polynomial with du=11 and serialize to bytes.

Parameters

[out]	r	Output byte array.
[in]	a	Polynomial to compress.

Definition at line 373 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_compress_d4()

void MLKEM_POLY_compress_d4	(	uint8_t *	r,
		const poly *	a
	)

Compresses a polynomial with dv=4 and serialize to bytes.

Parameters

[out]	r	Output byte array.
[in]	a	Polynomial to compress.

Definition at line 285 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_compress_d5()

void MLKEM_POLY_compress_d5	(	uint8_t *	r,
		const poly *	a
	)

Compresses a polynomial with dv=5 and serialize to bytes.

Parameters

[out]	r	Output byte array.
[in]	a	Polynomial to compress.

Definition at line 308 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_decompress_d10()

void MLKEM_POLY_decompress_d10	(	poly *	r,
		const uint8_t *	a
	)

Decompresses a polynomial from bytes with du=10.

Parameters

[out]	r	Output polynomial.
[in]	a	Input compressed byte array.

Definition at line 357 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_decompress_d11()

void MLKEM_POLY_decompress_d11	(	poly *	r,
		const uint8_t *	a
	)

Decompresses a polynomial from bytes with du=11.

Parameters

[out]	r	Output polynomial.
[in]	a	Input compressed byte array.

Definition at line 394 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_decompress_d4()

void MLKEM_POLY_decompress_d4	(	poly *	r,
		const uint8_t *	a
	)

Decompresses a polynomial from bytes with dv=4.

Parameters

[out]	r	Output polynomial.
[in]	a	Input compressed byte array.

Definition at line 299 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_decompress_d5()

void MLKEM_POLY_decompress_d5	(	poly *	r,
		const uint8_t *	a
	)

Decompresses a polynomial from bytes with dv=5.

Parameters

[out]	r	Output polynomial.
[in]	a	Input compressed byte array.

Definition at line 323 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_fqmul()

int16_t MLKEM_POLY_fqmul	(	int16_t	a,
		int16_t	b
	)

Multiplication in the NTT domain followed by Montgomery reduction.

Parameters

[in]	a	First operand.
[in]	b	Second operand.

Returns: Product reduced modulo q.

Definition at line 75 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_frombytes()

void MLKEM_POLY_frombytes	(	poly *	r,
		const uint8_t *	a
	)

Deserializes a polynomial from bytes (12 bits per coefficient).

Parameters

[out]	r	Output polynomial.
[in]	a	Input byte array of MLKEM_POLYBYTES bytes.

Definition at line 217 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_frommsg()

void MLKEM_POLY_frommsg	(	poly *	r,
		const uint8_t *	msg
	)

Decodes a 32-byte message into a polynomial.

Parameters

[out]	r	Output polynomial.
[in]	msg	Input message of MLKEM_SYMBYTES bytes.

Definition at line 414 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_invntt_tomont()

void MLKEM_POLY_invntt_tomont ( poly * p )

Computes the inverse NTT and multiply by Montgomery factor.

Parameters

[in,out] p Polynomial to transform in place.

Definition at line 138 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_montgomery_reduce()

int16_t MLKEM_POLY_montgomery_reduce ( int32_t a )

Montgomery reduction of a 32-bit integer.

Parameters

[in] a Input value.

Returns: Reduced value in [-q/2, q/2].

Definition at line 67 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_ntt()

void MLKEM_POLY_ntt ( poly * p )

Computes the NTT of a polynomial in place.

Parameters

[in,out] p Polynomial to transform.

Definition at line 121 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_reduce()

void MLKEM_POLY_reduce ( poly * r )

Applies Barrett reduction to all coefficients and map to [0, q-1].

Parameters

[in,out] r Polynomial to reduce in place.

Definition at line 93 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_compress_d1()

uint8_t MLKEM_POLY_scalar_compress_d1 ( int16_t u )

Scalar compression with d=1.

Parameters

[in] u Coefficient to compress.

Returns: Compressed value (1 bit).

Definition at line 232 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_compress_d10()

uint16_t MLKEM_POLY_scalar_compress_d10 ( int16_t u )

Scalar compression with d=10.

Parameters

[in] u Coefficient to compress.

Returns: Compressed value (10 bits).

Definition at line 260 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_compress_d11()

uint16_t MLKEM_POLY_scalar_compress_d11 ( int16_t u )

Scalar compression with d=11.

Parameters

[in] u Coefficient to compress.

Returns: Compressed value (11 bits).

Definition at line 272 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_compress_d4()

uint8_t MLKEM_POLY_scalar_compress_d4 ( int16_t u )

Scalar compression with d=4.

Parameters

[in] u Coefficient to compress.

Returns: Compressed value (4 bits).

Definition at line 238 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_compress_d5()

uint8_t MLKEM_POLY_scalar_compress_d5 ( int16_t u )

Scalar compression with d=5.

Parameters

[in] u Coefficient to compress.

Returns: Compressed value (5 bits).

Definition at line 249 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_decompress_d10()

int16_t MLKEM_POLY_scalar_decompress_d10 ( uint16_t u )

Scalar decompression with d=10.

Parameters

[in] u Compressed value (10 bits).

Returns: Decompressed coefficient.

Definition at line 267 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_decompress_d11()

int16_t MLKEM_POLY_scalar_decompress_d11 ( uint16_t u )

Scalar decompression with d=11.

Parameters

[in] u Compressed value (11 bits).

Returns: Decompressed coefficient.

Definition at line 279 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_decompress_d4()

int16_t MLKEM_POLY_scalar_decompress_d4 ( uint8_t u )

Scalar decompression with d=4.

Parameters

[in] u Compressed value (4 bits).

Returns: Decompressed coefficient.

Definition at line 244 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_scalar_decompress_d5()

int16_t MLKEM_POLY_scalar_decompress_d5 ( uint8_t u )

Scalar decompression with d=5.

Parameters

[in] u Compressed value (5 bits).

Returns: Decompressed coefficient.

Definition at line 255 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_signed_to_unsigned_q()

int16_t MLKEM_POLY_signed_to_unsigned_q ( int16_t c )

Maps a signed representative to an unsigned one in [0, q-1].

Parameters

[in] c Signed coefficient.

Returns: Unsigned representative modulo q.

Definition at line 87 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_sub()

void MLKEM_POLY_sub	(	poly *	r,
		const poly *	b
	)

Subtracts polynomial b from polynomial r in place.

Parameters

[in,out]	r	Accumulator polynomial.
[in]	b	Polynomial to subtract.

Definition at line 114 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_tobytes()

void MLKEM_POLY_tobytes	(	uint8_t *	r,
		const poly *	a
	)

Serializes a polynomial to bytes (12 bits per coefficient).

Parameters

[out]	r	Output byte array of MLKEM_POLYBYTES bytes.
[in]	a	Polynomial to serialize.

Definition at line 206 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_tomont()

void MLKEM_POLY_tomont ( poly * r )

Converts a polynomial to Montgomery domain.

Parameters

[in,out] r Polynomial to convert in place.

Definition at line 100 of file cx_mlkem_poly.c.

◆ MLKEM_POLY_tomsg()

void MLKEM_POLY_tomsg	(	uint8_t *	msg,
		const poly *	a
	)

Encodes a polynomial into a 32-byte message.

Parameters

[out]	msg	Output message of MLKEM_SYMBYTES bytes.
[in]	a	Polynomial to encode.

Definition at line 424 of file cx_mlkem_poly.c.

Variable Documentation

◆ zetas

const int16_t zetas[MLKEM_N/2U]

static

Initial value:

= {
    -1044, -758,  -359,  -1517, 1493,  1422,  287,   202,   -171,  622,   1577,  182,   962,
    -1202, -1474, 1468,  573,   -1325, 264,   383,   -829,  1458,  -1602, -130,  -681,  1017,
    732,   608,   -1542, 411,   -205,  -1571, 1223,  652,   -552,  1015,  -1293, 1491,  -282,
    -1544, 516,   -8,    -320,  -666,  -1618, -1162, 126,   1469,  -853,  -90,   -271,  830,
    107,   -1421, -247,  -951,  -398,  961,   -1508, -725,  448,   -1065, 677,   -1275, -1103,
    430,   555,   843,   -1251, 871,   1550,  105,   422,   587,   177,   -235,  -291,  -460,
    1574,  1653,  -246,  778,   1159,  -147,  -777,  1483,  -602,  1119,  -1590, 644,   -872,
    349,   418,   329,   -156,  -75,   817,   1097,  603,   610,   1322,  -1285, -1465, 384,
    -1215, -136,  1218,  -1335, -874,  220,   -1187, -1659, -1185, -1530, -1278, 794,   -1510,
    -854,  -870,  478,   -108,  -308,  996,   991,   958,   -1460, 1522,  1628,
}

Definition at line 54 of file cx_mlkem_poly.c.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ MLKEM_BARRETT_SHIFT

◆ MLKEM_BARRETT_V

◆ MLKEM_COMPRESS_CONST_D1

◆ MLKEM_COMPRESS_CONST_D10_11

◆ MLKEM_COMPRESS_CONST_D4

◆ MLKEM_COMPRESS_CONST_D5

◆ MLKEM_INVNTT_SCALE

◆ MLKEM_MONT_FACTOR

◆ MLKEM_QINV

Function Documentation

◆ MLKEM_POLY_add()

◆ MLKEM_POLY_barrett_reduce()

◆ MLKEM_POLY_basemul_acc_montgomery()

◆ MLKEM_POLY_compress_d10()

◆ MLKEM_POLY_compress_d11()

◆ MLKEM_POLY_compress_d4()

◆ MLKEM_POLY_compress_d5()

◆ MLKEM_POLY_decompress_d10()

◆ MLKEM_POLY_decompress_d11()

◆ MLKEM_POLY_decompress_d4()

◆ MLKEM_POLY_decompress_d5()

◆ MLKEM_POLY_fqmul()

◆ MLKEM_POLY_frombytes()

◆ MLKEM_POLY_frommsg()

◆ MLKEM_POLY_invntt_tomont()

◆ MLKEM_POLY_montgomery_reduce()

◆ MLKEM_POLY_ntt()

◆ MLKEM_POLY_reduce()

◆ MLKEM_POLY_scalar_compress_d1()

◆ MLKEM_POLY_scalar_compress_d10()

◆ MLKEM_POLY_scalar_compress_d11()

◆ MLKEM_POLY_scalar_compress_d4()

◆ MLKEM_POLY_scalar_compress_d5()

◆ MLKEM_POLY_scalar_decompress_d10()

◆ MLKEM_POLY_scalar_decompress_d11()

◆ MLKEM_POLY_scalar_decompress_d4()

◆ MLKEM_POLY_scalar_decompress_d5()

◆ MLKEM_POLY_signed_to_unsigned_q()

◆ MLKEM_POLY_sub()

◆ MLKEM_POLY_tobytes()

◆ MLKEM_POLY_tomont()

◆ MLKEM_POLY_tomsg()

Variable Documentation

◆ zetas