Is there a block cipher mode that doesn't use the key input of the block cipher? Is there a block cipher mode that does encryption and decryption without using the "key" input of the block cipher?

I ask this because rekeying a block cipher can be an expensive process, and I intend to encrypt many blocks with many different keys.

Is there some mode or construction that has the security of the underlying cipher, while not using it's key input?
This is the difference between block-encryption (with a mode) and permutation-based encryption.

I. Block encryption

Split your message in blocks of the width of the block-cipher, apply a transformation (XOR of the previous ciphertext, XOR of an IV you name it...) and then apply the block cipher.

On a high level, it can be summarized as the following Figure where $K$ is your key, $P_1 \ldots P_n$ are the plaintext blocks, $randomize$ correspond to an operation trying to remove similarity between blocks (remove ECB...) and $C_1 \ldots C_n$ are your ciphertext blocks.

           P_1                 P_2                     P_n

            |                   |                       |
         randomize           randomize               randomize
            |                   |                       |
       +----v----+         +----v----+             +----v----+
       |         |         |         |             |         |
   K -&gt;|    B    |     K -&gt;|    B    |  ...   K  -&gt;|    B    |
       |         |         |         |             |         |
       +---------+         +---------+             +---------+
            |                   |                       |
            |                   |                       |
            v                   v                       v

           C_1                 C_2                     C_n


Of course one could argue that CTR does not work that way, but the principle is the same, you encrypt the counter and XOR the result to the plaintext.
In the end, the process is very similar.

Note: If you are using a different key for each block, you are doing it wrong...

II. Stream encryption

This mode does not requires you to split your plaintext in blocs. You just generate a keystream and Xor it. Nothing fancy, simple, fast and efficient.

                   K

                   |
            +------v-------+
            |              |
       IV --&gt;   Stream     +----+  Keystream
            |              |    |
            +--------------+    |
                                v
Plaintext ----------------------+---&gt; Ciphertext


Examples of this construction are Chacha20, Salsa20...

III. permutation-based encryption

Permutation-based encryption works in a similar fashion as the stream and the block encryption. The key is set at the beginning of the encryption and not used after. The message is split into chunks. This mode is based on a sponge construction



The key stream is then XORed with the message, resulting in the Cipher text.
Examples of this construction are Keyak, Ketje, NORX...

IV. Going further

From that permutation based mode, you can use it in a session style, removing the need to have a key once the session has been initialized.



More readings:

- FSE 2017 - Innovations in permutation-based encryption and/or authenticationInvited Talk by Joan Daemen