Geometry-Based Symmetric Cryptosystem Method

• US 20040105546A1
• Filed: 11/06/2003
• Published: 06/03/2004
• Est. Priority Date: 11/19/2002
• Status: Abandoned Application

• Current Assignee: Arkady Berenstein, Leon Chernyak
• Original Assignee: Arkady Berenstein, Leon Chernyak
• Inventors: Chernyak, Leon, Berenstein, Arkady
• Application Number:
  US10/605,935
• Publication Number:
  US 20040105546A1
• Time in Patent Office: Days
• US Class Current: 380/259
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

A method of communicating information between users of a communication system includes the following steps of: generating a module V over a ring R; generating an outer component P of encryption key that includes sequence (p₁, p₂, . . . , p_k) where each member p_j of the sequence belongs to the set {1, 2, . . . , m} (the length k of the sequence is arbitrary and thus repetitions are allowed in the sequence); generating an inner component Q of encryption key that includes elements v_1,v₂, . . . , V_m of V and automorphisms g₁, g₂, . . . , g_m of V; generating the encryption key K=(P; Q), where P is the outer component and Q is the inner component; generating an encryption automorphism T_e of V based on the encryption key K, where T_e includes a composition of certain automorphisms T₁, T₂, . . . , T_m of the module V which composition is performed in the order prescribed by P; generating an encrypted message element E as a function of a message element M in V and of the encryption automorphism T_e; transmitting the encrypted message element E along with the outer component P from one user to another; generating the outer component P′ of the decryption key that includes sequence (p_k, p_k−1, . . . , p₁), i.e., the sequence reversed of that involved in producing the outer component P of the encryption key; generating the decryption key K′=(P′; Q′), where P′ is the outer component of the decryption key and Q′ is the inner component of the decryption key which is equal to the inner component Q of the encryption key; generating a decryption automorphism T_d of V based on the decryption key K′, where T_d includes a composition of the automorphisms T₁, T₂, . . . , T_m, which composition is performed in the order prescribed by P′, e.g., T_d is the inverse automorphism of T_e; determining the message element M as a function of the encrypted message element E and of the decryption automorphism T_d, where the function is the same as that one used in generation of E (that is, the decryption method is symmetric to encryption: the decryption proceeds as the encryption, but with replacement of the outer component P with the outer component P′).

Claims

1. A method of communicating information between users of a communication system includes the following steps of:

generating a module V over a ring R;

generating an outer component P of encryption key that includes sequence (p₁, p₂, . . . , p_k) where each member p_j of the sequence belongs to the set {1, 2, . . . , m} (the length k of the sequence is arbitrary and thus repetitions are allowed in the sequence);

generating an inner component Q of encryption key that includes elements v₁, v₂, . . . , v_m of V and automorphisms g₁, g₂, . . . , g_m of V;

generating the encryption key K=(P;

Q), where P is the outer component and Q is the inner component;

generating an encryption automorphism T_e of V based on the encryption key K, where T_e includes a composition of certain automorphisms T₁, T₂, . . . , T_m of the module V, which composition is performed in the order prescribed by P;

generating an encrypted message element E as a function of a message element M in V and of the encryption automorphism T_e;

transmitting the encrypted message element E along with the outer component P from one user to another;

generating the outer component P′

of decryption key that includes sequence (p_k, p<sub>k−

1</sub>, . . . , p₁), i.e., the sequence that is reversed of that involved in producing the outer component P of the encryption key;

generating the decryption key K′

=(P′

;

Q′

), where P′

is the outer component of the decryption key and Q′

is the inner component of the decryption key which is equal to the inner component Q of the encryption key;

generating a decryption automorphism T_d of V based on the decryption key K′

, where T_d includes a composition of the automorphisms T₁, T₂, . . . , T_m, which composition is performed in the order prescribed by P′

, e.g., T_d is the inverse automorphism of T_e;

determining the message element M as a function of the encrypted message element E and of the decryption automorphism T_d, where the function is the same as that one used in generation of E (that is, the decryption method is symmetric to encryption;

the decryption proceeds as the encryption, but with replacement of the outer component P with the outer component P′

).

2. The method as defined by claim 1, wherein the ring R is any commutative or non-commutative ring.

3. The method as defined by claim 1, wherein said V is a projective module over the ring R.

4. The method as defined by claim 1, wherein said V is a free R-module of dimension n, and where n is an integer greater than 1.

5. The method as defined by claim 4, wherein the R-module V is the standard free module Rⁿ, that is, V is the set of all n-tuples x=[x₁, x₂, . . . , x_n] of elements of R.

6. The method as defined by claim 2, wherein said ring R is the field of real numbers.

7. The method as defined by claim 2, wherein said ring R is the skew-field of quaternions.

8. The method as defined by claim 2, wherein said ring R is a finite field.

9. The method as defined by claim 2, wherein the ring R is the ring of matrices over the field of real numbers.

10. The method as defined by claim 1, wherein said step of generating said automorphisms T₁, T₂, . . . , T_m further comprises generating automorphisms T₁, T₂, . . . , T_m of finite orders.

11. The method as defined by claim 10 further comprises generation of each automorphism T_i of the order 2.

12. The method as defined by claim 10, wherein said index i is used in the derivation of said outer component of the encryption or decryption keys and said element T_i is a part of said encryption and decryption automorphisms.

13. The method as defined by claim 1, wherein said message element M is an element of said module V.

14. The method as defined by claim 13, wherein the encrypted message element E is obtained by applying said automorphism T_e (as defined in the claim 1) to the message element M.

15. The method as defined by claim 1, wherein said encrypted message element is produced by a user at one location, transmitted from said one location to another location, and decrypted by a user at said another location.

40. The method as defined by claim 6, wherein each said real number is represented as decimal number with a prescribed number of decimal places after the dot.

41. The method as defined by claim 40, wherein each said number is an integer.

16. A method of communicating information between users of a communication system, the method comprising the steps of:

generating a module V over a ring R;

generating an outer component P of encryption key;

P=(p₁, p₂, . . . , p_k) where each member p_j of the sequence belongs to the set {1, 2, . . . , m};

generating an inner component Q of encryption key that includes elements v₁, v_2, . . . _, v_m of said module V and automorphisms g₁, g₂, . . . , g_m of V;

generating the encryption key K=(P;

Q), where P is the outer component and Q is the inner component;

generating an encryption automorphism T_e of the module V based on automorphisms T₁, T₂, . . . , T_m of the module V and on the outer component P=(p₁, p₂, . . . , p_k) of encryption key;

T_e=T_p1°

T_p2°

. . . T_pk. That is, T_e is an automorphism of the module V obtained as a composition of automorphisms T₁, T₂, . . . , T_m, which composition is performed in the order prescribed by P;

generating an encrypted message element E as a function of a message element M in V and of the encryption automorphism T_e;

transmitting the encrypted message element E along with the outer component P from one user to another;

generating an outer component P′

=(p_k, p<sub>k−

1</sub>, . . . p₁), i.e., the sequence that is reversed of that involved in producing the outer component P of the encryption key;

generating the decryption key K′

=(P′

;

Q′

), where P′

is the outer component of the decryption key and Q′

is the inner component of the decryption key which is equal to the inner component Q of the encryption key;

generating a decryption automorphism T_d of the module V based on automorphisms T₁, T₂, . . . , T_m of the module V and on the outer component P′

=(p_k, p<sub>k−

1</sub>, . . . p₁) of the decryption key;

T_e=T_pk°

. . . T_p2°

Tp1, where T₁, T₂, . . . , T_m are the same automorphisms of V which have been used in the construction of the encryption automorphism T_e;

determining the message element M as a function of the encrypted message element E and of the decryption automorphism T_d, where the function is the same as that one used in generation of E (that is, the decryption method is symmetric to encryption;

the decryption proceeds as the encryption, but with replacement of the outer component P with the outer component P′

).

17. The method as defined by claim 16, wherein said encrypted message element M is produced as

E=T_e(M),

where T_e(M) is the element of V obtained by applying the automorphism T_e to said message element M.

18. The method as defined by claim 16, wherein said decrypted message element M is produced as

M=T_d(E),

where T_d(E) is the element of V obtained by applying the automorphism Td to said encrypted message element E.

19. The method as defined by claim 16, of further selecting non-zero elements v₁, v₂, . . . , v_m of the module V.

20. The method as defined by claim 16, of construction of R-linear maps / p:

V # R, for p=1, 2, . . . , m, such that / _p(v_p)=2.

21. The method as defined by claim 16, wherein said step of generating said automorphisms T₁, T₂, . . . , T_m of V includes selecting automorphisms g₁, g₂, . . . , g_m of V and reflections S₁, S₂, . . . S_m of V.

22. The method as defined by claim 21, wherein said elements T₁, T₂, . . . , T_m are defined by:

T_p=g_p°

S_p°

h_p,

where h_p is the inverse automorphism of g_p, that is,

g_p°

h_p=h_p°

g_p=the identity automorphism of V,

and S_p is the reflection of V relative to the element v_p, as defined in claim 19, and an R-linear map / _p;

V # R as defined in claim 20. That is, S_p is defined by;

S_p(x)=x−

/ _p(x)#v_p

for any x in V.

23. The method as defined by claim 21 where each g_i is a polynomial automorphism of the module V. By definition, a map g:

U#V from a R-module U to R-module V is called polynomial map if for any elements u₁, u₂, . . . , u_r of U there is a finite family of elements v_J labeled by finite sequences J=(j₁, j₂, . . . ) of indices each of which belongs to the set {1, 2, . . . , r} such that for any elements a₁, a₂, . . . , a_r of R one has;

g(a₁#u₁+a₂#u₂+ . . . +a_r#u_r)=#(^aj_i#^aj₂###^aj_r)#v_J,

where summation is over all J=(j₁, j₂, . . . ) as above. A map g;

V # V is a polynomial automorphism if g is invertible and both g and inverse of g are polynomial maps.

24. The method as defined by claim 21 where each g_i is a rational automorphism of the module V. By definition, a partially defined map g:

U # V from a R-module U to R-module V is called rational if there exists a polynomial map f;

U # R and a polynomial map h;

U # V such that h(u)=f(u)#g(u) for all u in the domain of g.

25. The method as defined by claims 5 and 23 of constructing polynomial automorphisms g_i of the free module V=Rⁿ, where each g_i belongs to that group of polynomial automorphisms of V which is generated by all R-linear invertible maps V # V and by all the polynomial automorphisms g:

V# V of the form;

g(x₁, x₂, . . . , x_n)=(x₁, x₂+f₁(x₁), x₃+f₂(x₁, x₂), . . . , x_n+f<sub>n−

1</sub>(x₁, x₂, . . . x<sub>n−

1</sub>)),

where f_i;

Rⁱ # R for i=1, 2, . . . , n−

1 are polynomial maps.

26. The method as defined by claims 5 and 24 of constructing rational automorphisms g_i of the free module V=Rⁿ, where each g_i belongs to that group of rational automorphisms of V which is generated by all R-linear invertible maps V # V and by all the rational automorphisms g:

V# V of the form;

g(x₁, x₂, . . . , x_n)=(x₁, x₂+f₁(x₁), x₃+f₂(x₁, x₂), . . . , x_n+f<sub>n−

1</sub>(x₁, x2, . . . , x<sub>n−

1</sub>)),

where f_i;

Rⁱ# R for i=1, 2, . . . , n−

1 are rational maps.

27. The method for construction of rational automorphisms f_i:

Rⁱ # R, as of claim 26, where the domain of each f_i is the entire Rⁱ, where R is the field of real numbers as in claim 6.

28. The method of claim 27, where each f_i is of the form:

f_i(x₁, x₂, . . . , x_i)=P_i(x₁, x₂, . . . , x_i)/Q_i(x₁, x₂, . . . , x_i),

where P_i (x₁, x₂, . . . , x_i) and Q_i (x₁, x₂, . . . , x_i) are polynomials with real coefficients in the variables x₁, x₂, . . . , x_i such that Q_i(x₁, x₂, . . . , x_n)>

0 for any real numbers x₁, x₂, . . . , x_n.

29. The method as defined by claim 22, of further construction of the R-linear map / _p:

V # R by means of a map L;

V×

V # R, which is left R-linear, that is,

L(a#x+b#y, v)=a#L(x,v)+b#L(y,v)

for any elements x, y, and v of V, and any elements a and b of R, where ‘

#’

stands for the action of the ring R on the module V.

30. The method of selecting elements v₁, v₂, . . . , v_m of the claim 19 that provides that L(v_p, v_p) # 0 for each p=1, 2, . . . , m.

31. The method as defined by claim 29, of further selecting elements v₁, v₂, . . . , v_m satisfying the property that for each p=1, 2, . . . , m there exists an element r_p in R such that L(v_p, v_p)#r_p=2.

32. The method of claims 20, 29, and 31 for construction of a R-linear map / _p:

V # R by

/ _p(x)=L(x,v_p)#r_p

for all x in V, p=1, 2, . . . , m.

33. The method of claims 6, 20, 30, and 32 for construction of a R-linear map / _p:

V # R by

/ _p(x)=2L(x,v_p)/L(v_p,v_p)

for all x in V, p=1, 2, . . . , m.

34. The method of claims 6, 20, 22, 30, and 32 for construction of a reflection S_p:

V # V by

S_p(x)=x−

2L(x,v_p)/L(v_p,v_p)#v_p

for all x in V, p=1, 2, . . . , m.

35. The method as defined by claims 5 and 29, wherein the left R-linear map L is a bi-linear form on V=Rⁿ, i.e.,

L(x,y)=x₁#f₁(y₁)+x₂#f₂(y₂)+ . . . +x_n#f_n(y_n)

where each f_i:

R # R for i=1, 2, . . . , n is a polynomial.

36. The method as defined by claims 5 and 29, wherein the left R-linear map L on V=Rⁿ is further defined by:

L(x,y)=#x_i#/ _i,j#y_j

for any x, y # Rⁿ, where the summation is over all pairs (i,j) such that 1#i,j#n, and / _i,j in R for i=1, 2, . . . , n and j=1, 2, . . . , n.

37. The method as defined by claim 36, wherein the left R-linear map L is the standard bilinear form on V=Rⁿ further defined by:

L(x,y)=x₁#y₁+x₂#y₂+ . . . +x_n#y_n.

38. The method as defined by claim 36, wherein the left R-linear map L is defined by:

L(x,y)=x₁#(y₁)³+x₂#(y₂)³+ . . . +x_n#(y_n)³.

39. The method as defined by claim 16, wherein said encrypted message element E is produced by a user at one location, transmitted from said one location to another location, and decrypted by a user at said another location.

42. A method of communicating information between users of a communication system, the method comprising the steps of:

means for generating a module V over a ring R;

means for generating an outer component P of encryption key that includes sequence (p₁, p₂, . . . , p_k) where each member p_j of the sequence belongs to the set {1, 2, . . . , m};

means for generating an inner component Q of encryption key that includes elements v_1, v_2, . . . _, v_m of V and automorphisms g_1, g_2, . . . _, g_m of V;

means for generating the encryption key K=(P;

Q), where P is the outer component and Q is the inner component;

means for generating an encryption automorphism T_e of V based on the encryption key K, where T_e includes a composition of certain automorphisms T₁, T₂, . . . , T_m of the module V which composition is performed in the order prescribed by P;

means for generating an encrypted message element E as a function of a message element M in V and of the encryption automorphism T_e;

means for transmitting the encrypted message element E along with the outer component P from one user to another;

means for generating the outer component P′

of the decryption key that includes sequence (p_k, p<sub>k−

1</sub>, . . . p₁), i.e., the sequence that is reversed of that involved in producing the outer component P of the encryption key;

means for generating the decryption key K′

=(P′

;

Q′

), where P′

is the outer component of the decryption key and Q′

is the inner component of the decryption key which is equal to the inner component Q of the encryption key;

means for generating a decryption automorphism T_d of V based on the decryption key K′

, where T_d includes a composition of the automorphisms T₁, T₂, . . . , T_m, which composition is performed in the order prescribed by P′

, e.g., T_d is the inverse automorphism of T_e;

means for determining the message element M as a function of the encrypted message element E and of the decryption automorphism T_d, where the function is the same as that one used in generation of E (that is, the decryption method is symmetric to encryption;

the decryption proceeds as the encryption, but with replacement of the outer component P with the outer component P′

).

43. The system as defined by claim 42, wherein said encrypted message element is produced by a user at one location, transmitted from said one location to another location, and decrypted by a user at said another location.