Nested Rings of different types for Public Key

From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 05/29/03 

Date: Thu, 29 May 2003 14:43:46 -0400

Does anyone have an opinion as to the security of this method?

Consider the following permutations,
where each permutation Pai is parameterized by
a different hash of the secret key A (or B).

Let AFunc(x) = Pa8(Pa7(...(Pa0(x))...))
and BFunc(x) = Pb8(Pb7(...(Pb0(x))...))

A permutation can be defined as embedded or nested
recursively with different rings of each
lower level of n/2 bits.

One simple parameterization example,
where a0 and a1 are each 512-bit parameters, is
Pai(XBARi) = ABARi*XBARi,
where ABAR is a 1024-bit parameter vector (a0,a1)
and XBAR is the 1024-bit input vector (x0,x1).
and where ABAR times XBAR = ( (a0*x0+a1*x1),(a0*x1-a1*x0) )
and ABAR plus XBAR = (a0+x0,a1+x1).
The multiplication permutation Pai is commutative,
where (*,+) is a commutative ring of 512-bit
values.

These operations can then be defined recursively
for n/2 bits, then n/4 bits, then n/8 bits, and so on.
GF(2^k) can be used, and for smaller bit sizes,
other rings defined on 2^k elements can be used.
Those GF operations can be done in different
irreducible polynomials at the different levels
of embedding (extensions in the GF(2^n) cases).

Because of the nesting, every output bit of
a permutation is dependent on every input
bit of the permutation and the parameterizations.

Different rings should be applied at different levels.
Additional parameters can also be based on the permutation stage i
and also on embedding level in the particular
permutation. This is because the commutativity of these
rings is independent of the parameters.

The parameters should be different hash output bits of
for each stage and level of nesting, as in
a0 = hashik0(A), a1=hashik1(A).

Because of commutativity,

Shared Key = BFunc( AFunc(x) ) = AFunc( BFunc(x) )

where AFunc(x) is Alice's public key and BFunc(x) is Bob's public key.

The permutations are all mutually commutative
and can be applied in any order.

A commutative ring operation could be defined as
(a OP+ b) = a+b-1 and (a OP* b) = a+b-ab in GF(2^k).

Commutative rings can be also constructed randomly (but must be
commonly known to both Alice and Bob).

At the lowest 2-bit level, the ring operation could
be the following simple commutative ring, where
a,b,c,d are some encoding of 00 01 10 11 bit values.

+ a b c d
=========
a a b c d
b b a d c
c c d a b
d d c b a

* a b c d
=========
a a a a a
b a b c d
c a c d b
d a d b c

  -Jim Steuert