METHOD AND APPARATUS FOR ESTABLISHING A KEY AGREEMENT PROTOCOL

Abstract

A system and method for generating a secret key to facilitate secure communications between users. A first and second and a function between the two monoids are selected, the function being a monoid homomorphism. A group and a group action of the group on the first monoid is selected. Each user is assigned a submonoid of the first monoid so that these submonoids satisfy a special symmetry property determined by the function, a structure of the first and second monoids, and the action of the group. A multiplication of an element in the second monoid and an element in the first monoid is obtained by combining the group action and the monoid homomorphism. First and second users choose private keys which are sequences of elements in their respective submonoids. A first result is obtained by multiplying an identity element by the first element of the sequence in a respective submonoid. Starting with the first result, each element of the user's private key may be iteratively multiplied by the previous result to produce a public key. Public keys are exchanged between first and second users. Each user's private key may be iteratively multiplied by the other user's public key to produce a secret key. Secure communication may then occur between the first and second user using the secret key.

Claims

1. A method for securing communications from a user, the method comprising: selecting a first monoid; selecting a second monoid; selecting a function, the function being a monoid homomorphism that maps the first monoid to the second monoid; selecting a group; selecting an action of the group on the first monoid; determining a semi-direct product of the first monoid and the group to produce a third monoid; selecting a first and second submonoid of the third monoid, a pair of the first and second submonoids satisfying a criterion, the first submonoid being defined by a first set of generators, wherein the criterion satisfies a property determined by the function, a structure of the first and second monoids, and the action; and selecting a plurality of generators of the first set of generators to produce a private key.

2.-23. (canceled)

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0013] FIG. 1 is a system diagram illustrating a II-Function module in accordance with an embodiment of the invention.

[0014] FIG. 2 is a system diagram illustrating a S-Action module in accordance with an embodiment of the invention.

[0015] FIG. 3 is a system diagram illustrating an E-Function module in accordance with an embodiment of the invention.

[0016] FIG. 4 is a system diagram illustrating the operation of an E-Function iterator module in accordance with an embodiment of the invention.

[0017] FIG. 5 is another system diagram illustrating the operation of an E-Function iterator module in accordance with an embodiment of the invention.

[0018] FIG. 6 is a system diagram illustrating a system for determining a pair of E-commuting monoids in accordance with an embodiment of the invention.

[0019] FIG. 7 is a system diagram illustrating a system for determining a private key in accordance with an embodiment of the invention.

[0020] FIG. 8 is a system diagram illustrating a system for determining a public key in accordance with an embodiment of the invention.

[0021] FIG. 9 is a system diagram illustrating a system for determining a common agreed upon secret key in accordance with an embodiment of the invention.

[0022] FIG. 10 is a flow diagram illustrating a method for determining a common agreed upon secret key and transmitting a message using that secret key in accordance with an embodiment of the invention.

[0023] FIG. 11 is a system diagram illustrating a system for determining a secret key in accordance with an embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

[0024] The present invention introduces an algorithmically efficient one-way function. The algorithm is both rapidly computable and computationally hard to reverse. An overview in accordance with the invention is provided in FIG. 10. Parties Alice and Bob are each in possession of a database from which they form their respective private keys (Boxes 101 and 102). They then proceed to produce their respective public keys based on their respective private keys by applying an algorithm in accordance with the invention (Boxes 103 and 104). Alice and Bob each have access to a respective transmitter and receiver. Alice and Bob use their respective transmitter and receiver to exchange their public keys. By exchanging these public keys they are each in a position to obtain a common agreed upon secret key by letting the received public key act on the respective user's private keys (Boxes 105 and 106). Once the shared secret key has been obtained, Alice can then encrypt a plaintext message, produce an encrypted message (Box 107), send the encrypted message (Box 108) to Bob, who can then decrypt the encrypted message (Box 109) to obtain Alice's plaintext message (Box 107).

[0025] Let M, N denote monoids and let S denote a group which acts on M on the left. Given an element sS, and an element mM, we denote the result of s acting on m by .sup.sm. The semidirect product of M and S, MS is defined to be the monoid whose underlying set is MS and whose internal binary operation

.sub.M.sub.S:(MS)(MS).fwdarw.MS

is given by

.sub.M.sub.S:((m.sub.1,s.sub.1),(m.sub.2,s.sub.2)).fwdarw.(m.sub.1.Math..sup.s.sup.1m.sub.2,s.sub.1s.sub.2).

Furthermore, we let NS denote the direct product.

[0026] An algebraic eraser is specified by a 6-tuple (MS, N, II, E, A, B) where MS and N are as above, A, B are user submonoids of M, II is an easily computable monoid homomorphism

II:M.fwdarw.N,

E is a function

E:(NS)(MS).fwdarw.NS

given by

E((n,s),(m.sub.1,s.sub.1))=(nII(.sup.sm.sub.1),ss.sub.1),

and A, B are submonoids of MS such that for all (a, s.sub.a)A,(b, s.sub.b)B

E((II(a),s.sub.a),(b,s.sub.b))=E((II(b),s.sub.b),(a,s.sub.a)).

Two submonoids satisfying the above identity are termed E-Commuting.

[0027] An action of S on M does not induce an action of S on N, and given knowledge of the elements

(n,s),E((n,s),(m.sub.1,s.sub.1))NS

it is very difficult to obtain the element (m.sub.1, s.sub.1)MS. The action of the element sS has been effectively erased by the algebraic eraser. A benefit lies in the efficiency of the computation of the function II and the iterative nature of the method and apparatus for the computation of the function E.

[0028] A preferred embodiment of an apparatus to perform an algebraic key agreement protocol based on the algebraic eraser, is depicted in FIGS. 1 through 11, and begins with an apparatus to compute the function II. The II-Function module 13 is responsive to the data from the II-Function module library 11, and the input element mM from 12. The II-Function module 13 computes the element II(m)N.

[0029] In general a group S is said to act (on the left) on a monoid M provided there is a homomorphism from S to the endomorphisms of M which satisfies certain properties. Given sS and mM, the element s maps m to a new element in M, denoted .sup.sm. The required properties are

.sup.s(m.sub.1m.sub.2)=.sup.sm.sub.1.sup.sm.sub.2,.sup.1m=m,.sup.s.sup.1.sup.s.sup.2m=.sup.s.sup.1(.sup.s.sup.2m)

Referring to FIG. 2, S-Action module 23 is responsive to the inputs sS 21 and mM 22, and computes the image of m under the action of s yielding .sup.sm as output.

[0030] An apparatus to compute the function E is depicted in FIG. 3. The E-Function module 36 is responsive to the inputs (n, s) 31 and (m, s) 34. Given an ordered list, (x, y) of two elements x, y, the first component projection of (x, y) outputs the first component x on the list. Similarly, the second component projection outputs the second component y. The input (n, s), 31, is sent to the second component projection module, 32 and the input (m.sub.1, s.sub.1) is likewise sent to a first component projection module, 33. The resulting elements of S and M of the first and second component modules 32, 33 are then forwarded to the S-Action module 23, yielding the element .sup.sm.sub.1M. This resulting element .sup.sm.sub.1 is forwarded to the II-Function module, 13, which outputs the element II(.sup.sm.sub.1). The E-Function multiplier, 35, is responsive to the input (n, s), 31, the element II(.sup.sm.sub.1)N, and the result of the input (m.sub.1, s.sub.1), 34, being entered into the second component projection module, 32. The E-Function multiplier outputs the element (n II(.sup.sm.sub.1)s s.sub.1)NS which is also the output of the E-Function module 36.

[0031] The semi-direct product of M and S, denoted MS, is defined to be the monoid whose underlying set is the direct product MS and whose binary operation is given by

(m.sub.1,s.sub.1).Math.(m.sub.2,s.sub.2)=(m.sub.1.Math..sup.s.sup.1m.sub.2,s.sub.1s.sub.2).

It is noted that given, an element (n, s)NS and two elements (m.sub.1, s.sub.1), (m.sub.2, s.sub.2)MS, that

E(n,s),((m.sub.1,s.sub.1).Math.(m.sub.2,s.sub.2))=E(E((n,s),(m.sub.1,s.sub.1)),(m.sub.2,s.sub.2)).

Hence computing the E-Function iteratively increases the system's efficiency and speed.

[0032] FIG. 4 depicts an apparatus which may be used in performing the above computation. An E-Function Iterator module 42 is responsive to the input (n, s), 31, and to the input (m.sub.1, s.sub.1), (m.sub.2, s.sub.2), . . . , (m.sub.k,s.sub.k), 41, and outputs

(nII(.sup.sm.sub.1)II(.sup.ss.sup.1m.sub.2) . . . II(.sup.ss.sup.1.sup.. . . s.sup.km.sub.k),ss.sub.1 . . . s.sub.k).

[0033] A more detailed apparatus of the E-Function Iterator module 42, is depicted in FIG. 5, begins with the input (n, s) 31 being sent to the E-Function module 36. In addition, an input (m.sub.1, s.sub.1), (m.sub.2, s.sub.2), . . . , (m.sub.k, s.sub.k), 41, is sent to the choose t.sup.th component module, 53, which is a module initialized at the value t=1 and repeatedly incremented by the increment t module, 54. The t.sup.th component of the input (m.sub.1, s.sub.1), (m.sub.2, s.sub.2), . . . , (m.sub.k, s.sub.k) is precisely (m.sub.t, s.sub.t) which is the output of 53 and sent to the E-Function module 36. Furthermore the value of t is sent to the decision box 55 which also receives the value of the E-Function (iterated t1 times up to that point). The decision box 55 determines if t=k, at which point the computation stops, otherwise, the output of decision box 55 becomes input 31 to the E-Function module 36 to be used as the new first component of E together with the incoming entry from choose t.sup.th component module 53. The final value arrived at is given by

(n.Math.II(.sup.sm.sub.1)II(.sup.ss.sup.1m.sub.2) . . . II(.sup.ss.sub.1 .sup.. . . s.sup.k-1m.sub.k),ss.sub.1 . . . s.sub.k)=(n.Math.II((.sup.sm.sub.1)(.sup.ss.sup.1m.sub.2) . . . (.sup.ss.sup.1 .sup.. . . s.sup.k-1m.sub.k)),ss.sub.1 . . . s.sub.k).

[0034] Recall that two submonoids A, B are said to be E-Commuting provided

E((II(a),s.sub.a),(b,s.sub.b)=E(II(b),s.sub.b),(a,s.sub.a))

holds for all (a, s.sub.a)A, (b, s.sub.b)B. FIG. 6 illustrates an apparatus which may be used in choosing a pair of E-Commuting monoids, A, B which may be utilized in the invention. A monoid is specified by a generating set, i.e., a subset of elements of the monoid which have the property that every element of the monoid can be expressed as a product of some of these generators (in some order, with repetitions allowed). The Semidirect Product Producer 60 is responsive to the monoid M and the group S and produces the monoid MS. The monoid MS, together with the monoid N and the function n are sent to the E-Commuting Monoid Producer 63, whose output is sent to the Pairs of E-Commuting Monoid Library 64. A Pseudorandom Number Generator 61 produces a random number , a Chooser 62 then accesses the .sup.th element of the Pairs of E-Commuting Monoid Library 63 and outputs the pair of E-Commuting monoids A.sub.1, B.sub.1 which are forwarded to Alice and Bob, respectively. Additionally the pair A.sub.1, B.sub.1 is forwarded to the User Submonoid Generator Database 65.

[0035] With the apparatuses for computing the S-Action, the functions H and E specified, and each users submonoid in place, the algebraic eraser key agreement protocol can now be detailed. If the E-commuting monoids A.sub.1, B.sub.1, are privately assigned to Alice and Bob, then the invention functions, for example, as a symmetric cryptosystem. If the monoid MS possesses a large library of pairs of E-Commuting submonoids which are recursively enumerable and whose internal algebraic structure is hidden then the invention can function, for example, as an asymmetric cryptosystem.

[0036] FIG. 7 illustrates a mechanism which may be used hi enabling a user to generate a private key. Focusing on Alice (Bob case is analogous) a second Pseudorandom. Number Generator 72 responsive to the input *, 71, creates a list of integers e.sub.1, e.sub.2, . . . , e.sub.* where each e.sub.i is generated in such a way that e.sub.inumber of generators of (A.sub.1). The Sequence Encoder 73 is responsive to the list e.sub.1, e.sub.2, . . . , e.sub.* and the User Submonoid Generator database 65, is responsive to the submonoid A.sub.1. The Sequence Encoder 73 produces the list of the user generators (m.sub.e.sub.1, s.sub.e.sub.1), (m.sub.e.sub.2, s.sub.e.sub.2), . . . , (m.sub.e.sub.*, s.sub.e.sub.*) out of the generating set of A.sub.1. The Private Key Generator 74 is responsive to Encoder 73 and produces the user private key

M.sub.A=(m.sub.e.sub.1s.sub.e.sub.1),(m.sub.e.sub.2,s.sub.e.sub.2), . . . ,(m.sub.e.sub.*,s.sub.e.sub.*)

which is sent to a memory 75. It should be observed that the product of the elements, denoted (M.sub.A, S.sub.A),

[00001]$\left(M_A,s_A\right)=\left(m_{{e.Math.}_1},s_{{e.Math.}_1}\right).Math.\left(m_{{e.Math.}_2},s_{{e.Math.}_2}\right).Math..Math.\mathrm{.Math.}.Math..Math.\left(m_{e_{}*},s_{e_{}*}\right)=\left(\left(m_{{e.Math.}_1}\right).Math.{(}^{s_1}.Math.m_{e_2}).Math..Math.\mathrm{.Math.}.Math..Math.{(}^{s_1.Math.\mathrm{.Math.}.Math..Math.s_{}.Math.{*}_{-1}}.Math.m_{e_{}*}),s_{e_1.Math.}.Math.\mathrm{.Math.}.Math..Math.s_{e_{}*}\right)$

is an element of the submonoid A.sub.1.Math.MS, but need not be computed explicitly for key agreement.

[0037] Now that Alice and Bob have chosen their respective user private keys, FIG. 8 depicts the apparatus which may be used in computing the user public keys. The E-Function Iterator module 42 is responsive to the input (m.sub.e.sub.1, s.sub.e.sub.1), (m.sub.e.sub.2, s.sub.e.sub.2)), . . . , (m.sub.e.sub.*, s.sub.e.sub.*), 81 and the element

(1.sub.N,1.sub.S)=(identity.sub.N,identity.sub.S)NS,

which is the identity of the monoid N in the first component and the identity of S in the second component. The E-Function iterator module 42 produces the User Public Key

[00002]$\left(N_A,s_A\right)=E\left(\left(1_N,1_S\right),\left(M_A,s_A\right)\right)=(\left(\left(m_{{e.Math.}_1}\right).Math..Math.{(}^{s_1}.Math.m_{e_2}).Math..Math.\mathrm{.Math.}.Math..Math..Math.{(}^{s_1.Math.\mathrm{.Math.}.Math..Math.s_{}.Math.{*}_{-1}}.Math.m_{e_{}*}),s_{e_1.Math.}.Math.\mathrm{.Math.}.Math..Math.s_{e_{}*}\right)=\left(\left(\left(m_{{e.Math.}_1}\right).Math.{(}^{s_1}.Math.m_{e_2}).Math..Math.\mathrm{.Math.}.Math..Math.{(}^{s_1.Math.\mathrm{.Math.}.Math..Math.s_{}.Math.{*}_{-1}}.Math.m_{e_{}*})\right),s_{e_1.Math.}.Math.\mathrm{.Math.}.Math..Math.s_{e_{}*}\right)=\left(\left(M_A\right),s_A\right),$

which is sent to memory 83.

[0038] At this point Alice has the public key (N.sub.A, s.sub.A) and private key (M.sub.A), Bob has public key (N.sub.B, s.sub.B) and private key (M.sub.B), and they are now in a position to utilize the apparatus depicted in FIG. 9 to obtain a common agreed upon secret key. Alice transmits her public key (N.sub.A, s.sub.A) input 91 via the transmitter/receiver 93, and likewise Bob transmits his public key (N.sub.B, s.sub.B) input 92 via the transmitter/receiver 94. The received public keys together with the each users private keys are then forwarded to the respective E-Function Iterator modules 42a, 42b, to yield

(N.sub.BII(.sup.s.sup.BM.sub.A),s.sub.Bs.sub.A)=E((N.sub.B,s.sub.B),(M.sub.A,s.sub.A))=E((II(M.sub.B),s.sub.B),(M.sub.A,s.sub.A))

(N.sub.AII(.sup.s.sup.AM.sub.B),s.sub.As.sub.B)=E((N.sub.A,s.sub.A),(M.sub.B,s.sub.B))=E((II(M.sub.A),s.sub.A),(M.sub.B,s.sub.B)).

Since (M.sub.A, s.sub.A) and (M.sub.B, s.sub.B) are contained in the submonoids A.sub.1, B.sub.1 respectively, the original assumptions regarding the structure of the algebraic eraser imply that the above elements of NS are equal and can serve as the common agreed upon secret key, 97.

[0039] The above key agreement protocol can be enhanced by combining it with the Diffie-Hellman protocol described in the prior art. One such combination is given as follows. Referring to FIG. 8, replace input 82 by the element (K.sub.A, identity.sub.S) (for Alice) and (K.sub.B, identity.sub.S) (for Bob) where K.sub.A, K.sub.BN axe additional private keys chosen so that they commute. The public keys for Alice and Bob are, E((K.sub.A, identity.sub.S), (M.sub.A, s.sub.A)), E((K.sub.B, identity.sub.S), (M.sub.B, s.sub.B)), respectively. In this variation of the key agreement protocol, the common agreed upon secret key is given by

E((K.sub.AK.sub.B.Math.(M.sub.B),s.sub.B),(M.sub.A,s.sub.A))=E((K.sub.BK.sub.A.Math.II(M.sub.A),s.sub.A),(M.sub.B,s.sub.b)).

[0040] Referring now to FIG. 11, there is shown a system 1130 which could be used in accordance with an embodiment of the invention. System 1130 includes a first transmitter/receiver 1102a and a second transmitter/receiver 1102b. Transmitters/receivers 1102a and 1102b could be, for example, readers and tags in an RF-ID system. Transmitters/receivers 1102 and 1102b may, for example, generate information, receive information, or modulate received information to transmit other information.

[0041] Transmitter/receiver 1102a includes a memory 1104a, a processor 1110a, an action module 1112a, a II-Function module 1103a an E-function multiplier 1106a and an antenna 1114a. Similarly, transmitter/receiver 1102b includes a memory 1104b, a processor 1110b, an action module 1112b, a II-Function module 1108b, an E-function multiplier 1106b and an antenna 1114b. Action modules 1112a and 1112b could be, for example, S-action module 23 discussed above. II-Function modules 1108a and 1108b could be, for example, II-Function module 13 discussed above. E-Function multipliers 1106a and 1106b could be E-Function multipliers 35 as described above.

[0042] Memories 1104a and 1104b each include monoids N and M, group S and function II which all could be determined using, for example, the algorithms discussed above. Memory 1104a further includes a submonoid A and memory 1104b further includes a submonoid B. Submonoids A and B may be determined as discussed above. For example, a semi-direct product of S and M may be determined. A and B may then be E-commuting submonoids of this semi-direct product. Monoids M and N, group S, function n and submonoids A and B may all be determined by a communications center 1132 in communication with a database 1134. Communications center 1132 may forward monoids M and N, group S, function II and submonoids A and B to transmitter/receivers 1102a, 1102b using, for example an antenna 1136. Alternatively, monoids M and N, group S, function II and submonoids A and B, may be stored in memories 1104a, 1104 of transmitter/receives 1102a, 1102b respectively, when the respective devices are manufactured.

[0043] In operation, processors 1110a and 1110b each select generators of monoids A and B, respectively. The selection could be, for example, through the use a pseudo-random number generators 1120a, 1120b. Processor 1110a then orders the generators to produce a private key 1118a for transmitter/receiver 1102a.

[0044] Processor 1110a then forwards private key 1118a and an identity element 1122a to action module 1112a, II Function module 1108a and E-Function multiplier 1106a to produce a public key 1122a for transmitter/receiver 1102a. Identity element 1122a includes a first component which is the identity of monoid N and a second component which is the identity of group S. The process through action module 1112a, II-Function module 1108a and E-Function multiplier 1106a may be performed iteratively for each generator in private key 1118a.

[0045] Similarly, processor 1110b orders generators of monoid B to produce a private key 1118b for transmitter/receiver 1102b. Processor 1110b then forwards private key 1118b and an identity element 1122b to action module 1112b, II-Function module 1108b and E-Function multiplier 1106b to produce a public key 1122b for transmitter/receiver 1102b. Identity element 1122b includes a first component which is the identity monoid N and a second component which is the identity of group S. The process through action module 1112b, II-Function module 1108b and E-Function multiplier 1106b may be performed iteratively for each generator in private key 1118b.

[0046] Transmitter/receivers 1102a and 1102b exchange their respective public keys 1122a, 1122b using antennas 1114a and 1114b respectively over a communication link 1128. Once the public keys 1122a, 1122b are received, a secret key may be ascertained. Focusing on transmitter/receiver 1102a, for example, public key 1122b from transmitter/receiver 1102b is input to action module 1112a, II-function module 1108a and E-Function multiplier 1100a along with private key 1118a. Action module 1112a, II-Function module 1108a, and E-Function multiplier 1106a may operate on these inputs iteratively for each generator in the Ovate key from transmitter/receiver 1102a, to produce a secret key 1124. A similar operation is performed at transmitter/receiver 1102b. The secret key 1124 may be then be used by transmitter/receivers 1102a and 1102b to communicate securely.

[0047] While the invention has been described and illustrated in connection with preferred embodiments, many variations and modifications as will be evident to those skilled in this art may be made without departing from the spirit and scope of the invention, and the invention is thus not to be limited to the precise details of methodology or construction set forth above as such variations and modification are intended to be included within the scope of the invention.

EXAMPLE

[0048] An instance of the algebraic eraser and its associated key agreement protocol can be obtained in the case where the monoid M is chosen to be the set of LL matrices whose entries are rational functions with integral coefficients in the variables {t.sub.1, t.sub.2, . . . , t.sub.}, i.e., the entries take the form

[00003]$\frac{C_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}{D_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}$

where 1i, j, and C.sub.ij, D.sub.ij are polynomials. The group S is chosen to be the symmetric group on symbols, denoted S.sub., The action of the elements of sS.sub., on the set of variable {t.sub.1, t.sub.2, . . . , t.sub.}, given by

s:t.sub.it.sub.s(i),

can be extended to an action of the monoid M in a natural manner. Given element of M, input 22, (see FIG. 2) of the form

[00004]${\left[\frac{C_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}{D_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}\right]}_{1i,j}$

and an element sS.sub., input 21, the result of the S.sub.-Action module 23 is the element of M given by

[00005]${s.Math.\left[\frac{C_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}{D_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}\right]}_{1i,j}={\left[\frac{C_{\mathrm{ij}}\left(t_{s\left(1\right)},t_{s\left(2\right)},\mathrm{.Math.}.Math.,t_{s\left(\right)}\right)}{D_{\mathrm{ij}}\left(t_{s\left(1\right)},t_{s\left(2\right)},\mathrm{.Math.}.Math.,t_{s\left(\right)}\right)}\right]}_{1i,j}.$

[0049] Having specified the monoid M and the action of a group S on M, we fix a prime p and let the monoid N be the set of LL matrices whose entries are integers mod p. Then to define the homomorphism II a set of integers (.sub.1, .sub.2, . . . , .sub.n) (mod p), is chosen and is stored in the II-Function module Library 11. Given an element of M, Input 12, the II-Function module produces the element of N given by

[00006]${\left[\frac{C_{\mathrm{ij}}\left({}_1,{}_2,\mathrm{.Math.}.Math.,{}_{}\right).Math..Math.\mathrm{mod}.Math..Math.p}{D_{\mathrm{ij}}\left({}_1,{}_2,\mathrm{.Math.}.Math.,{}_{}\right).Math..Math.\mathrm{mod}.Math..Math.p}\right]}_{1i,j}.$

It is tacitly assumed that

D.sub.ij(.sub.1,.sub.2, . . . ,.sub.)0(mod p),

which can always be arranged by appropriate selection of (.sub.1, .sub.2, . . . , .sub.) for the situation at hand.

[0050] With the above choices in place the E-Function 13 takes the form,

[00007]$E\left(\left(\left[d_{\mathrm{ij}}\right],s\right),\left(\left[\frac{C_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}{D_{\mathrm{ij}}\left(t_1,t_2,\mathrm{.Math.}.Math.,t_{}\right)}\right],s_1\right)\right)=\left(\left[d_{\mathrm{ij}}\right].Math.\left[\frac{C_{\mathrm{ij}}\left({}_{s\left(1\right)},{}_{s\left(2\right)},\mathrm{.Math.}.Math.,{}_{s\left(\right)}\right).Math..Math.\mathrm{mod}.Math..Math.p}{D_{\mathrm{ij}}\left({}_{s\left(1\right)},{}_{s\left(2\right)},\mathrm{.Math.}.Math.,{}_{s\left(\right)}\right).Math..Math.\mathrm{mod}.Math..Math.p}\right],s.Math..Math.{\mathrm{.Math.}}_{.Math.1}\right).$

The E-Function Iterator module 42 may be evaluated via the apparatus in FIG. 5.

[0051] A method for creating the library of pairs of E-Commuting monoids will now be specified. Each monoid in such a pair will be presented as a list of generators each of which is contained in MS. A feature of the method is that the internal algebraic structure of the pairs of E-Commuting monoids is difficult to determine from the publicly announced list of generators. Choose two sets X, Y of elements of M, and two sets U, V of elements of S.sub., where the following properties hold:

xy=yx

uv=vu

.sup.vx=x

.sup.uy=y

for all xX, yY and uU, vV. There are many such choices for the sets X, Y, U, V. In fact, the number of choices also grows exponentially with L.

[0052] One method to specifically choose the sets X, Y, U, V is given as follows. Partition the set {t.sub.1, t.sub.2, . . . , t.sub.} into two disjoint subsets T.sub.1, T.sub.2 where T.sub.i={t.sub.i.sub.1, t.sub.i.sub.2, . . . , t.sub.i.sub.} for i=1,2. Correspondingly, there will exist two distinct subgroups U, V of S.sub., where an element of U permutes the variables in T.sub.1 and fixes the variables in T.sub.2, and similarly an element of V permutes the variables in T.sub.2 and fixes the variables in T.sub.1. Observe that every element uU commutes with every element vV. Next choose positive integers l.sub.1 and l.sub.2 such that L=l.sub.1+l.sub.2+1. The matrices in X are chosen to be of the form

[00008]$\left(\begin{array}{ccccccc}& & & 0& & & \\ {}_{}& {l_1}_{}.Math.& & \mathrm{.Math.}& & & \\ & & & 0& & & \\ 0& \mathrm{.Math.}& 0& 1& 0& \mathrm{.Math.}& 0\\ & & & 0& 1& & \\ & & & \mathrm{.Math.}& & & \\ & & & 0& & & 1\end{array}\right)$

where .sub.l.sub.1 is an l.sub.1l.sub.1 matrix whose entries are rational functions in the variables T.sub.1. All nonspecified entries the above matrix are equal to 0. Similarly, the matrices in Y are chosen to be of the form

[00009]$\left(\begin{array}{ccccccc}1.Math.& & & 0& & & \\ & .Math.& & \mathrm{.Math.}& & & \\ & & 1.Math.& 0& & & \\ 0& \mathrm{.Math.}& 0& 1& 0& \mathrm{.Math.}& 0\\ & & & 0& & & \\ & & & \mathrm{.Math.}& & {l_2}_{}& \\ & & & 0& & & \end{array}\right)$

where .sub.l.sub.2 is an l.sub.2l.sub.2 matrix whose entries are rational functions in the variables T.sub.2. It is clear that the above choices of matrices commute, and that an element uU acts trivially on each matrix in Y, and an element vV acts trivially on each matrix in X.

[0053] With this done choose an invertible element (z, w)MS. There are many such choices for (z, w), and in fact, the number of such choices grows exponentially with L. One can now define the submonoids as

A={(z,w).Math.(x,u).Math.(z,w).sup.1|xX,uU},

B={(z,w).Math.(y,v).Math.(z,w).sup.1|yY,vV}.

It is readily verifiable that A, B are E-Commuting monoids. Note that the search for (z, w) is more difficult than a standard conjugacy search problem because the conjugated elements are unknown.

[0054] In the key agreement protocol, there are two users, Alice and Bob, each of whom has a public and a private key. The users proceed with a public exchange, after which each is in a position to obtain common agreed upon secret key which can then be used for further cryptographic applications. The key agreement protocol begins in this example with each user, Alice and Bob, being assigned a user submonoid A.sub.1, and B.sub.1, respectively, from a pair in the E-Commuting Monoid Library, 63. Each user, Alice and Bob, proceeds to choose a private key which is the output of a respective Private Key Generator 74. Each user public key is then computed by directing the user private key, input 81 to the E-Function Iterator module 42, along with the input 82. The E-Function Iterator module 42 allows the users to compute their respective public keys in a novel and rapid fashion. The computations involved are 8-bit modular arithmetic operations (addition, subtraction, multiplication, and division) and 8-bit string search and replacement. These computations can be achieved at low cost and high efficiency.

[0055] Finally, the public keys are exchanged via the transmitter/receivers 93, 94. The results of this exchange, along with the users private keys, are sent to the E-Function Iterator module 42a, 42h, which outputs the common agreed upon secret key 97.