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?