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.

  • $\begingroup$ 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? ​ ​ ​ ​ $\endgroup$ – user991 Oct 28 '16 at 20:54
  • $\begingroup$ 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. $\endgroup$ – bobuhito Oct 28 '16 at 22:25
  • $\begingroup$ What security properties do you want? ​ (Consider bitwise-xor.) ​ ​ ​ ​ $\endgroup$ – user991 Oct 28 '16 at 22:32
  • $\begingroup$ 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. $\endgroup$ – bobuhito Oct 28 '16 at 22:48
  • $\begingroup$ 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.) $\endgroup$ – 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.)

It might help to know what you wanted to use this for!

|improve this answer|||||
  • $\begingroup$ Thanks. Looks like you have a hash but no unhash/decryption method from knowledge of the key (and if you include a back door as part of the key in your last proposal, I think we lose the 1-to-1 key-to-output requirement, right?). It has been a long time, so I don't remember what exactly motivated my question, but I think I was just curious mathematically if 1-to-1 key-to-output decryptable methods existed. $\endgroup$ – bobuhito Mar 31 '19 at 20:14
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Mar 31 '19 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.