A new public key algorithm based on avalanche properties

From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 06/13/03


Date: Fri, 13 Jun 2003 10:32:38 -0400


Here is a new public key algorithm based on
avalanche properties (and boolean complexity)
It has been developed based on feedback from
this newsgroup (Scott Fluhrer).

The overall scheme is to create a public key
by a onion-skin layered approach of permutations
of the common public value x. These commutative
permutations, due to the multiple layers and interactions
between layers, provide a degree of avalanche
complexity which makes is non-invertible.

What it needs is a means of proving these points.

Working code with a terse explanation is
at <"http://users.rcn.com/pjsteuert/rings2.c">
 
Alice forms a random secret key A.
She uses a hash function to come up with a set of
parameters based on A. These parameters are pa1,...,pa5
(in practice > 100 layers)

Then Alice forms her public key:

APub = Pa5(Pa4(Pa3(Pa2(Pa1(x))))))))

  where Pa5, etc are permutations based on those parameters.

and sends it to Bob.

Likewise, Bob forms his public key:

BPub = Pb5(Pb4(Pb3(Pb2(Pb1(x))))))))

  where Pb5, etc. are permutations based on his parameters,

and sends it to Alice.

Then Alice's would form her shared (but private to she and Bob)
key value:

AShared = AInv( BPub )
 = Ainv( Pb5(Pb4(Pb3(Pb2(Pb1(x)))))))) )
 = Pa1(Pa2(Pa3(Pa4(Pa5( Pb5(Pb4(Pb3(Pb2(Pb1(x)))))))) ))))))

Likewise, Bob would form his shared private key value:

BShared = Binv( APub )
 = Binv( Pa5(Pa4(Pa3(Pa2(Pa1(x)))))) )
 = Pb1(Pb2(Pb3(Pb4(Pb5( Pa5(Pa4(Pa3(Pa2(Pa1(x)))))) ))))))

Note that each layer is parameterized by a different
hash of the private key of that person.
And that, if each inner pair of permutations is truly
commutative, then those expressions are equal.

I used small bitfields because the commutative permutations
available were not very wide bit-wise. The attempt is
to achieve security features like avalanche and
non-invertibility between distinct bitfields.

Non-invertibility means, given APub, one can't find parameters
sufficient to form Ainv(BobPub) and thus form shared key.

These are some of the points I found:

Point 1: Start and End Layers for a Field

This controls when a field starts (startxlayer)
and ends (endxlayer) its operations (having the parameters
added to it). This is important so that
only a small fraction of the output fields are modified in the
last several layers, so that the output value cannot be
algorithmically modified by altering parameters.
(Scott Fluhrer rebutted early attempts based on this
"meet-in-the-middle" type attack.

Point 2: Initial Field value a Hash of Parameters and X

The initial field layer is not the same for each
fields. Likewise, the initial field value is not the
selected part of the common public value x, but rather
is a hash of x ALONG WITH the prior parameters for
xlayers before the current one. Since two separate
fields will each have different initial values, but derived from separate
hashes of x and several
common prior parameters, then it will be impossible to
tweak parameters before this layer. This requires that the initial
value be kept secret (or derived from x and the parameters)
for each, and that initial value added to the mix at
the appropriate place, in both the PubKey and SharedKey
computations. (even though in SharedKey computations
we haven't got to those pararameters layers yet).

Point 3: Parameter Bits Common to different Fields

Another way that altering parameters is made impossible
is because they have bit fields with many common bits. So changing
one parameter to get a certain output value will cause another
field's addend to change.

Point 4: Divergence

When an inner field stops being added-to
(i.e. it's startlayer == xlayer) in the inverse
phase of computing BInv(APub) (or AInv(BPub),
there are no more additions to that field. Further the
value is symmetric at that point, and identical
for both Alice: AInv(BPub) and Bob: BInv(APub)
Any non-linear function or hash of that value
can be added to all other fields at that point.
That hash can also depend on any symmetric factors,
such as xlayer and xfld number.

Point 5: Homomorphic Convergence

The purpose of convergence is to make it difficult
to model with boolean equations the paramter bits.
In particular, for fields of the MOD2K TYPE,
a homomorphic (H(x+y) = h(x) OP h(y)
operator will preserve the commutativity.
That operator is to left shift the smaller field
into the wider field with 0s on the right, and then to add it
mod 2"wider. This will generate some complex wrap-around logic.

Point 6: A better Homomorphic function

A better homorphic functions for different MOD2K fields
H(i1+i2) = H(i1) + H(i2) can be had. The original
function shifted the narrower source field to left-justify it
in the wider fields. A better solution is to
left-pad it with all 1's. This allows more bits to be
influenced.