Document: One Way State Functions (theoretical)
Author: Robin Carey
Date: 16th Dec 2005
Revision: 1


Q: What makes a "function" one-way or non-reversible ?
Q: What makes a "function" reversible ?

To answer these questions, in terms of a state-permutation, consider
the first question:

1)	UNKNOWN START-STATE	| 1 | 2 | 3 .... | 10 |

2)	UNKNOWN PERMUTATION		||
	FUNCTION			\/

3)	KNOWN END-STATE		| 8 | 3 | 1 .... | 5 |

If you don't know what the START-STATE is, and you don't know what
the PERMUTATION-FUNCTION is, then given a KNOWN-END-STATE it is
impossible to work out what the START-STATE was (or for that matter
what the PERMUTATION-FUNCTION was); you simply "don't know" and there
are no clues in the KNOWN-END-STATE as to what they are/were.

--

With L15, the START-STATE is known (which fails one of the above two
criteria). However, the PERMUTATION-FUNCTION is not known since it
depends on the key-length and the key itself (in a complex way).
Not only that, but the L15 PERMUTATION-FUNCTION is different for
each differently sized key. And the key-length and key itself are
unknown. The END-STATE is of course known, as per the above.

So the question is: Is L15 a one-way function ?

Answer: I cannot prove that it is definitely a one-way function. However,
it is highly likely to be a one-way function, due to the complex permutation-
function, which is wholly dependent on the unknown-key. Since that function
permutes the internal state at least twice for every key, this fact increases
the chances of it being a one-way permutation.