Monday, February 3, 2014

Borrowing associative and commutative properties

I was trying to come up with a set of functions that had associative and commutative properties last week, and I found a way to "borrow" those properties from addition.

Start out with a function f(x) in ZN that acts as a permutation of the elements [0..N-1]. Since f(x) is a permutation, there exists the inverse f-1(x).

From these, generate a function F(x, y) = f(f-1(x) + f-1(y)). The new binary function F(x, y) has associative and commutative properties, which it has borrowed from addition. The commutative property is obvious, because f(f-1(x) + f-1(y)) = f(f-1(y) + f-1(x)), so F(x, y) = F(y, x). The associative property works like this:

F(F(x, y), z) = F(x, F(y, z))

Rewrite in terms of f(x) and f-1(x):

f(f-1(f(f-1(x) + f-1(y))) + f-1(z)) = f(f-1(x) + f-1(f(f-1(y) + f-1(z))))

Since f-1(f(x)) = x, we can simplify both sides as follows:

f(f-1(x) + f-1(y) + f-1(z)) = f(f-1(x) + f-1(y) + f-1(z))

The number of these functions is N!, i.e. the number of permutations of [0..N-1]. These functions have a zero value i, such that F(x, i) = x. Since F is associative, for simplicity we can write F(x, y, z) for either F(F(x, y), z) or F(x, F(y, x)).

Suppose you try to build a multiplication-like function G from F, such that, for example, G(x, 4) = F(x, x, x, x). The resulting function is simply G(x, y) = f(y * f-1(x)). Interestingly, this multiplication-like function is not guaranteed to be associative or commutative. In fact, it ends up being more like an exponent than multiplication.

If someone someday figures out how to calculate the discrete logarithm in polynomial time, and thereby break a number of existing cryptographic schemes, I wonder if other exponent-like functions could prove to be less easy to break.

No comments:

Post a Comment