2
$\begingroup$

So we want to bijectively map one path to another. But depending on start and target node we can only choose from a subset of all transitions. It would look like this:

enter image description here

We also do not know where one transition is leading us. So we firstly need to go it and check if it is a valid target starting from the prior value (chance $p$). If not we need to test another transition.

For the path we staring on (left in picture) we already know it contains only valid transitions.
Now how can we map this path to another path which starts on a new value. (We need to find a valid path from there)
If we now apply the inverse mapping function on the found path we need to end on the path we started from (to be bijective).

How can we do this more effectively than mapping the full path to another potential full path until one is working out? Could we do it step by step?


More detailed description related to target use case:

Intro:
In target use case each transition is made by a permutation of index $k$ (unknown order) with a permutation function $B$. After done this permutation start $x_i$ and end $x_{i+1}$ will be evaluated by a function $p(x_i,x_{i+1})$. This function decides if we can use this path or not.
If yes, we can continue at the next level $i+1$.
If not, we need to find another permutation index $k$

Furthermore the permutation index is not symmetric. It will be altered by function $b$ using the starting point $x_i$.
That means we can't compute the inverse of it without knowing the start point.
All this will be combined in a path-transition-function $P$ which eiter gives us a new point of the next level or an empty set if this combination of start point and permutation index is not possible.

Given now a path which has a valid starting point and permutation index for each level we want to transfer it to a new working path which also has valid starting point and permutation index for each level.
This need to be reversible. So if we have given the resulting path and make the inverse transfer/mapping function we end up at the path we started from.


Here the math details about it:

Given a black-box permutation function $$B(x_i,k_i) \rightarrow x_{i+1}$$ which gives the $k_i$'th permutation (order unknown) of input $x_i$. This function is bijective, so we can do $\forall x_{i},k_i$ $$B^{-1}(x_{i+1},k_i) \rightarrow x_i$$

Now there is a 2nd bijective function $$P(x_i,k_i) \rightarrow \{(x_{i+1},k_i') \cup \{\} \}$$ $$P^{-1}(x_{i+1},k_i') \rightarrow \{(x_{i},k_{i}) \cup \{\} \}$$ with output $k_{i}'$ which is a permutation of the permutation index.
This function $P$ delivers only a output of a subset of all inputs (set is unknown). Else just an empty set $\{\}$
It only has a chance of $p$.


Internally integer values $x_i \in [0,2^{128}-1]$ will be used.
With this we can write $p$ as: $$ p(x_i,x_{i+1}) = p(x_{i+1},x_{i}) = \begin{cases} 1 && \text{ if } & p\cdot 2^{128} - (x_i \oplus x_{i+1}) > 0 \\ 0 && \text{ else } \end{cases} $$ $\oplus $ being a binary xor operation.
This gives us an average value of $p$ $$\operatorname{E}(p(x_i,x_{i+1})) = p$$

To compute function $P$ another bijektive function $b$ will be used $$b(k_i,x_i) = k_i'$$ $$b^{-1}(k_i',x_i) = k_i$$ $$ \begin{split} P(x_i,k_i) & = \begin{cases} (B(x_i,k_{i+1}) , k_i') && \text{if} & p(x_i,x_{i+1}) = 1\\ \{\} && \text{else} \end{cases} \\ P^{-1}(x_{i+1},k_i') & = \begin{cases} (B^{-1}(x_{i+1},k_i) , k_i) && \text{if} & p(x_i,x_{i+1}) = 1 \\ \{\} && \text{else} \end{cases} \end{split} $$

So given inputs $x_i,k_i$ we only have a chance of $p$ it is working. If $B$ or $B^{-1}$ is working the inverse of it is also working.

The inverse $P^{-1}$ we can only compute if we already done $P$ and know it's input $x_i$ else we do not know which $k_i$ we have to use.


Now given a function series with parameters series $k_1$ to $k_8$ $$P(x_1,k_1) = (x_2,k_1')$$ $$P(x_2,k_2) = (x_3,k_2')$$ $$P(x_3,k_2) = (x_4,k_3')$$ $$...$$ $$P(x_8,k_8) = (x_9,k_8')$$ We know $P(x_i,k_i)$ did work out for all chosen parameters $x_1,k_1,k_2,..k_8$.
So $\forall i$ $p(x_i,x_{i+1} ) = 1$

Now I'm looking for a bijective mapping $M$ of those parameters to a new set of parameters $x^*_1,k^*_1,k^*_2,..k^*_8$ which could be used in real world even if $p$ is quite small. Meaning it should be computable by a normal PC in less than some seconds.
This mapping should not be predictable and for this has to use function $B$ or $P$ to some extend. $$M: (x_1,k_1,k_2,..k_8) \leftrightarrow (x^*_1,k^*_1,k^*_2,..k^*_8)$$


Too slow put possible solution:
For example we could do:
Finding the first suitable $j=m$ $$(x^*_1,k^*_1,k^*_2,..k^*_8) = (x_{1,m},k_{1,m},k_{2,m},..k_{8,m})$$

firstly make a shorter notation for all the $8$ $k_i$ $$M(x_1,k_1,k_2,...k_8) = M(x_1,K_1)$$ To find $M: (x_{1,1},K_1) \leftrightarrow (x_{1,m},K_m) $ we could try for success until it works with following algorithm with: $$x_{1,1} = x_1$$ $$B(x_{1,j},K_j) = c_j$$ $$K_{j+1} = K_j \oplus c_j$$ $$B^{-1}(c_j,K_{j+1}) = x_{1,j+1}$$

we convert $K_{j+1}$ back to 8 $k_{i,j+1}$ and check if $P$ function series works out with those parameters: $$P(x_{1,j+1}, k_{1,j+1}) \overset{?}= (x_{2,i+1} , k_{1,j+1}' )$$ $$P(x_{2,j+1}, k_{2,j+1}) \overset{?}= (x_{3,i+1}, k_{2,j+1}')$$ $$P(x_{3,j+1}, k_{3,j+1}) \overset{?}= (x_{4,i+1}, k_{3,j+1}')$$ $$...$$ $$P(x_{8,j+1}, k_{8,j+1}) \overset{?}= (x_{9,i+1}, k_{9,j+1}')$$

$\overset{?}=$ stands for $P(x_{i,j+1},k_{i,j+1})$ only has a chance $p(x_{i,j+1}, x_{i+1,j+1})$ to not deliver an empty set $\{\}$.
If one fails and gives $\{\}$ we repeat the calculation to get $x_{1,j+2},K_{j+2}$ and so on until all $P$ working out.
We set $m := j$ and done.

Now given any resulting $x_{1,m},K_{m}$ we can easily compute it in inverse direction and end up at the same values $x_{1,1},K_{1}$ we started from.

In target use case $x$ and with this also also $c$ have a bit length of 128-bits. $k_i$ have a bit-length of 16-bits each. With 8 times $k_i$ in $K$ this also has a bit-length of 128-bits. $k_i'$ has a bit-length of 80 bit


However chance of finding a valid configuration is only: $$p^8$$ For target chance $p\approx\frac{1}{100}$ this would result in a too long computation time. Even if each step could be done in one cycle it would take days for a current standard desktop PC.


Now my question is can we do any better? Best would be $< O(\frac{1}{p^3})$ calculations. Need to be at least$< O(\frac{1}{p^5})$

Only way I can think of is making this $P$ calculation step by step by instead only taking the first $k_1$ instead of all in $K_1$ $$B(x_{1,j},k_{1,j}) = c$$ $$k_{1,j+1} = k_{1,j} \oplus c \text{ } \text{ only xor the bit size of $k_1 = 16$ here}$$ $$B^{-1}(c_j,k_{1,j+1}) = x_{1,j+1}$$ And repeat until finding a valid $P(x_{1,m},k_{1,m})$ which does not return $\{\}$.
This operation would still be bijective.

But how can we add the other $k_i$ while still staying bijective?
Or any other ideas to solve this?


Further notes
To be complete a special case for $P^{-1}(x_{i+1},k_i')$ with $k_i'=0$ will be mentioned here.
As written above to compute $P^{-1}$ we first need to compute $P$ to know valid parameters.
$k_i' = 0$ is a special case constant $$P^{-1}(x_{i+1},k_i'=0) = (x_i, k)$$ To be specific $k$ will be the first 16-bit of $x_i$. which does always work with probability $1$ $$p_{k_i' = 0}(x_i,x_{i+1}) = 1$$ Assuming all $k_i' = 0$ we could do a bijective mapping from $x_{8,1} \leftrightarrow x_{8,2}$ with $$B(x_{8,1},0) = c$$ $$B^{-1}( \mathbf{1} - c,0) = x_{8,2}$$ For $k_j' \not = 0$ we could only do a one directional mapping to a case with all $kj' = 0$. But the inverse of this would be bidirectional again (with all $k_j = 0$).

Edit: We are also allowed to make some further assumptions about the given $x_1,k_1,..,k_8$ unless they destroy (almost) all other paths.

Edit2:
We might can reduce the problem to some smaller one.
Inside the mapping function we could write the used $k_j$ in a different order than we have used them inside the working starting path.
Given this we can allow every combination of the permutation indices to be tested. For 16-bit $k_j$ we would have $8$ options in step $1$, next step $7$, $6$ and so on. Much more but still not enough. We can therefor splice them in half. Giving us $64$, $49$, $36$, .. combinations. We could also allow to swap their position, giving us $240$, $182$, $132$, $90$,.. options.
This will make it much likelier we can find a valid path among this.
There is a small chance finding a 2nd combination inside the starting path which makes this invalid. That would be ok for target use case.

'Only' thing we need now is a obfuscation function which maintains the order or brings it in another specified order. This can happen also after multiple trials as long they are not too many to keep the total cost in some limit. This function need to be bijective to work out.
(Just adding a constant or the same variable to every byte is not enough obfuscation)

Any ideas? This alone would also count as answer.

$\endgroup$
11
  • 3
    $\begingroup$ This is a lot to read. I'm not sure what is meant by "$P$ delivers only output of a subset of all inputs", or what "working" means. I find it confusing that you change the variables and meaning of variables partway through the question. I don't understand what "did work out" means, or what determines whether something "could be used in real world". $\endgroup$
    – D.W.
    Commented Apr 13 at 22:31
  • $\begingroup$ @D.W. $P(x_i,k_i) \rightarrow x_{i+1}$ only has a chance to delivers some result depending on $x_i$ and $x_{i+1}$. I could have wrote another function $Q$ which computes $P$ and only outputs the result $x_{i+1}$ if another function $q( x_i, x_{i+1}) < 0$ . e.g. $q( x_i, x_{i+1}) = (x_i \oplus x_{i+1} )- p \cdot 2^{16} < 0$ is fulfilled. Else it returns an empty set, an error or similar. At this example $q$ would most likely be $>0$ for small chances $p$. So $Q$ or $P$ in text will not work out but instead deliver only an empty set. ... $\endgroup$
    – J. Doe
    Commented Apr 14 at 3:50
  • $\begingroup$ ...We need to repeat until we found one solution which does not returns an empty set. If we found it the algorithm terminates. With in real world I meant it need to be calculated on a PC without waiting hours for it. With $p \approx \frac{1}{100}$ the chance of all 8 $P$ (or with extra function $Q(P)$) would return not empty set would be $p^8$. Even if a PC computes every $B$ in one cycle it would take weeks until complete. But if there is a way to not throw away all $P$ already passed this could be done in less than a second. $\endgroup$
    – J. Doe
    Commented Apr 14 at 4:02
  • 1
    $\begingroup$ @kodlu Sometimes insights about boring problems can lead to insights about more interesting one. Problem description might be not too hard after all. I'm just missing the correct words to describe it accurately. This can also happen in new fields. It fist need to be characterized and classified to speak about it more effectively. The related crypto question was made as another check to not forget something. I'm pretty confident it is working this time. Btw the chance $p$ noted here will increase the security to $\approx 2^{95}$ ... $\endgroup$
    – J. Doe
    Commented Apr 14 at 19:41
  • 1
    $\begingroup$ @Karl the math part after the picture is supposed to be the problem description. I changed the header to make it more clear. $\endgroup$
    – J. Doe
    Commented Apr 16 at 21:22

1 Answer 1

0
$\begingroup$

Looks like nobody got another idea.
Here one solution:
As written in top part we can sort the keys used for the given working path into a list. This only works if there is no other combination of those keys resulting in a working path. This requires a low chance $p$ (as it was stated).

We can encode this sorted list into a number shown here:
https://cstheory.stackexchange.com/questions/19313/optimal-encoding-of-k-subsets-of-n

To make it not predictable we can e.g. apply function $B$ on it.

After that we can decode it again. We check every combination of being a working path.

If we found a single one, we also found a bijective mapping to another path.
If we found 0 or more than 1, we apply function $B$ again and try with the next sorted list.

Here a related thread to this problem:
https://crypto.stackexchange.com/questions/111472/is-there-any-bijective-obfuscation-scheme-which-maintains-a-byte-order-e-g-sor

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .