A constant-time sampler for close-to-uniform bitsliced ternary vectors

Pierre Karpman (1)

1 CASC - Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie

In this note we describe an algorithm for sampling close-to-uniform random vectors of $\mathbb{F}_3^{64}$ stored in "bitsliced" representation. This algorithm can be implemented in a "constant-time" fashion at some cost and benefits heavily from bit manipulation instructions. We propose three main instantiations that respectively use 256, 384 and 512 uniform random bits to sample vectors whose statistical distance to uniform is upper-bounded by $2^−{31.4}$, $2^{−71.9}$ and $2^{−141.6}$.

Domains: Cryptography and Security [cs.CR]; Data Structures and Algorithms [cs.DS]

Pierre Karpman. A constant-time sampler for close-to-uniform bitsliced ternary vectors. 2022. ⟨hal-03777885⟩