PALOMA: Binary Separable Goppa-based KEM

Dong-Chan Kim, Chang-Yeol Jeon, Minji Kim, Dong Hyun Park, Dong Hyeon Kim, Yeonghyo Kim

Future cryptography Design Lab., Kookmin University

(last updated: 2024.03.16.)

About PALOMA

We propose PALOMA, a new code-based KEM(Key Encapsulation Mechanism), which has the following features:

Trapdoor based on SDP(Syndrome Decoding Problem) with a binary separable (not irreducible) Goppa code.
IND-CCA2-secure KEM based on FO(Fujisaki-Okamoto) transformation.

Parameter sets

PALOMA provides three parameter sets: PALOMA-128, PALOMA-192, and PALOMA-256, which correspond to security strength levels of 128-bit, 192-bit, and 256-bit, respectively.

	Security Level	n	t	k(=n-mt)	m
PALOMA-128	128	3,904	64	3,072	13
PALOMA-192	192	5,568	128	3,904	13
PALOMA-256	256	6,592	128	4,928	13

Each parameter set was carefully chosen to meet the following conditions, ensuring efficient implementation.

Binary separable Goppa codes are defined in $F_{2^{13}}$ which can be used for PALOMA-128, PALOMA-192, and PALOMA-256 simultaneously,
$n + t \leq 2^{13}$ to define a support set and a Goppa polynomial,
$n \equiv k \equiv t \equiv 0 \pmod {64}$ for 64-bit word-aligned implementation, and
$k/n > 0.7$ to reduce the size of a public key, and
Enough security margin.

Performance

Data size (in bytes)

	Public Key	Secret Key	Ciphertext	Key
PALOMA-128	319,488	94,528	136	32
PALOMA-192	812,032	357,568	240	32
PALOMA-256	1,025,024	359,616	240	32

Note that it is possible to compress the size of the secret key to 96 bytes.

Speed (in milliseconds(cycles))

PALOMA is implemented in ANSI C. A speed benchmark was performed on the following platform:

Platform: MacBook Pro(Apple M3, 8GB RAM), Sonoma 14.2.1, Apple clang version 14.0.3 with the -O3 optimization option.
DRBG: AES-256-CTR-based DRBG provided in OpenSSL.

	GenKeyPair	Encap	Decap
PALOMA-128	27.81 (1,021,606)	0.042 (1,014)	1.75 (40,848)
PALOMA-192	119.77 (2,939,786)	0.051 (1,279)	8.97 (212,087)
PALOMA-256	150.03 (3,665,877)	0.060 (1,368)	9.43 (225,231)