# Key-Bijective Secure Symmetric Encryption Methods

In AES, an N-bit message is mapped 1-to-1 message-to-output (for a fixed key). If we use a key with N bits, however, the key is not mapped 1-to-1 key-to-output (for a fixed message).

So, is there any secure symmetric encryption method with a 1-to-1 key-to-output mapping?

In the end, I'm just looking for a hash function h(m,k) with no collisions over m (for a fixed k) and no collisions over k (for a fixed m), but it seems easiest to leverage encryption methods research.

• Does the number of valid ms need to equal the number of valid ks? ​ Does the number of allowed outputs need to equal the maximum of those two? ​ ​ ​ ​ – user991 Oct 28 '16 at 20:54
• Yes and yes. Ideally, I want all N-bit numbers valid for m, all N-bit numbers valid for k, and then to simply calculate an N-bit output. N=128 or more. – bobuhito Oct 28 '16 at 22:25
• What security properties do you want? ​ (Consider bitwise-xor.) ​ ​ ​ ​ – user991 Oct 28 '16 at 22:32
• At this point, I just want the obvious: Determining k (from known m and output) takes much longer than determining output (from known m and k). So, XOR is out. – bobuhito Oct 28 '16 at 22:48
• You have a constant M. Using 2 values K1 and K2 as key to an encryption algorithm E, you get C1=E(K1,M), C2=E(K2,M) and worry about the fact that C1 could equal C2 for certain K1 and K2 that are not equal. But you could have C1'=E(M,K1), C2'=E(M,K2) and C1' and C2' are sure to be different, right? (If the particular value of M here bing used as key would be a concern, you could IMHO use in it's place M'=E(K',M) where K' is a suitable key for E.) – Mok-Kong Shen Oct 29 '16 at 9:06

You are asking for a function $$h(m, k)$$ such that for fixed $$m$$, $$k \mapsto h(m, k)$$ is a permutation, and for fixed $$k$$, $$m \mapsto h(m, k)$$ is a permutation. Obviously $$m$$, $$k$$, and the output of $$h$$ must be in the same space. Suppose they live in a group $$G$$ (written additively), e.g. they're bit strings interpreted in $$\operatorname{GF}(2^n)$$. For any fixed permutations $$\pi$$ and $$\sigma$$, $$(m, k) \mapsto \pi(m) + \sigma(k)$$ satisfies this. (It seems likely that this is the only shape $$h$$ can have, but I haven't ruled others out.)
However, you presumably have some security goals in mind. For example, you probably want to require that $$\pi$$ and $$\sigma$$ be difficult to invert; otherwise, a known-plaintext attack would lead to key recovery from the ciphertext $$c = h(m, k)$$ by $$(m, c) \mapsto \sigma^{-1}(c - \pi(m))$$. One option would be $$x \mapsto (g^x - 1) \bmod p$$ where $$p$$ is a large prime and $$g$$ is a generator of $$(\mathbb Z/p\mathbb Z)^\times$$; this is a permutation of $$\{0, 1, 2, \dots, p - 2\}$$, inverting which is tantamount to computing discrete logs. (One could also use $$x \mapsto x^3 \bmod pq$$ for large secret primes $$p$$ and $$q$$, if one wanted a permutation with a back door.)
• Decryption is $(c, k) \mapsto \pi^{-1}(c - \sigma(k))$. $x \mapsto x^3 \bmod pq$ is a permutation of the units of $\mathbb Z/(pq)\mathbb Z$ (and zero); in principle someone could pass in an input that is not a unit (or zero), but if they managed to find one, they have factored the modulus. – Squeamish Ossifrage Mar 31 '19 at 20:18