We explore the problem of enciphering members of a finite set M where k = ∣M∣ is arbitrary (in particular, it need not be a power of two). We want to achieve this goal starting from a block cipher (which requires a message space of size N = 2ⁿ, for some n). We look at a few solutions to this problem, focusing on the case when M= [0, k - 1]. We see ciphers with arbitrary domains as a worthwhile primitive in its own right, and as a potentially useful one for making higher-level protocols.