Re: 3-instruction one-way function. Invitation

From: Mark Wooding (mdw_at_nsict.org)
Date: 08/22/03 

Date: 21 Aug 2003 23:45:16 GMT

Francois Grieu <fgrieu@micronet.fr> wrote:

> Now we have the definition of the mysterious 3-instructions
> function. It is Q(x) = P(P(P(x))+1) where P(x) is a
> permutation of {0..255}, and addition is modulo 256.

Right. So, it's a (conjectured) one-way function /on/ permutations --
that is, it acts on elements of $S_{2^8}$. Let $\sigma \in S_{2^8}$ be
a cyclic permutation of all 256 elements; then for any $\pi \in
S_{2^8}$, define

  Q(\pi) = \pi \sigma \pi^2

and claim that $Q(\cdot)$ is one-way.

Hmm. I can see why $\pi^3$ is not one-way; but my rather weak group
theory isn't up to inverting $\pi \sigma \pi$, let alone $\pi \sigma
\pi^2$.

Hmm again. $\sigma = \pi^{-1} Q \pi^{-2}$. No, that doesn't help.
Looks interesting.

-- [mdw]

Quantcast