chacha_feistel.cuh File Reference

Small-domain PRP via 4-round Feistel network with a ChaCha20-based round function and cycle-walking. More...

#include <fss/prp.cuh>
#include <fss/prg/chacha.cuh>
#include <cuda_runtime.h>
#include <cassert>
#include <fss/util.cuh>

Classes
class	fss::prp::ChaChaFeistel
	Small-domain ChaCha20-Feistel PRP for Cuckoo hashing. More...

Detailed Description

Small-domain PRP via 4-round Feistel network with a ChaCha20-based round function and cycle-walking.

Copyright

Apache License, Version 2.0. Copyright (C) 2026 Yulong Ming i@myl.nosp@m.7.or.nosp@m.g.

Author

Yulong Ming i@myl.nosp@m.7.or.nosp@m.g

Given a target domain [0, domain), the construction:

1. Computes b = ceil(log2(domain)) and half = ceil(b / 2).
2. Runs a 4-round balanced Feistel on (2 * half)-bit values. The round PRF is the keyed ChaCha block function already used as the library PRG: the per-round key (the seed, tweaked by the round number) fills the ChaCha key and the Feistel half-word (<= 64 bits) rides in the 64-bit nonce slot with counter 0.
3. Cycle-walks: if the Feistel output >= domain, re-applies the Feistel until it lands in [0, domain). Expected iterations <= 2 because 2^(2*half) < 4 * domain.

Security: 4-round Luby-Rackoff with PRF round functions gives a CCA-secure PRP and cycle-walking preserves the permutation property (Black & Rogaway, 2002). The round PRF relies on the same keyed-ChaCha pseudorandomness assumption the library PRG already makes, so no new assumption is introduced.

Unlike Aes128Feistel, this backend is stateless and free of OpenSSL, so the same code path serves host and device: Permu is host device and instances are trivially copyable.