Schneier on Security

Alex • September 15, 2008 6:21 AM

“”Almost any cryptographic scheme can be described by tweakable polynomials…”

I don’t doubt that this is true. But could someone educate me as to why this is true? That is, why are cryptograpic schemes based on non-polynomial functions uncommon?”

I may be barking up the wrong tree but here is a possible explanation.

Remember that any encryption scheme is just a way to pair a finite number of inputs with the same number of outputs. In this light, the statement is just saying that in most encryption schemes we can fit a polynomial of order = (#inputs-1) so that it passes through all (input, output) pairs.

Eg, say our encryption scheme is 0 –> 1, 1 –> 0. There are two pairings so we want a polynomial of degree one:

f(x) = ax + b

We plug in our desired pairings f(input) = output and solve for the coefficients a and b.

f(0) = 1 and f(1) = 0, so

a0 + b = 1 ==> b = 1
a1 + b = 0 –> a + 1 = 0 ==> a = -1

So the polynomial:
f(input) = 1-1*input

completely matches the given encryption scheme as every input is mapped to the desired output.

To see there’s a way to do this for any pairing provided each input has a single output:
http://en.wikipedia.org/wiki/Lagrange_polynomial

~~~~~~~~~~~~~~~~~~~~~~~

Some complications:
1) Our encryption scheme doesn’t only depend on the input message, it also depends on the key. ie, we want an f(input,key) not just f(input). In practice I guess this might mean that the coefficients for the polynomial depend on the key.

For our simple example above we could have:
f(key, input) = ( (-1) ^ key ) * input + key

where key, input, and output are in {0,1}

2) The polynomial may not be over the real numbers. To do the Lagrange polynomial thing it seems you need multiplicative inverses. Hence, I would guess you can use polynomials to model any function from a field into itself. http://en.wikipedia.org/wiki/Field_(mathematics) You may not need that much or you may need more conditions – I’d have to think about it.