Is there any bijective obfuscation scheme which maintains a byte order (e.g. sorted) or does so after not too many trials? (for 128bit = 16 byte)

Question

We have given 16 bytes and apply some order to them. For example sorting them by their absolute value.
We want to obfuscate them as best as possible while maintaining their order. That means if we apply the order function after the obfuscation (e.g. sorting them) nothing should change.
If it did not work out we are allowed to obfuscate them again until they are in order.
This should happen as least as possible.

Need to be bijective, so applying the inverse obfuscation function at the result will end up where we started in forward direction.

For variation of the obfuscation function we have given a 128-bit value $x$ (which also needed to be obfuscated at the very end, order not relevant for that).

---

Example (which needs too many operations)

Let $B_s$ be our 16-bytes in sorted order. We can use AES for obfuscation $$AES(x,B_s) = c$$ Apply xor on it $$B_{x} = c \oplus B_s$$ To make them less dependent again we apply AES again $$AES^{-1}(x,B_x) = x'$$

If $B_x$ is in order we end. If not we repeat those 3 calculations until it is (starts with $AES(x',B_x)$ this time).

This will (mostly) work out but will take way too long. If all bytes are different chance are only $\approx 1:2^{44}$ to be in order.

Can we do (much) better? Looking for something as quick as possible. $< 2^{16}$ trials wood be ok. The smaller the better.

---

Further requirements:

• Obfuscation by just a constant or a single variable or just $\pm 1$ for all bytes is not enough obfuscation.
• Obfuscation need to depend on the 2nd input $x$.
• Chosen order need to be well specified unless two bytes are equal it need to be deterministic if byte $a$ stands before or after byte $b$
• Doing obfuscation $n$ times should not be able to be simplified to compute it much faster than doing it $n$ times. Even with knowing all runtime variables.
• (Variance of trials not too high)

Allowed:

• The order function used before the forward obfuscation function does not need to be equal to the order function of the result or in other words the order function applied before doing the inverse obfuscation function. So e.g. we could start with bytes sorted ascending and end with bytes sorted descending.

Some weakening
Best would be as described above but to higher the chances we could split the 16-bytes in two groups of 8 bytes each. Order only need to be maintained inside those groups. Further order group splitting not allowed.

Doing this with the top approach highers the chances to $~ 1:2^{30}$. Still too long. With the weakening it should not take longer than $2^{6}$ trials.

---

Yes, obfuscation and maintaining are in conflict to each other.

Answer 1

(I assume that the 16 bytes are all different. If this is not the case, what follows can be easily adapted.)

If you care only about obfuscating sorted sequences of bytes of fixed length, you could interpret them as subsets of the numbers from 0 to 255, and encode them like described in Optimal encoding of k-subsets of n as numbers, use a format-preserving encryption (i.e., an encryption algorithm that works on sets of arbitrary order, no just powers of 2) to encrypt that numbers, and decode the ciphertext again to a subset/ordered sequence.

---

Edit(TO):

For completion I will write the linked thread again here with some modification to be applied to values $n \in [0,255]$.

The idea is to encode our sorted byte series $B_s$ into a number $x$, encrypt this number and afterwards decode this number back to a sorted list.

The idea is based on sets and not on sorted lists. Therefore $B_s$ need to contain $16$ different values $$|\{B_s\}| \overset{!}= 16$$

Each byte represents a number from 0 to 255 represented by $n$.

---

Encoding:
To encode it into a number $x \in [0,\binom{256}{16})$ we start with $x\operatorname{ENCODE}(B_s,n=255,k=16)$ and do:

$x = \operatorname{ENCODE}(B_s,n,k)$:

1. If $k = 0$, return $0$.
2. If $n \notin B_s$, return $\operatorname{ENCODE}(S,n-1,k)$.
3. If $n \in B_s$, return $\binom{n}{k}+\operatorname{ENCODE}(S,n-1,k-1)$.

So as we know $B_s$ is already sorted we can just start with the last element.

---

Encryption:

Max of $x$ is slightly above 83-bit. We apply a format-preserving bijective encryption of choice on those. $$\operatorname{Encrypt}(x) = x_e$$ Our encrypted $x_e$ also need to be in target range $[0,\binom{256}{16})$

---

Decoding

We can then apply $\operatorname{DECODE}(x_e,n = 255,k = 16)$ to generate the sorted encrypted equivalent $B_{es}$ of our starting series $B_{s}$

$B_{es} = \operatorname{DECODE}(x_e,n,k)$:

1. If $k = 0$, return $\emptyset$.
2. If $x_e < \binom{n}{k}$, return $\operatorname{DECODE}(x,n-1,k)$.
3. If $x_e \geq \binom{n}{k}$, return $[\text{ } \operatorname{DECODE}(x - \binom{n}{k},n-1,k-1)\text{ } \text{ }, n]$.

As we start from the highest $n$ and fill up $B_{es}$ in reverse oder we will end up with a sorted list.

---

Edit2:
For allowing equal values we can extend the max $n$ by $15$.
After sorting them we add their index to the value. They remain sorted but guaranteed to be different.
After decoding we subtract the index again.