1
$\begingroup$

Suppose that $f,g,h:X\rightarrow X$ are permutations such that $f^{2}=g^{2}=\textrm{Id}_{X}$ (i.e. $f,g$ have order 2). Let $F=f\circ g$. Let $D_{f,g}$ be the distribution that takes the value $n$ where $n$ is the least positive integer such that $F^{n}(x_{0})=x_{0}$ for randomly chosen $x_{0}$.

So if $f,g$ are chosen at random, then the expected value $E(D_{f,g})$ has order around $|X|$ with high probability. However, in my experience, if $f,g$ are not chosen randomly and they have some sort of relation to each other, then $E(D_{f,g})$ often falls very close to either $\sqrt{|X|},2\sqrt{|X|},4\sqrt{|X|},\frac{4}{3}\sqrt{|X|}$. Furthermore, if $f_{1},g_{1},f_{2},g_{2}$ are all closely related in some mysterious way, then $$\frac{E(D_{f_{1},g_{1}})}{E(D_{f_{2},g_{2}})}$$ is typically very close to $1$.

For example, suppose that $X=\{0,1\}^{n}\times\{0,1\}^{n}$ and $R,S:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ are randomly selected functions. Let $f(x,y)=(x,y\oplus R(x)),g(x,y)=(x\oplus S(y),y)$. Then $f,g$ are permutations of order 2 which are related and where $E(D_{f,g})$ is typically around $2^{n}$ (The phenomenon holds even when the relation between $f$ and $g$ is more complicated. It is hard to tell when the phenomenon will hold though).

  1. What is the mathematical explanation for this phenomenon?

  2. Is there any way to predict $E(D_{f,g})$ when $f,g$ have a simple description and are easy to compute?

  3. I am wondering if this phenomenon could cause an insecurity in a symmetric cryptosystem that is constructed from permutations of order two. For example, suppose that $f,g$ are closely related permutations of order two, and suppose $h$ is another permutation of order 2. Let $\ell_{0}=f\circ g$ and $\ell_{1}=f\circ g\circ h$. Suppose that for an expanded key $a_{0}\dots a_{n-1}$, the block encryption function is $$E_{a_{0}\dots a_{n-1}}=\ell_{a_{n-1}}\circ...\circ \ell_{a_{0}}.$$ Then could there be any cryptographic weakness from the block encryption function $E$? In particular, could there be any security weakness that arises from a cryptographic hash function that arises from the Matyas–Meyer–Oseas construction from the encryption function $E$? Should I be suspicious of a possible weakness of cryptosystems of this form?

$\endgroup$
  • 1
    $\begingroup$ define, maybe with an example, closely related $\endgroup$ – kodlu Feb 10 '18 at 2:38
  • $\begingroup$ So at cstheory.stackexchange.com/q/40417/47025, I have found another example of the low period property in the reversible cellular automaton Critters and in similar reversible cellular automata. The cellular automaton Critters is the composition of two block functions which are nearly involutions. However, the low period phenomenon for Critters is much more extreme since Critters preserves the number of on states. $\endgroup$ – Joseph Van Name Mar 24 '18 at 23:40
1
$\begingroup$

So it turns out that there is nothing strange about the composition of random permutations of order 2. The thing is that the distribution of the size of the orbit of an element under the operation $g\circ f$ where $f,g$ are involutions strongly depends on the number of fixed points the functions $f,g$ and if $f$ or $g$ have large quantities of fixed points, then $g\circ f$ has small orbits.

When computing the iterates $(f\circ g)^{k}(x)$, when one encounters a fixed point of the function $f$ or of the function $g$ before going back to $x$, one begins to uncompute the iterates $(f\circ g)^{k}(x)$. After one uncomputes the iterates $(f\circ g)^{k}(x)$, one eventually uncomputes back to $x$, and at this point, one starts computing $(f\circ g)^{-k}(x)$. When computing $(f\circ g)^{-k}(x)$, one eventually encounters another fixed point of the function $f$ or of the function $g$. At this point, one reverses the direction of computation until one returns to $x$ in a complete orbit. The amount of time it takes to find the first fixed point follows an exponential distribution, and the amount of time it takes to find the second fixed point after crossing $x$ also follows an exponential distribution with the same parameter. Therefore, the amount of time it takes to make a complete orbit will be $X+X$ for some exponential distribution $X$. The probability density function of $X+X$ is $xe^{-x}$ up to renormalization however.

Observe that every permutation can be written as the composition of two involutions. However, some permutations have a much higher probability of arising as the composition of two involutions than other permutations.

Suppose $1\leq r\leq k$. If $h:[k]\rightarrow[k]$ is a random permutation, then the probability that the size of the orbit with respect to $h$ of a random element $x$ is $r$ is precisely $\frac{1}{k}$. Suppose that $f,g:[2k]\rightarrow[2k]$ are permutations selected at random subject to the condition that $f,g$ have no fixed points. Then let $P_{k,r}$ denote the probability that the orbit with respect to $g\circ f$ of a random element $x\in[2k]$ has cardinality $2r$. Then, after one performs an exact computation of $P_{k,r}$, by taking a limit, one obtains $\lim_{n\rightarrow\infty}n\cdot P_{n,\lfloor nx\rfloor}=\frac{1}{2\sqrt{1-x}}$ for all $x\in(0,1)$ (in other words, $x$ probably has a very large orbit).

Now suppose that $f,g:[k]\rightarrow[k]$ are randomly selected permutations subject to the conditions that $\{x\in[k]|f(x)\neq x\}=2m,\{x\in[k]|g(x)\neq x\}=2n$. Then let $P_{m,n,k,r}$ denote the probability that the orbit of a random element has length $r$.

Then for $x>0$, we have $\frac{k\cdot P_{n,n,k,v}}{k-2n}\rightarrow xe^{-x}$ as $v\cdot\frac{k-2n}{k}\rightarrow x,k\rightarrow\infty,v\rightarrow\infty$. (I may probably give more details as to why this is the case later on).

Now, take note that the expected value of the distribution with probability density function $x\cdot e^{-x}$ is $2$. Therefore, the expected value of the size of the orbit of a random element approaches $\frac{2k}{k-2n}$. In the scenario outlined in the question, the functions $f,g$ typically have $O(\sqrt{|X|})$ many fixed points which would ensure that there are around $\frac{2k}{k-2n}$ many fixed points.

$\endgroup$

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.