Communication system

Abstract

A system effective to communicate a message between two devices. A first device may include a plaintext to monoid element module effective to receive a plaintext message and apply a first function to the plaintext message to produce a first monoid element. A monoid element evaluator module may be effective to receive and insert submonoid generators into a monoid expression to produce a second monoid element in response. An encryption device module may be effective to apply a second function to the first monoid element, the second monoid element, the monoid expression, and a third monoid element to produce an encrypted plaintext message. Decryption may be performed on the encrypted plaintext message knowing the private key which includes the first function, the second function, the third monoid element and the submonoid generators list.

What is claimed is: 
     
         1 . A device effective to communicate a message, the device comprising:
 a memory, wherein the memory is effective to include
 a first function, 
 a list of submonoid generators, 
 a second function, and 
 a first monoid element, 
   a first module in communication with the memory, the first module effective to receive a message and apply the first function to the message to produce a second monoid element;   a second module in communication with the memory, the second module effective to receive and insert the submonoid generators into at least one monoid expression to produce a third monoid element; and   a third module in communication with the memory, in communication with the first module, and in communication with the second module, the third module effective to apply the second function to the first monoid element, the second monoid element, the monoid expression, and the third monoid element to produce an encrypted message.   
     
     
         2 . The device as recited in  claim 1 , further comprising:
 a random number generator effective to produce a random number; and   a fourth module in communication with the random number generator and the memory, the fourth module effective to receive the random number and generate the monoid expression in response.   
     
     
         3 . The device as recited in  claim 1 , wherein the encrypted message includes an ordered pair with a first entry that is a fourth monoid element and a second entry that is the monoid expression. 
     
     
         4 . The device as recited in  claim 1 , wherein the second function is a one way function. 
     
     
         5 . The device as recited in  claim 1 , wherein the second function is a 6-tuple (M S, N, Π, E, A, B) where
 M and N are monoids, 
 S is a group that acts on M, 
 M S denotes the semi-direct product, 
 A and B denote submonoids of M S, 
 Π denotes a monoid homomorphism from M to N, 
 E is defined by
   E:(N×S)×(M S)→(N×S)
 
     E (( n,s ),( m   1   ,s   1 ))=( n  Π( S   m   1 ), s s   1 ).
 
     M=M     S,N=     S,    
 
 and the function   is defined as: given 
 (n 0 , s 0 )∈N S and (m,s 1 )∈M S let  ; N×M→N denote the function:
     (( n   0   ,s   0 ), ( m,s   1 ))= E (( n   0   ,s   0 ), ( m, s   1 ))=(( n   0  Π( S     0     m ),  s   0    s   1 )
 
 
 
     
     
         6 . The device as recited in  claim 1 , wherein the second function is selected such that monoids M and N are chosen to be a group G and
     ( x,g )= g   −1   x g = ( g   −1    x g ).   where x, g∈G.   
     
     
         7 . The device as recited in  claim 1 , wherein:
 the message is a first message;   the monoid expression is a first monoid expression;   the encrypted message is a first encrypted plaintext message;   the device is effective to receive a second encrypted message including a fourth monoid element and a second monoid expression, and   the second module is effective to receive the second monoid expression and insert the submonoid generators into the second monoid expression to produce a fifth monoid element;   and the device further comprises:   a fourth module in communication with the memory and the second module, the fourth module effective to
 receive the fourth monoid element in the second encrypted plaintext message, 
 receive the second function, 
 receive the first monoid element, 
 receive the fifth monoid element, and 
 apply the second function to the fourth monoid element, the inverse of the fifth monoid element and the inverse of the first monoid element to produce a sixth monoid element; 
   a fifth module in communication with the memory and the fourth module, the fifth module effective to receive the sixth monoid element and the first function, and apply the first function to the sixth monoid element to produce a second message.   
     
     
         8 . The device as recited in  claim 1 , wherein:
 the message is a first message   and the device further comprises:   a random number generator effective to produce a first random number; and   a fourth module in communication with the random number generator and the memory, the fourth module effective to receive the first random number and generate the monoid expression in response, where the monoid expression is a first monoid expression; and wherein   the first module is effective to receive a second message and apply the first function to the second message to produce a fourth monoid element;   the random number generator is further effective to produce a second random number;   the fourth module is further effective to receive the second random number and generate a second monoid expression in response;   the second module is effective to receive and insert the submonoid generators into the second monoid expression to produce a fifth monoid element; and   the third module is effective to apply the second function to the first monoid element, the fourth monoid element, the second monoid expression, and the fifth monoid element to produce another encrypted message.   
     
     
         9 . The device as recited in  claim 1 , further comprising:
 a random number generator effective to produce a random number; and   a fourth module in communication with the random number generator and the memory, the fourth module effective to receive the random number and generate the monoid expression in response; wherein   the encrypted message includes an ordered pair with a first entry that is a fourth monoid element and a second entry that is the monoid expression;   the first function is a mapping function; and   the second function is a one way function.   
     
     
         10 . A device effective to decrypt an encrypted message, the device comprising:
 a memory, wherein the memory is effective to include
 a first function, 
 a list of submonoid generators, 
 a second function, and 
 a first monoid element, 
   a first module in communication with the memory, the first module effective to receive a monoid expression in the encrypted message, the first module effective to insert the submonoid generators into the monoid expression to produce a second monoid element;   a second module in communication with the memory and the first module, the second module effective to
 receive a third monoid element in the encrypted message, 
 receive the second function, 
 receive the first monoid element, 
 receive the second monoid element, and 
 apply the second function to the third monoid element, to the inverse of the second monoid element, and to the inverse of the first monoid element to produce a fourth monoid element; 
   a third module in communication with the memory and the second module, the third module effective to apply the first function to the fourth monoid element to produce the message.   
     
     
         11 . The device as recited in  claim 10 , wherein the second function is a one way function. 
     
     
         12 . The device as recited in  claim 10 , wherein the second function is a 6-tuple (M S, N, Π, E, A, B) where
 M and N are monoids, 
 S is a group that acts on M, 
 M S denotes the semi-direct product, 
 A and B denote submonoids of M S, 
 Π denotes a monoid homomorphism from M to N, E is defined by
   E:(N×S)×(M S)→(N×s)
 
     E (( n,s ), ( m   1   ,s   1 ))=( n  Π( S   m   1 ), s s   1 ),
 
   M=M S, N=N S, 
 
 and the function   is defined as: given 
 (n 0 ,s 0 )∈N S and (m,s 1 )∈M S let  : N×M→N denote the function:
     (( n   0   ,s   0 ), ( m,s   1 ))= E (( n   0   ,s   0 ), ( m,s   1 ))=(( n   0  Π( S     o     m ), s   0    s   1 ).
 
 
 
     
     
         13 . The device as recited in  claim 10 , wherein the second function is selected such that monoids M and N are chosen to be a group G and
     ( x,g )= g   −1    x g = ( g   −1    x g ).   where x, g∈G.   
     
     
         14 . A system effective to communicate a message, the system comprising:
 a first device in communication with a second device over a network;   wherein the first device includes
 a first memory, wherein the first memory is effective to include
 a first function, 
 a list of submonoid generators, 
 a second function, and 
 a first monoid element, 
 
   a first module in communication with the first memory, the first module effective to receive a message and apply the first function to the message to produce a second monoid element;   a second module in communication with the memory, the second module effective to receive and insert the submonoid generators into at least one monoid expression to produce a third monoid element; and   a third module in communication with the memory, in communication with the first module, and in communication with the second module, the third module effective to apply the second function to the first monoid element, the second monoid element, the monoid expression, and the third monoid element to produce an encrypted message including a fourth monoid element and the monoid expression;
 wherein the second device includes
 a second memory, wherein the second memory is effective to include
 the first function, 
 the list of submonoid generators, 
 the second function, and 
 the first monoid element, 
 
 a fourth module in communication with the second memory, the fourth module effective to receive the monoid expression in the encrypted message, the fourth module effective to insert the submonoid generators into the monoid expression to re-produce the third monoid element; 
 a fifth module in communication with the second memory and the fourth module, the fifth module effective to
 receive the fourth monoid element in the encrypted message, 
 receive the second function, 
 receive the first monoid element, 
 receive the third monoid element, and 
 apply the second function to the fourth monoid element, the inverse of the first monoid element and the inverse of the third monoid element to produce the second monoid element; and 
 
 a sixth module in communication with the second memory and the fifth module, the sixth module effective to apply the first function to the second monoid element to re-produce the message. 
 
   
     
     
         15 . The system as recited in  claim 14 , wherein the network is a near field communications network 
     
     
         16 . The system as recited in  claim 14 , wherein:
 the network is an RF-ID network,   the first device is one of a tag or a reader; and   the second device is the other of the tag or the reader.   
     
     
         17 . The system as recited in  claim 14 , wherein the first device further comprises:
 a random number generator effective to produce a random number; and   a seventh module in communication with the random number generator, the seventh module effective to receive the random number and generate the monoid expression in response.   
     
     
         18 . The system as recited in  claim 14 , wherein the second function is a one way function. 
     
     
         19 . The system as recited in  claim 14 , wherein the second function is a 6-tuple (M S, N, Π, E, A, B) where
 M and N are monoids, 
 S is a group that acts on M, 
 M S denotes the semi-direct product, 
 A and B denote submonoids of M S, 
 Π denotes a monoid homomorphism from M to N, 
 E is defined by
   E: (N×S)×(M S)→(N×S)
 
     E (( n,s ), ( m   1   ,s   1 ))=( n  Π( S   m   1 ), z s   1 ).
 
   M=M S, N=N S 
 
 and the function   is defined as: given 
 (n 0 ,s 0 )∈N S and (m,s 1 )∈M S let  : N×M→N denote the function:
     (( n   0   ,s   0 ), ( m ,s   1 ))= E (( n   0   , s   0 ), ( m, s   1 ))=(( n   0  Π( S     0     m ). s   0    s   1 )
 
 
 
     
     
         20 . The system as recited in  claim 14 , wherein the first device further comprises:
 a random number generator effective to produce a random number; and   a seventh module in communication with the random number generator, the seventh module effective to receive the random number and generate the monoid expression in response; wherein   the first function is a mapping function; and   the second function is a one way function.