Method and apparatus for geometric key establishment protocols based on topological groups

• US 20060002562A1
• Filed: 02/16/2004
• Published: 01/05/2006
• Est. Priority Date: 06/02/2003
• Status: Abandoned Application

• Current Assignee: Arkady Berenstein, Leon Chernyak
• Original Assignee: Arkady Berenstein, Leon Chernyak
• Inventors: Chernyak, Leon, Berenstein, Arkady
• Application Number:
  US10/708,197
• Publication Number:
  US 20060002562A1
• Time in Patent Office: Days
• US Class Current: 380/278
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates

Abstract

The present invention proposes a continuous multi-parameter version of Diffie-Hellman protocol based on topological groups. In its turn, based on this continuous protocol, a method for public establishment and distribution of keys for encryption systems is implemented. An embodiment of the method, while providing an extremely high security level, is several orders of magnitude faster than the existing key establishment systems.

Claims

1. A method of secure distribution of encryption/decryption keys among two communicating parties comprising of:

public (non-secret) selecting a natural number n;

public (non-secret) selecting a natural number k;

public (non-secret) selecting a k-tuple S=(S₁, S₂, . . . , S_k) of pairwise-commuting n×

n matrices with integer coefficients;

private (non-public) generating the polynomial p(x₁, x₂, . . . , x_k) in k variables x₁, x₂, . . . , x_k and with integer coefficients by the first communicating party;

private (non-public) generating the polynomial q(x₁, x₂, . . . , x_k) in k variables x₁, x₂, . . . , k_k and with integer coefficients by the second communicating party;

private (non-public) generating n×

n matrix A with integer coefficients by the first communicating party according to the formula;

A=p(S₁, S₂, . . . , S_k);

private (non-public) generating n×

n matrix B with integer coefficients by the second communicating party;

B=q(S₁S₂, . . . , S_k),

(therefore, A·

B=B·

A);

public (non-secret) selecting a compact topological monoid G by both communicating parties;

public (non-secret) selecting an n-tuple g=(g₁, g₂, . . . , g_n) of pairwise commuting elements in G by both communicating parties;

generating the n-tuple g^A by the first communicating party by the formula;

g^A=(y₁, y₂, . . . , y_n),

where

y_j=g₁^A1,j·

g₂^A2,j·

. . . ·

g_n^An,j

for j=1, 2, . . . , n, where each A_ij is a corresponding matrix coefficient of the matrix A;

generating the n-tuple g^B by the second communicating party by the formula;

g^B=(z₁, z₂, . . . , z_n),
where
z_j=g₁^B1,j·

g₂^B2,j·

. . . ·

g_n^Bn,j

for j=1, 2, . . . , n, where each B_ij is a corresponding matrix coefficient of the matrix B;

public (non-secret) transmitting the n-tuple g^A from the first communicating party to the second communicating party;

public (non-secret) transmitting the n-tuple g^B from the second communicating party to the first communicating party;

creating the shared secrete key g<sup>A·

B</sup> by the communicating parties;

generating the n-tuple (g^A)^B by the second communicating party and generating the n-tuple (g^B)^A by the first communicating party (since (g^A)^B=g<sup>A·

B</sup>=g<sup>B·

A</sup>=(g^B)^A, both communicating parties possess this n-tuple g<sup>A·

B</sup>).

2. The method as defined by claim 1, wherein G is an arbitrary compact topological monoid and the polynomials p(x₁, x₂, . . . x_k) and q(x₁, x₂, . . . , x_k) have non-negative integer coefficients, and all the matrices S₁, S₂, . . . , S_k have non-negative integer matrix coefficients.

3. The method as defined by claim 1, wherein G is an arbitrary compact topological group and the polynomials p(x₁, x₂, . . . x_k) and q(x₁, x₂, . . . , x_k) have arbitrary integer coefficients, and all the matrices S₁, S₂, . . . S_k have arbitrary integer matrix coefficients.

4. The method as defined by claims 1 and 2, wherein G is an arbitrary compact topological monoid, k=1 and the n×

n matrix S has non-negative integer matrix coefficients so that

A=a₀·

I+a₁·

S+a₂·

S²+ . . . +a<sub>n−

1</sub>·

S<sup>n−

1</sup> and B=b₀·

I+b₁·

S+b₂·

S²+ . . . +b<sub>n−

1</sub>·

S<sup>n−

1</sup>,

where a₀, a₁, . . . , a<sub>n−

1</sub> are non-negative integers privately generated by the first communicating party and b₀, b₁, . . . , b<sub>n−

1</sub> are non-negative integers privately generated by the second communicating party, and where I is the identity n×

n matrix.

5. The method as defined by claims 1 and 3, wherein G is an arbitrary compact topological group, k=1 and the n×

n matrix S has arbitrary integer matrix coefficients so that

A=a₀·

I+a₁·

S+a₂·

S²+ . . . +a<sub>n−

1</sub>·

S<sup>n−

1</sup> and B=b₀·

I+b₁·

S+b₂·

S²+ . . . +b<sub>n−

1</sub>·

S<sup>n−

1</sup>,

where a₀, a₁, . . . , a<sub>n−

1</sub> are arbitrary integers privately generated by the first communicating party and b₀, b₁, . . . , b<sub>n−

1</sub> are arbitrary integers privately generated by the second communicating party, and where I is the identity n×

n matrix.

6. The method as defined by claims 1, 2, and 4, wherein G is an arbitrary compact topological monoid, k=1, n=2, and the 2×

2 matrix S has non-negative integer matrix coefficients s₁₁, s₁₂, s₂₁, s₂₂ so that

7. The method as defined by claims 1, 3, and 5, wherein G is an arbitrary compact topological group, k=1, n=2, and the 2×

2 matrix S has arbitrary integer matrix coefficients s₁₁, s₁₂, s₂₁, s₂₂ so that

8. The method as defined by claims 1 and 2, wherein G is an arbitrary compact topological monoid, k=2 and the n×

n matrices S₁ and S₂ have non-negative integer matrix coefficients and satisfy S₁·

S₂=S₂·

S₁ so that

A=Σ

<sup>n−

1</sup>_i,j=0a_i,j·

S₁ⁱ·

S₂^j and B=Σ

<sup>n−

1</sup>_i,j=0b_i,j·

S₁ⁱ·

S₂^j,

where all a_i,j, i=0, 1, . . . , n−

1, and j=0, 1, . . . , n−

1, are non-negative integers privately generated by the first communicating party and all b_i,j, i=0, 1, . . . , n−

1, and j=0, 1, . . . , n−

1, are non-negative integers privately generated by the second communicating party, and where I is the identity n×

n matrix.

9. The method as defined by claims 1 and 3, wherein G is an arbitrary compact topological group, k=2 and the n×

n matrices S₁ and S₂ have arbitrary integer matrix coefficients and satisfy S₁·

S₂=S₂·

S₁ so that

A=Σ

<sup>n−

1</sup>_i,j=0a_i,j·

S₁ⁱ·

S₂^j and B=Σ

<sup>n−

1</sup>_i,j=0b_i,j·

S₁ⁱ·

S₂^j,

where all a_i,j, i=0, 1, . . . , n−

1, and j=0, 1, . . . , n−

1, are arbitrary integers privately generated by the first communicating party and all b_i,j, i=0, 1, . . . , n−

1, and j=0, 1, . . . , n−

1, are arbitrary integers privately generated by the second communicating party, and where I is the identity n×

n matrix.

10. The method as defined by claim 1, wherein n=1 and G is any compact topological monoid and the said 1×

1 matrices A and B are any non-negative integers.

11. The method as defined by claim 1, wherein n=1 and G is any compact topological group and the said 1×

1 matrices A and B are arbitrary integers.

12. The method as defined by claims 1, 2, 4, 6, and 8 wherein G is any commutative compact topological monoid.

13. The method as defined by claims 1, 3, 5, 7, and 9, wherein G is any commutative compact topological group.

14. The method as defined by claim 11, wherein n=1 and G is any connected compact Lie group.

15. The method as defined by claim 11, wherein n=1 and said G is a connected closed subgroup of the orthogonal group O(V), where V is a Euclidean vector space.

16. The method as defined by claim 11, wherein n=1 and said G is a connected closed subgroup of the unitary group U(W), where W is a Hermitian vector space.

17. The method as defined by claim 15, wherein the group G is the special orthogonal group SO(V), that is, G is the connected component of the identity in the orthogonal group O(V).

18. The method as defined by claim 16, wherein the group G is the unitary group U(W).

19. The method as defined by claim 15, wherein the set V is a Euclidean vector space of dimension m, where m is an integer greater than 1.

20. The method as defined by claim 16, wherein the set W is a Hermitian vector space of dimension m, where m is an integer greater than 0.

21. The method as defined by claim 19, wherein said V is the real vector space R^m with the standard Euclidean dot product:

22. The method as defined by claim 16, wherein said W is the complex vector space C n with the standard Hermitian dot product:

x·

y*=x₁y₁*+x₂y₂*+ . . . +x_my_m*

for any vectors x=[x₁, x₂, . . . , x_m] and y=[y₁, y₂, . . . , y_m] of C^m, where y_i* is the complex conjugate number of the complex number y_i.

23. The method as defined by claims 17 and 21, wherein the group G is the group SO_m of special orthogonal m×

m matrices, that is, SO_m is the set of all real m×

m matrices M such that the determinant of M is 1 and M·

M^T=I, where M^T is the transposed matrix of M and I is the identity m×

m matrix.

24. The method as defined by claims 18 and 22, wherein the group G is the group U_m of unitary m×

m matrices, that is, U_m is the set of all complex m×

m matrices M such that M·

M*=I, where M* is the transposed complex conjugate matrix of M and I is the identity m×

m matrix.

25. The method as defined by claims 23 and 24, wherein the group G is any of two isomorphic groups SO₂ or U₁.

26. The method as defined by claims 13 and 25, wherein the group G is a torus of dimension m, that is, G is direct product of m copies of the group U₁.

27. The method of claim 25, wherein as the group G is further defined as the semi-open interval [0, 1) of real numbers that includes 0 but does not include 1, where the group operation “

*”

is the fractional part of the sum;

28. The method as defined by the claims 1 and 27, wherein the said n-tuple g is given by:

g=(g₁, g₂, . . . , g_n),

where g₁, g₂, . . . , g_n are real numbers in the semi-open interval [0,1); and

for a given integer n×

n matrix A=(A_ij) the power g^A is given by;

g^A=(y₁, y₂, . . . , y_n),

where y_j={g₁A_1,j+g₂A_2,j+ . . . +g_nA_n,j} for j=1, 2, . . . , n; and

for a given integer n×

n matrix B=(B_ij) the power g^B is given by;

g^B=(z₁, z₂, . . . , z_n),

where z_j={g₁B_1,j+g₂B_2,j+ . . . +g_nB_n,j} for j=1, 2, . . . , n.

29. The method as defined by the claims 1, 7, 27, and 28, wherein n=2, g=(g₁, g₂), the 2×

2 matrices A and B are given by;

30. Method as defined by the claims 1, 7, 27, 28, and 29, wherein n=2, g=(g₁, g₂), and the said matrix S is given by

31. The method as defined by the claim 27, wherein for each natural number P, each element g of the group G is rounded to a rational element [g]_P of the group G according to the formula:

[g]_P=(Round(gP))/P

if Round(gP)<

P, and

[g]_P=0

if Round(gP)=P, where Round(z) stands for the standard rounding of a real number z to the closest integer.

32. The method as defined by the claims 27 and 31, wherein for each n-tuple P=(P₁, P₂, . . . , P_n) of natural numbers, each n-tuple g=(g₁, g₂, . . . , g_n) of elements of the group G is rounded to a rational n-tuple [g]_P according to the formula:

[g]_P=([g₁]_P1, [g₂]_P2, . . . , [g_n]_Pn).

33. A method of secure distribution of encryption/decryption keys among two communicating parties comprising of:

public (non-secret) selecting a natural number n and k as in claim 1;

public (non-secret) selecting a k-tuple S═

(S₁, S₂, . . . , S_k) of pairwise-commuting n×

n matrices with integer coefficients as in claim 1;

public (non-secret) selecting n-tuples natural numbers P=(P₁, P₂, . . . , P_n), Q=(Q₁, Q₂, . . . Q_n), and K=(K₁, K₂, . . . , K_n);

public (non-secret) selecting a natural number D>

1;

public (non-secret) selecting the commutative compact topological group G as in claim 27;

public (non-secret) selecting an n-tuple g=(g₁, g₂, . . . , g_n) elements in G as in claims 28, 29, 30, 31 and 32;

private (non-public) generating the polynomial p(x₁, x₂, . . . , x_k) in k variables x₁, x₂, . . . , x_k and with integer coefficients by the first communicating party as in claim 1;

private (non-public) generating the polynomial q(x₁, x₂, . . . , x_k) in k variables x₁, x₂, . . . , x_k and with integer coefficients by the second communicating party as in claim 1;

private (non-public) generating n×

n matrix A with integer coefficients by the first communicating party as in claim 1;

private (non-public) generating n×

n matrix B with integer coefficients by the first communicating party as in claim 1;

generating the n-tuple g^A by the first communicating party as in claim 1;

generating the P-rounded n-tuple [g^A]_P by the first communicating party as in claim 32;

generating the n-tuple g^B by the second communicating party as in claim 1;

generating the Q-rounded n-tuple [g^B]_Q by the second communicating party as in claim 32;

public (non-secret) transmitting the n-tuple [g^A]_P from the first communicating party to the second communicating party;

public (non-secret) transmitting the n-tuple [g^B]_Q from the second communicating party to the first communicating party;

creating the shared secrete key by the communicating parties;

generating the n-tuple [([g^A]_P)^B]_K by the second communicating party and generating the n-tuple [([g^B]_Q)]_K by the first communicating party.

34. The method as defined by the claims 28, 29, 30, 31, 32, and 33, wherein at least one coordinate of the said vector g=(g₁, g₂, . . . , g_n) is an irrational number.

35. The method as defined by the claims 28, 29, 30, 31, 32, and 33, wherein each coordinate g_i of the said vector g=(g₁, g₂, . . . , g_n) is a rational number of the form

g_i=M_i/N_i,

where 0≦

M_i≦

N_i.

36. The method as defined by the claim 33, wherein the n-tuples of natural numbers P=(P₁, P₂, . . . , P_n),Q=(Q₁, Q₂, . . . , Q_n), and K=(K₁, K₂, . . . , K_n) and the natural number D satisfy the following compatibility conditions:

Q<sup>−

1</sup>·

α

≦

(D·

K)<sup>−

1</sup>, P<sup>−

1</sup>·

β

≦

(D·

K)<sup>−

1</sup>,

where α and

β

are arbitrary public (non-secret) n×

n matrices with natural coefficients α

_ij and β

_ij respectively such that;

|A_ij|<

α

_ij, |B_ij|<

β

_ij

for all i=1,2, . . . , n, j=1,2, . . . ,n; and

P<sup>−

1</sup>=(1/P₁, 1/P₂, . . . , 1/P_n), Q<sup>−

1</sup>=(1/Q₁, 1/Q₂, . . . , 1/Q_n), (D·

K)<sup>−

1</sup>=(1/(DK₁), 1/(DK₂), . . . , 1/(DK_n)), and the vector inequality

(y₁, y₂, . . . , y_n)≦

(z₁, z₂, . . . , z_n)

is equivalent to n scalar inequalities;

y₁≦

z₁, y₂≦

z₂, . . . , y_n≦

z_n. The compatibility conditions guarantee that either at least one coordinate of [([g^A]_P)^B]<sub>D·

K</sub> equals 0, or at least one coordinate of [([g^B]_Q)^A]<sub>D·

K</sub> equals 0, or

([g^A]_P)^B−

([g^B]_Q)^A=θ

·

(D·

K)<sup>−

1</sup>,

where −

½

<

θ

<

½

.

37. The method as defined by the claim 33, wherein a vector x=(x₁,x₂, . . . , x_n) is defined to be (K, D)-consistent if:

(−

c, −

c, . . . , −

c)≦

x−

[x]_K≦

(c, c, . . . , c),

where c=½

−

1/(2D).

38. The method as defined by the claims 33, 36, and 37 wherein both n-tuples ([g^A]_P)^B and ([g^B]_Q)^A are (K, D)-consistent, which guarantees the equality of the shared keys:

[([g^A]_P)^B]_K=[([g^B]_Q)^A]_K.

39. The method as defined by the claims 30, 33, 35, 36, and 37, wherein

g=(M₁/N₁, M₂/N₂),

where θ

≦

M₁<

N₁, 0≦

M₁<

N₂; and

the 2×

2 matrices A and B are given by;

40. The method as defined by the claims 36, 37, 38, and 39, wherein each coordinate K of the said n-tuple K=(K₁, K₂, . . . K_n) is given by the formula:

K_i=r^Ci

for i=1,2, . . . , n, where r is a natural number, and C1, C2, . . . , Cn are non-negative integers.

41. The method as defined by the claims 36, 37, 38, 39, and 40, wherein each i-th coordinate of the shared key [([g^A]_P)^B]=[([g^B]_Q)^A]_K is presented as a rational r-ary number having at most Ci r-ary digits after the dot.