In this talk we will introduce a new public key system, the "Tame Transformation Method" or TTM. One should not view "TTM" as an abbreviation of "Time To Market" nor of "Time To Money". Many years ago, I wrote a text book "Algebra" for graduate students. In there I mentioned RSA as a cute example of number theory. In the summer of 1995, Dr. John M. Acken of Intel came to visit my family. He raised the question of a fast public key system. I reviewed my book and realized that classically people glued a big chunk of characters together, say 128 characters with each an 8 bits number, so one got 1024 bits. Then one viewed this huge data as a binary whole number. One played with those 1024 bits numbers in a modular sense. It is naturaly slow to manipulate those numbers. It is essentially the same for ECC and other group-theorectic ones.
Maybe I shall mention that the public key system is not a mathematical problem. Most mathematicians will dismiss any discussion about public key systems which can be solved in finitely many steps.
Mathematics or not, public key system is interesting in itself. Let a1,...,a128 be 128 characters with each an 8 bits number. The natural way is not to glue them together. We shall treat them as a point a=(a1,...,a128) (a so called "plaintext") in 128 dimensional space. To scramble it, we simple apply a map f to the 128 dimensional space and get a new point b=(b1,...,b128) (a so called "ciphertext"). For the conveniece of computation, we require that
(a) both value f(a) and its inverse value f-1(b) can be computed easily.There are ready candidates "Tame Automorphisms" (see below). Furthermore we require the coefficient field of the 128 dimensional space to be the finite field GF(28) (see below). Thus all computations will be fast.
(b) a composition of a few of the maps should be hard to be decompsed and its inverse hard to be recovered.
(c) it should be user-friendly.
The beauty of Tame Automorphisms is that after compositing a few of them, the resulting map loses all appearances of a Tame Automorphism (cf the example below). For a technique reason, we shall select the space of plaintexts to be a subspace of this space (of ciphertexts). Then we have a fast public key system.
(a): Finite Field.
We shall discuss the concept of finite fields. The finite field GF(2m) of 2m elements is the collection of the m bits numbers (a1,a2,...,am) , where ai's are zeroes or ones, and the sum of m bits numbers is bitwise, while the product depends on the defining irreducible polynomial, which can be carried out by a LSR (linear shift register) or by looking up a table.
(b): Affine Space.
Let K be a field, say GF(2m). Let Kn+r be the affine space of dimension n+r over K. Note that an "affine space" Kn+r is a vector space without the algebraic structure and the origin, i.e., the "physical space". We prefer an affine space over a vector space because (1) we need to move the origin around, (2) we shall consider non-linear maps such as polynomial maps.
(c): Tame Automorphism.
A linear transformation f is a map of the following form,
f(xi)=ai1x1+...+ai(n+r)xn+ r+biwhere aij and bi are elements in K. A linear transformation f is said to be invertible if the coefficient matrix (aij) is invertible.
Definition: We define a tame automorphism fi=(fi,1,..., fi,n+r) as either an invertible linear transformation, or of the following form in any order of variables x1,...,xn+r with polynomials hi,j,
(1): fi,1(x1,..., xn+r)=x1+hi,1(x2,...,xn+r)=y1Example: Let K=GF(2), f(x1, x2, x3) =(x1+x2x3, x2 +x32, x3), g(x1, x2, x3) =(x1, x2, x3+x12) be two tame automorphisms. Then it is easy to see that f2(x1, x2, x3)=(x1+x33, x2, x3) and fg(x1, x2, x3) =(x1+x2x3 +x12x2, x2+x32 +x14, x3+x12) .
(2): fi,2(x1,..., xn+r)=x2+hi,2(x3,...,xn+r)=y2
..........................
(j): fi,j(x1,..., xn+r)=xj+hi,j(xj+1,...,xn+r )=yj
..........................
(n+r): fi,n+r(x1,...,xn+r)=xn+r=yn +r
The group generated by all tame automorphisms is called the tame automorphism group. Note that the group product is the composition of maps, i.e., substitution (cf the previous example), which is different from the product of polynomials. The following proposition and its corollaries will be given without proofs.
Proposition 1: Let a tame automorphism fi be defined as in the preceding paragraph. We have the inverse f-1 =(fi,1-1,...,fi,n+r-1) with xn+r=fi,n+r-1(y1,..., yn+r)=yn+r and xj= fi,j-1(y1,...,yn+r)= yj-hi,j(fi,j+1-1(y1, ..., yn+r),...,fi,n+r-1(y1,..., yn+r)), for j=n+r-1,...,1.
For instance, in the case of four variables, we have the inverse polynomial map fi-1 in the following abstract general form in term of variables,
fi,4-1(y1,...,y4)=y4 .In general, the total degree of fi,j-1(y1,..., yn+r) increases very fast and the number of terms can be quite large. As can be shown, the number of terms in g-1 in our scheme is greater than 10254. Therefore it is impractical to actually write down the inverse map. However, if a point (y'1,..., y'n+r) is given, the value of the inverse map can be readily computed in the following special form in term of numbers.
fi,3-1(y1,...,y4)=y3 -hi3(y4).
fi,2-1(y1,...,y4)=y2 -hi2(y3-hi3(y4),y4).
fi,1-1(y1,...,y4)=y1 -hi1(y2-hi2(y3-hi3(y< sub>4),y4),y3-hi3(y4),y4).
Corollary 2: Given a set of values (y'1,..., y'n+r) in Kn+r and a tame automorphism fi as in the Definition of this section, then the values (x'1,..., x'n+r) =(fi,1-1(y'1,...,y'n+r),..., fi,n+r-1(y'1,...,y'n+r)) can be found by induction; first, we have x'n+r =fi,n+r-1(y'1,...,y'n+r) =y'n+r, inductively we have x'j+1,..., x'n+r in K, then we have x'j =fi,j-1(y'1,...y'n+r) =y'j-hi,j(x'j+1,..., x'n+r) for j=n+r-1,...,1.
Corollary 3: Given the decomposition g=f1....fs where fi are tame automorphisms, then we have g-1=fs-1... f1-1. Furthermore, if a set of values (y'1,..., y'n+r) is given, then we have g-1(y'1,..., y'n+r) =fs-1...f1-1 (y'1,..., y'n+r).
There is an abyss between our knowledge of the automorphism group of K2 and the automorphism group of Kn+r for n+r greater than or equal to 3. In these cases, every element g in the tame automorphism group has a factorization into a product of tame automorphisms by its definition, however, there is no known way to find it. In 1972, a very good mathemtician, M. Nagata constructed an automorphism g for n+r=3. One can not decide whether g is in the tame automorphism group since there is no theorem for the above factorization. Note that one can show that the square root of 2 is not rational since we know the factorization theorem for integers.
Let the restriction of g to the n dimensional subspace be g'=(h1,..., hn+r): Kn--> Kn+r. The field K and the polynomial map (h1,..., hn+r) will be announced as the public key.
Given a plaintext (x'1,...,x'n) in Kn, let y'i=hi(x'1,...,x'n), then the ciphertext will be (y'1,...,y'n+r).
Given tame automorphisms fi and a ciphertext (y'1,..., y'n+r), it is easy to find fi-1 (y'1,..., y'n+r). Therefore, the plaintext can be recovered by taking (x'1,...,x'n,0...0) =f1-1 f2-1...fs-1( y'1,..., y'n+r). The private key will be the set of maps {f1-1,..., fs-1}.
(1) all componenets, q*i, of it are polynomials in 64 variables of degree 2.Furthermore, we require that the linear transformation f1 to move the origin (0,...,0) to a point (b1,...,b64) where all bi 's are nozeroes, and the linear transformation f4 to make the composition f4f3f2f1 fixes the origin. The reason is that then all linear forms of q*i's will not form an linear transformation of the vector space K64. The purpose of the above requirement is to safeguqrd the linear terms from an attack using linear algebra.
(2) the degree 2 homogeneous parts of q*i's are linear independent.
(3) no polynomial in q*i's of degree less than 8 will generate a power of any polynomial of degree 1.
Of equal importance to having a large number of possible plaintexts is having lots of possible users. In order to allow for many such users, we first get an expression for this number in terms of 8 and 64. This amounts to counting the number of automorphisms g of the form g=f4f3f2f1. Assuming that a negligible proportion of these automorphisms g have more than one representation g=f4f3f2f1 =f'4f'3f'2f'1, the number of users is asymptotic to (choices for f4) (choices for f1). We may use the possible numbers for the invertible linear transformations as an estimation for f4, f1. The number of invertible linear transformations f1 is greater than 233279. A similar count of terms of f4 results in the total possible number of users is greater than 2114079.
Now let us look at the compactness of the scheme. We have 100 quadratic polynomials in 64 variables. It is easy to see that the number of terms of polynomials of degree 2 is (67)(64)/2! and we have 100 polynomials, therefore the total number of terms is 214,400 (for another software implementation TTM 2.8, the number is 20,736). This is the size of the public key. We believe that the number can be further reduced. The expense to the sender is mainly in evaluating the 100 polynomials. Note that our scheme can also be computed in a parallel way. Thus the process can be sped up several hundred fold. On the receiver's side, the total number of terms for f1, f2, f3, f4 is 17,000 (the corresponding number for TTM 2.8 is 4,800). This is the size of the private key. The legitimate receiver needs to evaluate f1-1f2-1 f3-1f4-1 (according to Corollaries 2 & 3) which is not expensive.
250 Mhz PowerPC 750 (G3)
200 Mhz PowerPC 604e w/1024K cache.
225 Mhz PowerPC 603e w/256K cache,
167 Mhz Ultrasparc w/512K cache.
167 Mhz Pentium w/512K cache.
The software TTM 2.1, 2.3, and 2.5 are on 200 Mhz PowerPC 604e (w/1024K cache: virtual memory off) and the software TTM 2.8 is on 250 Mhz PowerPC 750 (G3). Their speeds are listed in the following;
TTM 1.9, 94,939 bit/sec
TTM 2.1, 106.224 bit/sec
TTM 2.3, 207,000 bit/sec
TTM 2.5, 300,000 bit/sec
TTM 2.8, 617,363 bit/sec
The implementation speed depends on the speed to compute a*b+c where a,b and c are in the 8-bits finite field. For TTM 2.8, every 108 repeatitions of this computation will process one bit of imformation, while each computation requires 3.75 cycles. It is interesting to note that the newly announced Motorola "AltiVec" chip will provide "table walks" and parallel computation, thus speeds up the process.
The decrypting speed is in general 4 to 15 times faster than the encrypting speed. The PC software TTM 2.8 is faster than a possible hardware implementation for RSA 1024. According to the opinion of a certain expert, a couple added instruction about finite field multiplication in the chip architecture would increase the speed of software implementations at least 10--16 times. If it is done, then our software implementations would reach a few million bits per second for the PC.
It is possible to encrypt voice communications(64,000 bit/sec) by those softwares on an ordinary PC. Note that in comparison, RSA toolkit BSAFE 3.0 for 1024 is 7 K bit/sec. It is conceivable that a hardware implementation, using finite field multiplication and parallel computing, would approximate the speed of the fastest hardware implementation of the triple DES 128.
The other methods one may use are "search for polynomial relations" and "identify the highest homogeneous parts" . It can be shown that they are ineffective.
Finally we may use the "brute force attack" as follows: The attacker has the 100 polynomials {f1,...,f100). Then the attacker assign random values from the field K for {x1,...,x64} to see if the assigned values are correct. It is easy to see that the possiblities is one in 10153. Assuming it only take one clock cycle to test if a set of 64 random numbers is correct, the attacker still need 3* 10139 misp (one million instruction per second) years to crack the scheme. In comparison, it requires 3* 1020 mips years to cracked RSA 2048.