Very short block ciphers for equally-short plaintexts I'm trying to develop an encryption technique for encrypting short phrases (such as reversibly-anonymized names) in text. The key-generation and ciphertext-representation details are fungible, but most of the techniques I'm envisioning would be best facilitated by a function with the following properties:

I want to encrypt multiple plaintexts with a common key (which is expected to be at least 256 bytes) in such a way that the encrypted string is no larger than the source text (which may be compressed with a short-string-compression algorithm like smaz, both keeping the data small and increasing input entropy).

I looked at common symmetric-encryption ciphers like AES and Salsa20, but the block sizes of both of these result in the output being significantly longer than our input (which may be as short as a single byte).

Since my key material is expected to be almost always longer than the input, I also considered using a one-time-pad approach like just simply XORing the input against the bytes of the key, but this is subject to a trivial known-plaintext attack: if an attacker can guess one encrypted string's input representation, they can can obtain a partial key that can decrypt any other string of that length or shorter by XORing against that plaintext.

I also considered a stream-cipher-like approach using each byte as a block, but that had the issue of inputs with the same prefix having the same prefix when encrypted (ie. if I know "John Smith" encrypts to "ABCDEFGHIJ", then I know "ABCDEKLMNOPQ" is another string beginning with "John").

Is it possible to symmetrically encrypt multiple shorter-than-the-key byte sequences (without nonces) in such a way that


the output is the same length as the input,
inputs with similar subsequences (eg. identical prefixes) don't have matching (partial) ciphertext,
and other plaintexts can't be derived from a known plaintext (or at least, not trivially)?


It feels like what I'm asking for is a block cipher that can operate on blocks of any width from $8$ to $n$ (where $n$ is the length of the message, or at least the length of the key). Does such an algorithm exist?
Why don't you use a stream chiper like RC4? (ok, RC4 is known to be broken, but there are many others). Am I missing something from your question?