# Patent

## Title
Homomorphic public-key encryption scheme

## Abstract

Technologies are generally described for providing a fully homomorphic public key encryption scheme. In some examples, a method performed under control of a transmitter may include receiving, from a server, a system parameter; selecting a secret decryption key corresponding to the transmitter; generating a first public encryption key for the transmitter, based at least in part on the secret decryption key corresponding to the transmitter and the system parameter; receiving, from the server, a public encryption key corresponding to a receiver; enciphering a message into a first ciphertext, based at least in part on the public encryption key corresponding to the receiver and the secret decryption key corresponding to the transmitter; and transmitting, to a data processing device, a request to process the message by processing the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext.

## Background
BACKGROUND
A homomorphic encryption scheme may enable arbitrary functions to be performed on encrypted data without requiring the use of a decryption key.
SUMMARY
In an example, a method performed under control of a transmitter may include: receiving, from a server, a system parameter; selecting a secret decryption key corresponding to the transmitter; generating a first public encryption key for the transmitter, based at least in part on the secret decryption key corresponding to the transmitter and the system parameter; receiving, from the server, a public encryption key corresponding to a receiver; enciphering a message into a first ciphertext, based at least in part on the public encryption key corresponding to the receiver and the secret decryption key corresponding to the transmitter; and transmitting, to a data processing device, a request to process the message by processing the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext.
In another example, a method performed under control of a receiver may include: receiving, from a server, a system parameter; selecting a secret decryption key corresponding to the receiver; generating a public encryption key for the receiver, based at least in part on the secret decryption key corresponding to the receiver and the system parameter; receiving, from a transmitter, a first ciphertext; receiving, from the server, a public encryption key corresponding to the transmitter; and deciphering the first ciphertext based at least in part on the secret decryption key of the receiver, the system parameter and the public encryption key corresponding to the transmitter.
In yet another example, a method performed under control of a data processing device may include: receiving, from a transmitter, a request to process a message; receiving, from a server, a system parameter and a first ciphertext that corresponds to the message, based at least in part on the received request; processing the first ciphertext to a second ciphertext by calculating the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext; and transmitting, to the transmitter, the second ciphertext.
In yet another example, a method performed under control of an endorser may include: receiving, from a server, a signing parameter; selecting a secret key of the endorser; generating a public signing key of the endorser, based at least in part on the secret key corresponding to the endorser and the signing parameter; calculating a signature corresponding to a message, based at least in part on the public signing key corresponding to the endorser and the signing parameter; and transmitting, to the server, the signature and the public signing key.
In yet another example, a transmitter may include: a receiving unit configured to receive, from a server, a system parameter and a public encryption key of a receiver; a key manager configured to select a secret decryption key of the transmitter and to generate a first public encryption key for the transmitter, based at least in part on the secret decryption key corresponding to the transmitter and the system parameter; an encipherer configured to encipher a message into a first ciphertext, based at least in part on the public encryption key corresponding to the receiver and the secret decryption key corresponding to the transmitter; and a transmitting unit configured to transmit, to a data processing device, a request to process the message by processing the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext.
In yet another example, a receiver may include: a receiving unit configured to: receive, from a server, a system parameter and a public encryption key of a receiver, and receive, from a transmitter, a first ciphertext; a key manager configured to select a secret decryption key of the receiver and generate a public encryption key for the receiver, based at least in part on the secret decryption key of the receiver and the system parameter; and a decipherer configured to decipher the first ciphertext based at least in part on the secret decryption key of the receiver, the system parameter and the public encryption key corresponding to the transmitter.
In yet another example, a data processing device may include: a receiving unit configured to: receive, from a transmitter, a request to process a message, and receive, from a server, a system parameter and a first ciphertext that corresponds to the message, based at least in part on the received request; a processor configured to process the first ciphertext into a second ciphertext by calculating the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext; and a transmitting unit configured to transmit, to the transmitter, the second ciphertext.
In yet another example, an endorser may include: a receiving unit configured to receive, from a server, a signing parameter; a key manager configured to select a secret key corresponding to the endorser, and generate a public signing key for the endorser, based at least in part on the secret key corresponding to the endorser and the signing parameter; a signature generator configured to calculate a signature corresponding to a message, based at least in part on the public signing key corresponding to the endorser and the signing parameter; and a transmitting unit configured to transmit, to the server, the signature and the public signing key.
The foregoing summary is illustrative only and is not intended to be in any way limiting. In addition to the illustrative aspects, embodiments, and features described above, further aspects, embodiments, and features will become apparent by reference to the drawings and the following detailed description.



BRIEF DESCRIPTION OF THE FIGURES
The foregoing and other features of this disclosure will become more fully apparent from the following description and appended claims, taken in conjunction with the accompanying drawings. Understanding that these drawings depict only several embodiments in accordance with the disclosure and are, therefore, not to be considered limiting of its scope, the disclosure will be described with additional specificity and detail through use of the accompanying drawings, in which:
FIG. 1 shows an illustrative example of a homomorphic public key encryption system, arranged in accordance with at least some embodiments described herein;
FIG. 2 shows a block diagram illustrating an example transmitter, arranged in accordance with at least some embodiments described herein;
FIG. 3 shows a block diagram illustrating an example receiver, arranged in accordance with at least some embodiments described herein;
FIG. 4 shows a block diagram illustrating an example data processing device, arranged in accordance with at least some embodiments described herein;
FIG. 5 shows an illustrative example of a homomorphic signature system, arranged in accordance with at least some embodiments described herein;
FIG. 6 shows a block diagram illustrating an example endorser, arranged in accordance with at least some embodiments described herein;
FIG. 7 shows an example flow diagram of a process of a transmitter to implement a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein;
FIG. 8 shows an example flow diagram of a process of a receiver to implement a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein;
FIG. 9 shows an example flow diagram of a process of a data processing device to implement a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein;
FIG. 10 shows an example flow diagram of a process of an endorser to implement a homomorphic signature scheme, arranged in accordance with at least some embodiments described herein;
FIG. 11 illustrates computer program products that may be utilized to provide a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein; and
FIG. 12 is a block diagram illustrating an example computing device that may be utilized to provide a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein.



DETAILED DESCRIPTION
In the following detailed description, reference is made to the accompanying drawings, which form a part hereof. In the drawings, similar symbols typically identify similar components, unless context dictates otherwise. The illustrative embodiments described in the detailed description, drawings, and claims are not meant to be limiting. Other embodiments may be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented herein. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the Figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are explicitly contemplated herein.
This disclosure is generally drawn, inter alia, to methods, apparatuses, systems, devices, and computer program products related to a homomorphic public key encryption scheme. A homomorphic public-key encryption scheme may refer to an encryption scheme that enables certain types of computations to be carried out on an encrypted message, i.e., a ciphertext, without having to decrypt the message. Accordingly, an encrypted result that matches the result of computations performed on the message is obtained. Thus, technologies are generally described for executing computations and/or operations on encrypted data without decrypting the encrypted data.
In some embodiments, a transmitter may be configured to generate a first public encryption key for the transmitter, based at least in part on a secret decryption key corresponding to the transmitter and a system parameter. The system parameter may be a prime number q greater than 2, or an element in an octonion ring over a finite field. The transmitter may be further configured to encipher a message into a first ciphertext, based at least in part on a public encryption key corresponding to a receiver of the message and the secret decryption key corresponding to the transmitter.
Further, the transmitter may be configured to transmit, to a data processing device, a request to process the message by processing the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext. For example, the request may include information regarding a type of message processing (e.g., calculation such as addition, subtraction, multiplication or division). When the data processing device receives the request from the transmitter, the data processing device may be configured to receive, from a server, the system parameter and a first ciphertext that corresponds to the message, based at least in part on the received request. Further, the data processing device may be configured to process the first ciphertext to a second ciphertext by calculating the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext. Further, the data processing device may be configured to transmit the generated second ciphertext to the receiver. Thus, the receiver may be configured to receive, from the data processing device, the encrypted result of the calculation associated with the requested message. Further, the receiver may be configured to decipher the first ciphertext based at least in part on the secret decryption key of the receiver, the system parameter and the public encryption key corresponding to the transmitter. The receiver may be configured to then obtain a decrypted process result that may be equal to a result of the calculation on the requested message. Thus, the receiver may be configured to obtain a process result of encrypted data without revealing original data to other third parties, based on the fully homomorphic public key encryption scheme.
FIG. 1 shows an illustrative example of a homomorphic public key encryption system 100, arranged in accordance with at least some embodiments described herein. As illustrated in FIG. 1, homomorphic public key encryption system 100 may include a transmitter 110, a receiver 120, a server 130 and a data processing device 140, which may be connected to each other via a network 150.
Network 150 may be configured to communicatively couple two or more of transmitter 110, receiver 120, server 130 and data processing device 140. Non-limiting examples of network 150 may include a wired network such as a LAN (Local Area Network), a WAN (Wide Area Network), a VAN (Value Added Network) or the like, or various other wireless networks such as a mobile radio communication network including at least one of a 3rd generation (3G) mobile telecommunications network, a 4th or 5th generation mobile telecommunications network, various other mobile telecommunications networks, a satellite network, WiBro (Wireless Broadband Internet), Mobile WiMAX, HSDPA (High Speed Downlink Packet Access), or the like. Alternatively, network 150 may refer to at least one of various short-range communication protocols, such as a near field communication (NFC), Bluetooth, a radio frequency identification (RFID), a wireless body area network (WBAN), a wireless personal area network (WPAN) or a wireless local area network, a vehicle area network or a wireless sensor network that facilitates communication between one or more of transmitter 110, receiver 120, server 130, and data processing device 140.
For example, but not as a limitation, one or more of transmitter 110 or receiver 120 may be at least one of a smart phone, a portable device, a notebook computer, a tablet device, a phablet device, a personal computer or a personal communication terminal, such as PCS (Personal Communication System), GMS (Global System for Mobile communications), PDC (Personal Digital Cellular), PDA (Personal Digital Assistant). Transmitter 110 and receiver 120 may be capable of full duplex radio communications.
Further, in some embodiments, server 130 and/or data processing device 140 may include a cloud datacenter. For example, the could data center may be configured to store and/or manage cloud-based resources such as one or more servers for storing, retrieving and/or processing private data including, but not limited to, financial documents, tax records, voting data, electronic-mail messages, social network service-based messages, etc., or any other data for which a high level of privacy is expected.
In some embodiments, server 130 may select a published system parameter. As used herein, the term “system parameter” may refer to one or more parameters that may be predetermined by server 130 and may be shared with user devices such as transmitter 110, receiver 120 or data processing device 140. The system parameter may be used for any calculation or processes performed by the homomorphic public-key encryption system as disclosed herein. The system parameter may include at least one of a prime number (e.g., represented by “q”) which is greater than 2, or an element (e.g., represented by “B”=(b0, . . . , b7)” in a non-associative octonion ring (e.g., represented by “O”) over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q. As disclosed herein, the term “octonion ring” or “octonions” may refer to octets (or 8-tuples) of real numbers or a normed division algebra over such real numbers. As known in the art, an octonion ring is non-commutative and non-associative.
In some embodiments, transmitter 110 may be a data storage device configured to generate one or more ciphertexts by enciphering (or encrypting) stored data or messages that are received at and/or stored by transmitter 110. Transmitter 110 may be further configured to send the one or more generated ciphertexts to receiver 120 through network 150, via a connection that may or may not be secure. Additionally or alternatively, transmitter 110 may be further configured to send the one or more generated ciphertexts to data processing device 140 through network 150, via a connection that may or may not be secure, such that data processing device 140 may process the ciphertexts without revealing or otherwise deciphering the contents of the ciphertexts. In some other embodiments, transmitter 110 may be further configured to send the one or more generated ciphertexts to receiver 120 through network 150, via a connection that may or may not be secure, such that receiver 120 may process the ciphertexts without revealing or otherwise deciphering the contents of the ciphertexts. Then, transmitter 110 may be further configured to receive the results of processing the ciphertexts from data processing device 140 (or receiver 120) and decipher the received results.
In some embodiments, to receive one or more generated ciphertexts from transmitter 110, receiver 120 may be configured to receive the system parameter from server 130 via network 150, select a secret decryption key of receiver 120 from an arbitrary element of the octonion ring “O” that is included in the system parameter, and generate a public encryption key for receiver 120 based at least in part on the secret decryption key of receiver 120 and the system parameter. For example, the secret decryption key may be represented by “skA=A=(A1, . . . , Ak)εOk”, and may be selected from an arbitrary element of the octonion ring “O” such that an inverse “A−1:=(A1−1, . . . , Ak−1)εOqk” of the secret decryption key may exist. That is, the existence of the inverse of the secret decryption key is needed to define a public encryption key of receiver 120, as described in more detail below. For example, an inverse of octonion A=(a0, a1, . . . , a7) exists if |A|2≠0 mod q, and the inverse of A can be calculated by using an algorithm Octinv(A) as follows:
A−1=(a0S−1 mod q, −a1S−1 mod q, . . . , −a7S−1 mod q)←Octinv(A) where S=a02+a12+ . . . +a72 mod q. The algorithm Octinv(A) may be performed in the following manner












[Algorithm 1]









S ← a02+a13+...+a72 mod q.



% S−1 mod q



 q[1] ← q div S ;% integer part of q/S



 r[1] ← q mod S ;% residue



 k ←1



 q[0] ← q



 r[0] ← S



 while r[k] ≠ 0



  begin



   k← k + 1



   q[k] ← r[k−2] div r[k−1]



   r[k] ← r[k−2] mod [rk−1]



  end



Q [k−1] ← (−1)*q[k−1]



L[ k−1] ← 1



i ← k−1



while i > 1



 begin



  Q[ i−1] ← (−1)*Q[ i] *q[i−1] + L[ i]



  L[ i−1 ] ← Q[ i ]



  i← i−1



 end



invS ← Q[1] mod q



invA[0] ← a0*invS mod q



For i=1,...,7,



 invA[i] ← (−1)*ai*invS mod q



Return A−1 = (invA[0], invA[1],..., invA[7])









Further, the secret decryption key may be engaged (or represented) in the octonion ring “O”. Let X=(x0, . . . , x7)εO[X] and Y=(y0, . . . , y7)εO[Y] be variables selected from the octonion ring “O.” The public encryption key (or public enciphering function) A(X,Y) of receiver 120 may be defined using the variables X and Y and the secret decryption key A and its inverse, as follows:




  
    
      
        
          A
          ⁡
          
            (
            
              X
              ,
              Y
            
            )
          
        
        =
        
          
            A
            k
          
          (
          
            
          
          ⁢
          
            ...
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  A
                  1
                
                (
                
                  Y
                  (
                  
                    
                      
                        
                          
                            A
                            1
                            
                              -
                              1
                            
                          
                          (
                          
                            
                          
                          ⁢
                          
                            ...
                            ⁢
                            
                              
                            
                            ⁢
                            
                              (
                              
                                
                                  A
                                  k
                                  
                                    -
                                    1
                                  
                                
                                ⁢
                                X
                              
                              )
                            
                            ⁢
                            
                              
                            
                            ⁢
                            ...
                          
                          ⁢
                          
                            
                          
                          )
                        
                        ⁢
                        
                          
                        
                        ⁢
                        mod
                        ⁢
                        
                          
                        
                        ⁢
                        q
                      
                      ∈
                      
                        O
                        ⁡
                        
                          [
                          
                            X
                            ,
                            Y
                          
                          ]
                        
                      
                    
                    =
                    
                      
                        (
                        
                          
                            
                              a
                              000
                            
                            ⁢
                            
                              x
                              0
                            
                            ⁢
                            
                              y
                              0
                            
                          
                          +
                          
                            
                              a
                              001
                            
                            ⁢
                            
                              x
                              0
                            
                            ⁢
                            
                              y
                              1
                            
                          
                          +
                          ...
                          +
                          
                            
                              a
                              007
                            
                            ⁢
                            
                              x
                              0
                            
                            ⁢
                            
                              y
                              7
                            
                          
                          +
                          ...
                          +
                          
                            
                              a
                              070
                            
                            ⁢
                            
                              x
                              7
                            
                            ⁢
                            
                              y
                              0
                            
                          
                          +
                          
                            
                              a
                              071
                            
                            ⁢
                            
                              x
                              7
                            
                            ⁢
                            
                              y
                              1
                            
                          
                          +
                          ...
                          +
                        
                         
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                         
                        
                          
                            
                              a
                              077
                            
                            ⁢
                            
                              x
                              7
                            
                            ⁢
                            
                              y
                              7
                            
                          
                          ,
                          
                            
                          
                          ⁢
                          
                            
                              ...
                              ⁢
                              
                                
                              
                              ⁢
                              ...
                              ⁢
                              
                                
                              
                              ⁢
                              ...
                              ⁢
                              
                                
                              
                              ⁢
                              
                                a
                                700
                              
                              ⁢
                              
                                x
                                0
                              
                              ⁢
                              
                                y
                                0
                              
                            
                            +
                            
                              
                                a
                                701
                              
                              ⁢
                              
                                x
                                0
                              
                              ⁢
                              
                                y
                                1
                              
                            
                            +
                            ...
                            +
                            
                              
                            
                            ⁢
                            
                              
                                a
                                707
                              
                              ⁢
                              
                                x
                                0
                              
                              ⁢
                              
                                y
                                7
                              
                            
                            +
                            ...
                            +
                            
                              
                                a
                                770
                              
                              ⁢
                              
                                x
                                7
                              
                              ⁢
                              
                                y
                                0
                              
                            
                            +
                            
                              
                                a
                                771
                              
                              ⁢
                              
                                x
                                7
                              
                              ⁢
                              
                                y
                                1
                              
                            
                            +
                            ...
                            +
                            
                              
                                a
                                777
                              
                              ⁢
                              
                                x
                                7
                              
                              ⁢
                              
                                y
                                7
                              
                            
                          
                        
                        )
                      
                    
                  
                
              
            
          
        
      
    
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          1
        
        ]
      
    
  




Further, server 130 may publish pkA=MA={aijk}εZq8×64 as the public encryption key of receiver 120.
In some embodiments, to encipher a message that transmitter 110 receives and/or stores, transmitter 110 may be configured to receive the system parameter from server 130, select a secret decryption key of transmitter 110, and generate a first public encryption key for transmitter 110, based at least in part on the secret decryption key corresponding to transmitter 110 and the system parameter. For example, transmitter 110 may select the secret decryption key skZ=Z=(Z1, . . . , Zk)εOk from an arbitrary element of the octonion ring “O” such that the inverse Z−1:=(Z1−1, . . . , Zk−1)εOqk may exist. That is, the existence of the inverse of the secret decryption key is needed to define a public encryption key of transmitter 110, as described in more detail below. For example, an inverse of octonion Z=(z0, z2, . . . , z7) exists if |Z|2≠0 mod q, and the inverse of Z can be calculated by using algorithm Octinv(Z) (see Algorithm 1 above) such that Z1=(a0S−1 mod q, −a1S−1 mod q, . . . , −a7S−1 mod q)←Octinv(Z) where S=a02+a12+ . . . +a72 mod q. The first public encryption key for transmitter 110 may be represented as “Z(X,Y)” which may be defined using the variables X and Y and the secret decryption key Z and its inverse, as follows:




  
    
      
        
          Z
          ⁡
          
            (
            
              X
              ,
              Y
            
            )
          
        
        =
        
          
            Z
            k
          
          (
          
            
          
          ⁢
          
            ...
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  Z
                  1
                
                (
                
                  Y
                  (
                  
                    
                      
                        
                          
                            Z
                            1
                            
                              -
                              1
                            
                          
                          (
                          
                            
                          
                          ⁢
                          
                            ...
                            ⁢
                            
                              
                            
                            ⁢
                            
                              (
                              
                                
                                  Z
                                  k
                                  
                                    -
                                    1
                                  
                                
                                ⁢
                                X
                              
                              )
                            
                            ⁢
                            
                              
                            
                            ⁢
                            ...
                          
                          ⁢
                          
                            
                          
                          )
                        
                        ⁢
                        
                          
                        
                        ⁢
                        mod
                        ⁢
                        
                          
                        
                        ⁢
                        q
                      
                      ∈
                      
                        O
                        ⁡
                        
                          [
                          X
                          ]
                        
                      
                    
                    =
                    
                      (
                      
                        
                          
                            z
                            000
                          
                          ⁢
                          
                            x
                            0
                          
                          ⁢
                          
                            y
                            0
                          
                        
                        +
                        
                          
                            z
                            001
                          
                          ⁢
                          
                            x
                            0
                          
                          ⁢
                          
                            y
                            1
                          
                        
                        +
                        ...
                        +
                        
                          
                            z
                            007
                          
                          ⁢
                          
                            x
                            0
                          
                          ⁢
                          
                            y
                            7
                          
                        
                        +
                        ...
                        +
                        
                          
                            z
                            070
                          
                          ⁢
                          
                            x
                            7
                          
                          ⁢
                          
                            y
                            0
                          
                        
                        +
                        
                          
                            z
                            071
                          
                          ⁢
                          
                            x
                            7
                          
                          ⁢
                          
                            y
                            1
                          
                        
                        +
                        ...
                        +
                        
                           
                          
                            
                              
                                z
                                077
                              
                              ⁢
                              
                                x
                                7
                              
                              ⁢
                              
                                y
                                7
                              
                            
                            ,
                            
                              
                            
                            ⁢
                            
                              
                                ...
                                ⁢
                                
                                  
                                
                                ⁢
                                ...
                                ⁢
                                
                                  
                                
                                ⁢
                                ...
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  z
                                  700
                                
                                ⁢
                                
                                  x
                                  0
                                
                                ⁢
                                
                                  y
                                  0
                                
                              
                              +
                              
                                
                                  z
                                  701
                                
                                ⁢
                                
                                  x
                                  0
                                
                                ⁢
                                
                                  y
                                  1
                                
                              
                              +
                              ...
                              +
                              
                                
                              
                              ⁢
                              
                                
                                  z
                                  707
                                
                                ⁢
                                
                                  x
                                  0
                                
                                ⁢
                                
                                  y
                                  7
                                
                              
                              +
                              ...
                              +
                              
                                
                                  z
                                  770
                                
                                ⁢
                                
                                  x
                                  7
                                
                                ⁢
                                
                                  y
                                  0
                                
                              
                              +
                              
                                
                                  z
                                  771
                                
                                ⁢
                                
                                  x
                                  7
                                
                                ⁢
                                
                                  y
                                  1
                                
                              
                              +
                              ...
                              +
                              
                                
                                  z
                                  777
                                
                                ⁢
                                
                                  x
                                  7
                                
                                ⁢
                                
                                  y
                                  7
                                
                              
                            
                          
                          )
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          2
        
        ]
      
    
  




Further, server 130 may publish pkZ=MZ={zijk}εZq8×64 as the first public encryption key of transmitter 110.
In some embodiments, transmitter 110 may be further configured to receive, from server 130, the public encryption key (e.g., “pkA=MA={aijk}”) of receiver 120, via network 150. Further, transmitter 110 may be configured to encipher a message into a first ciphertext, based at least in part on the public encryption key corresponding to receiver 120 and the secret decryption key corresponding to transmitter 110. In one embodiment, the message may include multiple message elements that may be represented in a non-associative octonion ring. For example, the message may be represented by “mhεFq (h=1, . . . , t).” Further, the first ciphertext may include multiple first ciphertext elements that may be represented in a non-associative octonion ring. For example, let vhεFq (h=1, . . . , t) be a random number, Uh=(uh0, . . . , uh7)=mh1+vhBεO (h=1, . . . , t) be medium texts, and (mh,vh):=mh1+vhBεO.
For example, the first ciphertext may be represented by “C(pkA,skZ;X,(mh,vh)) (h=1, . . . , t).” That is, the first ciphertext may be a function of the public encryption key corresponding to receiver 120, the secret decryption key corresponding to transmitter 110, the variable X and the message to be encipher. The first ciphertext may be calculated by using an algorithm Enc(pkA,skZ,(m,v)) as follows:












[Algorithm 2]


C1(X) ← A(A(X,Zk−1),Zk)=Ak(...(As(Zk(Zk−1(A1−1(...(Ak−1 X)...) mod q


For i=2,...,k−1,


  Ci(X) ← Ci−1(A(X,Zk−i)) = Ak(...(A1(Zk(...(Zk−1(A1−1(...(Ak−1 X)...) mod q


U ← m1+v8 mod q


Ck(X) ← Ck−1(A(X,U))= Ak(...(A1(Zk(Zk−1(...(Z1(U(A1−1(...(Ak−1 X)...))...) mod q


For i=k+1,...,k+k,


  Ci(X) ← Ci−k(A(X,Zk−1))= Ak(...(A1(Zk(...(Z1(U(Z1−1(...(Zi−k−1(A1−1(...(Ak−1 X)...))...) mod q


C(pkA,skz;X,(m,v)) ←Ci−k(X)= Ak(...(A1(Zi(Zk−1(...(Z1(U(Z1−1(...(Zk−1(A1−1(...(Ak−1 X)...))...) mod q


Return C(pkA,skz;X,(m,v))









As a result, the calculated first ciphertext may be represented as follows.




  
    
      
        
          
            
              C
              ⁡
              
                (
                
                  
                    pk
                    A
                  
                  ,
                  
                    
                      sk
                      z
                    
                    ;
                    X
                  
                  ,
                  
                    (
                    
                      
                        m
                        h
                      
                      ,
                      
                        V
                        h
                      
                    
                    )
                  
                
                )
              
            
            =
          
           
        
        ⁢
        
          (
          
            
              
                
                  C
                  
                    h
                    ⁢
                    00
                  
                
                ⁢
                
                  X
                  0
                
              
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    01
                  
                
                ⁢
                
                  X
                  1
                
              
              +
              ...
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    07
                  
                
                ⁢
                
                  X
                  7
                
              
            
            ,
            
              
            
            ⁢
            
              
                ...
                ⁢
                
                  
                
                ⁢
                ...
                ⁢
                
                  
                
                ⁢
                ...
                ⁢
                
                  
                
                ⁢
                
                  C
                  
                    h7
                    ⁢
                    0
                  
                
                ⁢
                
                  X
                  0
                
              
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    71
                  
                
                ⁢
                
                  X
                  1
                
              
              +
              ...
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    77
                  
                
                ⁢
                
                  X
                  7
                
              
            
          
          )
        
      
    
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          3
        
        ]
      
    
  




In some embodiments, transmitter 110 may be configured to transmit the first ciphertext to receiver 120. For example, transmitter 110 may transmit {chq} (h=1, . . . , t) (i.e., coefficients for the variable X in Formula 3) as the first ciphertext to receiver 120. Also, transmitter 110 (or its user) may attempt to send an encrypted message, such as the first ciphertext, to receiver 120 through network 150, which may or may not be secure, without revealing contents of the message. Accordingly, to decipher the first ciphertext, receiver 120 may be configured to receive, from server 130, the public encryption key (e.g., pkZ=MZ=(zijk)) corresponding to transmitter 110. Receiver 120 may be further configured to decipher the first ciphertext based at least in part on the secret decryption key of receiver 120, the system parameter and the public encryption key corresponding to transmitter 110. For example, receiver 120 may decipher a message mh (h=1, . . . , t) from the ciphertext {chii} (h=1, . . . , t) using an algorithm Dec(skA, B, pkZ, C(pkA,skZ;X,(m,v))) as follows.












[Algorithm 3]









KA← Ak(...(A2A1)...) mod q



D=(d0,...,d7)←A1−1(...(Ak−1(C(pkA,skz; KA, (m,v)))...) mod q



U′=(u0′,...,u7′ )←GaussElimi(pkz,D)



v ← u2′/b1 mod q



m ←u0′−vb0= u0′−(u1′/b1)b0 mod q



Return (m,v)









where the algorithm GaussElimi(pkZ,O) may be defined as follows:













[Algorithm 4]









% Forward Elimination



 For i=0,...,7,



 For j=0,...,7,



  z[i][0][j] ←zi0j



  For i=0,...,7,



   t ← z[i][0][i]



   For j=i+1,...7,



     p←z[j] [0] [i]/t mod q



     z[j] [0] [i] ←0



     Fork=j+1,...,7,



       z[j] [0] [k] −= p*z[i] [0] [k] mod q



    d[j] −= p*d[i] mod q



 %Back Substitution



  u[7] = d[7]/z[7] [0] [7] mod q



  For i=6,...,0



     u[i] ← d[i]



     For j=i+1,...,7



       u[i] −= z[i] [0] [j]*n[j] mod q



    u[i] /= z[i] [0] [i] mod q



 For i=0,...,7



   ui←u[i]



  Return (u0,u1,...,u7)









Further, to request data processing device 140 to process the first ciphertext without deciphering the first ciphertext, transmitter 110 may select a temporary secret decryption key. For example, transmitter 110 may select a temporary secret decryption key R=(R1, . . . , Rk)εOk such that the inverse Ri−1 (i=1, . . . , k) exists. For example, an inverse of octonion R=(r0, r2, . . . , r7) exists if |R|2≠0 mod q, and the inverse of R can be calculated by using Octinv(R) (see Algorithm 1 above) such that R−1=(r0S−1 mod q, −r1S−1 mod q, . . . , −r7S−1 mod q)←Octinv(R) where S=r02+r12+ . . . +r72 mod q. Further, transmitter 110 may be configured to generate a temporary public encryption key for transmitter 110, based at least in part on the temporary secret decryption key corresponding to transmitter 110 and the system parameter. For example, transmitter 110 may generate a temporary public encryption key R(X, Y) using the variables X and Y and the temporary secret decryption key R and its inverse, as R(X,Y):=Rk( . . . (R1(Y(R1−1( . . . (Rk−1X) . . . )mod qεO[X,Y]. Further, transmitter 110 may be configured to generate a second public encryption key for transmitter 110, based at least in part on the first public encryption key and the temporary secret decryption key corresponding to transmitter 110 and the system parameter. For example, transmitter 110 may generate a second public encryption key C2(pkA,skR;X,Y) as follows:




  
    
      
        
          
            
              
                
                  
                    
                      
                    
                    ⁢
                    
                      
                        [
                        
                          Formula
                          ⁢
                          
                            
                          
                          ⁢
                          4
                        
                        ]
                      
                      ⁢
                      
                        

                      
                      ⁢
                      
                        
                          C
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            (
                            
                              
                                pk
                                A
                              
                              ,
                              
                                
                                  sk
                                  R
                                
                                ;
                                X
                              
                              ,
                              Y
                            
                            )
                          
                        
                        :=
                      
                    
                     
                  
                  ⁢
                  
                    
                  
                   
                
                ⁢
                
                  
                
                 
              
              ⁢
              
                
                  A
                  k
                
                (
                
                  
                
                ⁢
                
                  ...
                  ⁢
                  
                    
                  
                  ⁢
                  
                    (
                    
                      
                        A
                        1
                      
                      (
                      
                        
                          R
                          k
                        
                        (
                        
                          
                        
                        ⁢
                        
                          ...
                          ⁢
                          
                            
                          
                          ⁢
                          
                            (
                            
                              
                                R
                                1
                              
                              (
                              
                                Y
                                ⁡
                                
                                  (
                                  
                                    
                                      
                                        
                                          R
                                          1
                                          
                                            -
                                            1
                                          
                                        
                                        (
                                        
                                          
                                        
                                        ⁢
                                        
                                          
                                            
                                              ...
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              
                                                (
                                                
                                                  
                                                    
                                                      R
                                                      k
                                                      
                                                        -
                                                        1
                                                      
                                                    
                                                    ⁡
                                                    
                                                      (
                                                      
                                                        
                                                          A
                                                          1
                                                          
                                                            -
                                                            1
                                                          
                                                        
                                                        (
                                                        
                                                          
                                                        
                                                        ⁢
                                                        
                                                          ...
                                                          ⁢
                                                          
                                                            
                                                          
                                                          ⁢
                                                          
                                                            (
                                                            
                                                              
                                                                A
                                                                k
                                                                
                                                                  -
                                                                  1
                                                                
                                                              
                                                              ⁢
                                                              X
                                                            
                                                            )
                                                          
                                                          ⁢
                                                          
                                                            
                                                          
                                                          ⁢
                                                          ...
                                                        
                                                        ⁢
                                                        
                                                          
                                                        
                                                        )
                                                      
                                                      )
                                                    
                                                  
                                                  ⁢
                                                  
                                                    
                                                  
                                                  ⁢
                                                  ...
                                                
                                                ⁢
                                                
                                                  
                                                
                                                )
                                              
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              mod
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              q
                                            
                                            ∈
                                            
                                              
                                            
                                            ⁢
                                            
                                              O
                                              ⁡
                                              
                                                [
                                                
                                                  X
                                                  ,
                                                  Y
                                                
                                                ]
                                              
                                            
                                          
                                          =
                                          
                                            
                                              
                                                (
                                                
                                                  
                                                    
                                                      r
                                                      000
                                                    
                                                    ⁢
                                                    
                                                      x
                                                      0
                                                    
                                                    ⁢
                                                    
                                                      y
                                                      0
                                                    
                                                  
                                                  +
                                                  
                                                    
                                                      r
                                                      001
                                                    
                                                    ⁢
                                                    
                                                      x
                                                      0
                                                    
                                                    ⁢
                                                    
                                                      y
                                                      1
                                                    
                                                  
                                                  +
                                                  ...
                                                  +
                                                
                                                 
                                              
                                              ⁢
                                              
                                                r
                                                007
                                              
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              
                                                x
                                                0
                                              
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              
                                                y
                                                7
                                              
                                            
                                            +
                                            
                                              
                                            
                                            ⁢
                                            ...
                                            +
                                            
                                              
                                            
                                            ⁢
                                            
                                              
                                                r
                                                070
                                              
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              
                                                x
                                                7
                                              
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              
                                                y
                                                0
                                              
                                            
                                            +
                                            
                                              
                                                r
                                                071
                                              
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              
                                                x
                                                7
                                              
                                              ⁢
                                              
                                                
                                              
                                              ⁢
                                              
                                                y
                                                1
                                              
                                            
                                            +
                                            ...
                                            +
                                          
                                        
                                         
                                      
                                      ⁢
                                      
                                         
                                         
                                      
                                      ⁢
                                      
                                         
                                         
                                      
                                      ⁢
                                      
                                        r
                                        077
                                      
                                      ⁢
                                      
                                        
                                      
                                      ⁢
                                      
                                        x
                                        7
                                      
                                      ⁢
                                      
                                        
                                      
                                      ⁢
                                      
                                        y
                                        7
                                      
                                    
                                    ,
                                    
                                      
                                    
                                    ⁢
                                    
                                      
                                        ...
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        ...
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        ...
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        
                                          r
                                          700
                                        
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        
                                          x
                                          0
                                        
                                        ⁢
                                        
                                          y
                                          0
                                        
                                      
                                      +
                                      
                                        
                                          r
                                          701
                                        
                                        ⁢
                                        
                                          x
                                          0
                                        
                                        ⁢
                                        
                                          y
                                          1
                                        
                                      
                                      +
                                      ...
                                      +
                                      
                                        
                                          r
                                          707
                                        
                                        ⁢
                                        
                                          x
                                          0
                                        
                                        ⁢
                                        
                                          y
                                          7
                                        
                                      
                                      +
                                      ...
                                      +
                                      
                                        
                                          r
                                          770
                                        
                                        ⁢
                                        
                                          x
                                          7
                                        
                                        ⁢
                                        
                                          y
                                          0
                                        
                                      
                                      +
                                      
                                        
                                          r
                                          771
                                        
                                        ⁢
                                        
                                          x
                                          7
                                        
                                        ⁢
                                        
                                          y
                                          1
                                        
                                      
                                      +
                                      ...
                                      +
                                      
                                        
                                          r
                                          777
                                        
                                        ⁢
                                        
                                          x
                                          7
                                        
                                        ⁢
                                        
                                          y
                                          7
                                        
                                      
                                    
                                  
                                  )
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
          
            
              
            
          
        
      
    
    
      
        
      
    
  




In this case, transmitter 110 may be configured to encipher the message into the first ciphertext further based on the temporary secret decryption key corresponding to the transmitter. For example, transmitter 110 may encipher a message Uh=mh1+vhB (h=1, . . . , t) into the first ciphertext. That is, the first ciphertext may be a function of the public encryption key corresponding to transmitter 110, the temporary secret decryption key corresponding to transmitter 110, the variable X and the message to be enciphered. The first ciphertext may be calculated using an algorithm Enc(pkA, skR, (m, v)). As a result, the calculated first ciphertext may be represented as follows




  
    
      
        
          
            
              
                
              
              ⁢
              
                [
                
                  Formula
                  ⁢
                  
                    
                  
                  ⁢
                  5
                
                ]
              
            
            ⁢
            
              

            
            ⁢
            
              
                C
                ⁢
                
                  
                
                ⁢
                2
                ⁢
                
                  (
                  
                    
                      pk
                      A
                    
                    ,
                    
                      
                        sk
                        R
                      
                      ;
                      X
                    
                    ,
                    
                      (
                      
                        
                          m
                          h
                        
                        ,
                        
                          v
                          h
                        
                      
                      )
                    
                  
                  )
                
              
              =
            
          
           
        
        ⁢
        
          
            A
            k
          
          (
          
            
          
          ⁢
          
            ...
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  A
                  1
                
                (
                
                  
                    R
                    k
                  
                  (
                  
                    
                  
                  ⁢
                  
                    ...
                    (
                    
                      
                        R
                        1
                      
                      (
                      
                        
                          U
                          h
                        
                        (
                        
                          
                        
                        ⁢
                        
                          
                            
                              
                                
                                  R
                                  1
                                  
                                    -
                                    1
                                  
                                
                                (
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      ...
                                      ⁢
                                      
                                        
                                      
                                      ⁢
                                      
                                        (
                                        
                                          
                                            
                                              R
                                              k
                                              
                                                -
                                                1
                                              
                                            
                                            ⁡
                                            
                                              (
                                              
                                                
                                                  A
                                                  1
                                                  
                                                    -
                                                    1
                                                  
                                                
                                                (
                                                
                                                  
                                                
                                                ⁢
                                                
                                                  ...
                                                  ⁢
                                                  
                                                    
                                                  
                                                  ⁢
                                                  
                                                    (
                                                    
                                                      
                                                        A
                                                        k
                                                        
                                                          -
                                                          1
                                                        
                                                      
                                                      ⁢
                                                      X
                                                    
                                                    )
                                                  
                                                  ⁢
                                                  
                                                    
                                                  
                                                  ⁢
                                                  ...
                                                
                                                ⁢
                                                
                                                  
                                                
                                                )
                                              
                                              )
                                            
                                          
                                          ⁢
                                          
                                            
                                          
                                          ⁢
                                          ...
                                        
                                        ⁢
                                        
                                          
                                        
                                        )
                                      
                                    
                                    ∈
                                    
                                      
                                    
                                    ⁢
                                    
                                      O
                                      [
                                      
                                        
                                      
                                      ⁢
                                      X
                                      ]
                                    
                                  
                                  =
                                
                                 
                              
                              ⁢
                              
                                
                              
                              ⁢
                              
                                (
                                
                                  
                                    
                                      C
                                      
                                        h
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        00
                                      
                                    
                                    ⁢
                                    
                                      X
                                      0
                                    
                                  
                                  +
                                  
                                    
                                      C
                                      
                                        h
                                        ⁢
                                        01
                                      
                                    
                                    ⁢
                                    
                                      X
                                      1
                                    
                                  
                                  +
                                
                                 
                              
                              ⁢
                              ...
                            
                            +
                            
                              
                            
                            ⁢
                            
                              
                                C
                                
                                  h
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  07
                                
                              
                              ⁢
                              
                                X
                                7
                              
                            
                          
                          ,
                          
                            
                          
                          ⁢
                          
                            
                              ...
                              ⁢
                              
                                
                              
                              ⁢
                              ...
                              ⁢
                              
                                
                              
                              ⁢
                              ...
                              ⁢
                              
                                
                              
                              ⁢
                              
                                C
                                
                                  h
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  70
                                
                              
                              ⁢
                              
                                X
                                0
                              
                            
                            +
                            
                              
                                C
                                
                                  h
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  71
                                
                              
                              ⁢
                              
                                X
                                1
                              
                            
                            +
                            ...
                            +
                            
                              
                                C
                                
                                  h
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  77
                                
                              
                              ⁢
                              
                                X
                                7
                              
                            
                          
                        
                        )
                      
                    
                  
                
              
            
          
        
      
    
    
      
        
      
    
  




Transmitter 110 may be configured to send the first ciphertext to server 130, which may publish the first ciphertext. For example, transmitter 110 may transmit {chij} (h=1, . . . , t) (i.e., coefficients for the variable X in Formula 5) as the first ciphertext to server 130.
In some embodiments, transmitter 110 may be configured to transmit, to data processing device 140, a request to process the message by processing the first ciphertext, which corresponds to the message enciphered by transmitter 110, into a second ciphertext without deciphering the first ciphertext. For example, transmitter 110 may request a value of a ciphertext of m*=(m1+m2−m3)/(m2m3)εFq. Data processing device 140 may be configured to receive the request to process the message from transmitter 110, and receive, from server 130, the system parameter and the first ciphertext (e.g., C2(pkA,skR;X,(mh,vh))={chij} (h=1, 2, 3)) that corresponds to the message, based at least in part on the received request.
In some embodiments, data processing device 140 may be configured to process the first ciphertext into a second ciphertext by performing a computation (e.g., addition, multiplication, quadratic function, etc.) on the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext. For example, data processing device 140 may calculate the ciphertext C2(pkA,skR;X,(m*,v*)) of U*=(U1+U2−U3)/(U2U3)=m*1+v*B, where v*εFq is a random number, as follows.




  
    
      
        
          
            
              
                
                  
                    
                      
                        
                          
                        
                        ⁢
                        
                          
                            
                              C
                              ⁢
                              
                                
                              
                              ⁢
                              2
                              ⁢
                              
                                (
                                
                                  
                                    pk
                                    A
                                  
                                  ,
                                  
                                    
                                      sk
                                      R
                                    
                                    ;
                                    X
                                  
                                  ,
                                  
                                    (
                                    
                                      
                                        m
                                        1
                                      
                                      ,
                                      
                                        v
                                        1
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                            ←
                            
                              {
                              
                                c
                                
                                  1
                                  ⁢
                                  ij
                                
                              
                              }
                            
                          
                          ⁢
                          
                            

                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              C
                              ⁢
                              
                                
                              
                              ⁢
                              2
                              ⁢
                              
                                (
                                
                                  
                                    pk
                                    A
                                  
                                  ,
                                  
                                    
                                      sk
                                      R
                                    
                                    ;
                                    X
                                  
                                  ,
                                  
                                    (
                                    
                                      
                                        m
                                        2
                                      
                                      ,
                                      
                                        v
                                        2
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                            ←
                            
                              {
                              
                                c
                                
                                  2
                                  ⁢
                                  ij
                                
                              
                              }
                            
                          
                          ⁢
                          
                            

                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              C
                              ⁢
                              
                                
                              
                              ⁢
                              2
                              ⁢
                              
                                (
                                
                                  
                                    pk
                                    A
                                  
                                  ,
                                  
                                    
                                      sk
                                      R
                                    
                                    ;
                                    X
                                  
                                  ,
                                  
                                    (
                                    
                                      
                                        m
                                        3
                                      
                                      ,
                                      
                                        v
                                        3
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                            ←
                            
                              {
                              
                                c
                                
                                  3
                                  ⁢
                                  ij
                                
                              
                              }
                            
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            

                          
                          ⁢
                          
                            
                              C
                              ⁢
                              
                                
                              
                              ⁢
                              2
                              ⁢
                              
                                (
                                
                                  
                                    pk
                                    A
                                  
                                  ,
                                  
                                    
                                      sk
                                      R
                                    
                                    ;
                                    X
                                  
                                  ,
                                  
                                    (
                                    
                                      
                                        
                                          m
                                          1
                                        
                                        +
                                        
                                          m
                                          2
                                        
                                        -
                                        
                                          m
                                          3
                                        
                                      
                                      ,
                                      
                                        v
                                        123
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                            =
                            
                              
                                C
                                ⁢
                                
                                  
                                
                                ⁢
                                2
                                ⁢
                                
                                  (
                                  
                                    
                                      pk
                                      A
                                    
                                    ,
                                    
                                      
                                        sk
                                        R
                                      
                                      ;
                                      X
                                    
                                    ,
                                    
                                      (
                                      
                                        
                                          m
                                          1
                                        
                                        ,
                                        
                                          v
                                          1
                                        
                                      
                                      )
                                    
                                  
                                  )
                                
                              
                              +
                              
                                C
                                ⁢
                                
                                  
                                
                                ⁢
                                2
                                ⁢
                                
                                  (
                                  
                                    
                                      pk
                                      A
                                    
                                    ,
                                    
                                      
                                        sk
                                        R
                                      
                                      ;
                                      X
                                    
                                    ,
                                    
                                      (
                                      
                                        
                                          m
                                          2
                                        
                                        ,
                                        
                                          v
                                          2
                                        
                                      
                                      )
                                    
                                  
                                  )
                                
                              
                              -
                            
                          
                        
                        ⁢
                        
                          
                        
                         
                      
                      ⁢
                      C
                      ⁢
                      
                        
                      
                      ⁢
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        (
                        
                          
                            p
                            ⁢
                            
                              
                            
                            ⁢
                            
                              k
                              A
                            
                          
                          ,
                          
                            
                              sk
                              R
                            
                            ;
                            X
                          
                          ,
                          
                            (
                            
                              
                                m
                                3
                              
                              ,
                              
                                v
                                3
                              
                            
                            )
                          
                        
                        )
                      
                    
                     
                  
                  ⁢
                  
                    mod
                    ⁢
                    q
                  
                
                ⁢
                
                  
                
                ⁢
                
                  

                
                ⁢
                
                  C2
                  ⁢
                  
                    
                  
                  (
                  
                    
                      pk
                      A
                    
                    ,
                    
                      
                        sk
                        R
                      
                      ;
                      X
                    
                    ,
                    
                      (
                      
                        
                          
                            m
                            2
                          
                          ⁢
                          
                            m
                            3
                          
                        
                        ,
                        
                          v
                          23
                        
                      
                      )
                    
                  
                  )
                
              
              =
              
                 
                
                  C
                  ⁢
                  
                    
                  
                  ⁢
                  2
                  ⁢
                  
                    (
                    
                      
                        pk
                        A
                      
                      ,
                      
                        
                      
                      ⁢
                      
                        
                          sk
                          R
                        
                        ;
                        
                          (
                          
                            C
                            ⁢
                            
                              
                            
                            ⁢
                            2
                            ⁢
                            
                              (
                              
                                
                                  pk
                                  A
                                
                                ,
                                
                                  
                                    sk
                                    R
                                  
                                  ;
                                  X
                                
                                ,
                                
                                  (
                                  
                                    
                                      m
                                      3
                                    
                                    ,
                                    
                                      v
                                      3
                                    
                                  
                                  )
                                
                              
                              )
                            
                          
                          )
                        
                      
                      ,
                      
                        (
                        
                          
                            m
                            2
                          
                          ,
                          
                            v
                            2
                          
                        
                        )
                      
                    
                    )
                  
                  ⁢
                  
                    

                  
                  ⁢
                  
                    
                      C
                      ⁢
                      
                        
                      
                      ⁢
                      2
                      ⁢
                      
                        (
                        
                          
                            pk
                            A
                          
                          ,
                          
                            
                              sk
                              R
                            
                            ;
                            X
                          
                          ,
                          
                            (
                            
                              
                                m
                                *
                              
                              ,
                              
                                v
                                *
                              
                            
                            )
                          
                        
                        )
                      
                    
                    =
                    
                      
                        C
                        ⁢
                        
                          
                        
                        ⁢
                        2
                        ⁢
                        
                          (
                          
                            
                              pk
                              A
                            
                            ,
                            
                              
                                sk
                                R
                              
                              ;
                              X
                            
                            ,
                            
                              (
                              
                                
                                  
                                    (
                                    
                                      
                                        m
                                        1
                                      
                                      +
                                      
                                        m
                                        2
                                      
                                      -
                                      
                                        m
                                        3
                                      
                                    
                                    )
                                  
                                  ⁢
                                  
                                    
                                      (
                                      
                                        
                                          m
                                          2
                                        
                                        ⁢
                                        
                                          m
                                          3
                                        
                                      
                                      )
                                    
                                    
                                      -
                                      1
                                    
                                  
                                
                                ,
                                
                                  v
                                  *
                                
                              
                              )
                            
                          
                          )
                        
                      
                      =
                    
                  
                
                 
              
            
             
          
          ⁢
          
            

          
          ⁢
          
            
              
                C
                ⁢
                
                  
                
                ⁢
                2
                ⁢
                
                  
                
                ⁢
                
                  (
                  
                    
                      p
                      ⁢
                      
                        
                      
                      ⁢
                      
                        k
                        A
                      
                    
                    ,
                    
                      
                    
                    ⁢
                    
                      
                        sk
                        R
                      
                      ;
                      
                        
                      
                      ⁢
                      
                        (
                        
                          C
                          ⁢
                          
                            
                          
                          ⁢
                          2
                          ⁢
                          
                            (
                            
                              
                                pk
                                A
                              
                              ,
                              
                                
                                  sk
                                  R
                                
                                ;
                                X
                              
                              ,
                              
                                (
                                
                                  
                                    
                                      (
                                      
                                        
                                          m
                                          2
                                        
                                        ⁢
                                        
                                          m
                                          3
                                        
                                      
                                      )
                                    
                                    
                                      -
                                      1
                                    
                                  
                                  ,
                                  
                                    v
                                    
                                      23
                                      ⁢
                                      inv
                                    
                                  
                                
                                )
                              
                            
                            )
                          
                        
                        )
                      
                    
                    ,
                    
                      
                    
                    ⁢
                    
                      (
                      
                        
                          
                            m
                            1
                          
                          +
                          
                            m
                            2
                          
                          -
                          
                            m
                            3
                          
                        
                        ,
                        
                          
                        
                        ⁢
                        
                          v
                          123
                        
                      
                      )
                    
                  
                  )
                
              
              =
              
                
                  (
                  
                    
                      
                        c
                        00
                        *
                      
                      ⁢
                      
                        x
                        0
                      
                    
                    +
                    
                      
                        c
                        01
                        *
                      
                      ⁢
                      
                        x
                        1
                      
                    
                    +
                    ...
                  
                   
                
                +
                
                  
                    c
                    07
                    *
                  
                  ⁢
                  
                    x
                    7
                  
                
              
            
            ,
            
              
            
            ⁢
            
              
                ...
                ⁢
                
                  
                
                ⁢
                ...
                ⁢
                
                  
                
                ⁢
                ...
                ⁢
                
                  
                
                ⁢
                
                  c
                  70
                  *
                
                ⁢
                
                  x
                  0
                
              
              +
              
                
                  c
                  71
                  *
                
                ⁢
                
                  x
                  1
                
              
              +
              ...
              +
              
                
                  c
                  77
                  *
                
                ⁢
                
                  x
                  7
                
              
            
          
        
        )
      
    
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          6
        
        ]
      
    
  




Also, data processing device 140 may send the calculated ciphertext (e.g., {c*ij} that are coefficients for the variable X in Formula 6 as the ciphertext) to transmitter 110 via a connection that may or may not be secure. Transmitter 110 may be configured to receive the ciphertext.
Transmitter 110 may be further configured to decipher the second ciphertext, based at least in part on the system parameter, the first public encryption key and the temporary secret decryption key corresponding to transmitter 110. For example, transmitter 110 may decipher {c*ij} to obtain U*=(U1+U2−U3)(U2U3)−1 as follows.

Dec(skA,B,pkZ;X,C2(pkA,skR;X,(U1+U2−U3)(U2U3)−1))=(U1+U2−U3)(U2U3)−1 mod q=U*=m*1+v*B=(u*0, . . . ,u*7)  [Formula 7]

Also, transmitter 110 may obtain
m*=(m1+m2−m3)(m2m3)−1 mod q as follows.

v*=u*1/b1 mod q, 

m*=u*0−v*b0=u*0−(u*1/b1)b0 mod q.  [Formula 8]

In the manner as described above, transmitter 110 may be configured to obtain a deciphered process result that may be equal to a result of the requested computations or calculations on the requested message. Thus, based on the homomorphic public key encryption scheme on non-associative octonion ring over finite field, transmitter 110 may be configured to obtain a calculation result of encrypted messages without revealing original messages to data processing device 140, and may be configured to obtain a calculation result of the original messages by deciphering the calculation result of encrypted messages.
FIG. 2 shows a block diagram illustrating an example transmitter, arranged in accordance with at least some embodiments described herein. As depicted in FIG. 2, for example, transmitter 110 may include a key manager 210, an encipherer 220, a receiving unit 230 and a transmitting unit 240. Although illustrated as discrete components, various components may be divided into additional components, combined into fewer components, or eliminated altogether while being contemplated within the scope of the disclosed subject matter. It will be understood by those skilled in the art that each function and/or operation of the components may be implemented, individually and/or collectively, by a wide range of hardware, software, firmware, or virtually any combination thereof. In that regard, one or more of key manager 210, encipherer 220, receiving unit 230 and transmitting unit 240 may be included in an instance of an application hosted by transmitter 110.
In some embodiments, key manager 210 may be configured to select a secret decryption key of transmitter 110 from an arbitrary element of the octonion ring “O” and to generate a first public encryption key for transmitter 110, based at least in part on the secret decryption key corresponding to transmitter 110 and a system parameter. The system parameter may be received from server 130. The system parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q. Further, encipherer 220 may be configured to encipher a message into a first ciphertext, based at least in part on the public encryption key corresponding to receiver 120 and the secret decryption key corresponding to transmitter 110.
In some embodiments, key manager 210 may be further configured to select a temporary secret decryption key for transmitter 110 from an arbitrary element of the octonion ring “O”, generate a temporary public encryption key for transmitter 110, based at least in part on the temporary secret decryption key corresponding to transmitter 110 and the system parameter, and generate a second public encryption key for transmitter 110, based at least in part on the first public encryption key and the temporary secret decryption key corresponding to transmitter 110 and the system parameter. In this case, encipherer 220 may be configured to encipher the message into the first ciphertext further based on the temporary secret decryption key corresponding to transmitter 110. Transmitting unit 240 may be configured to transmit the first ciphertext to server 130.
In some embodiments, receiving unit 230 may be configured to receive, from server 130, the system parameter and the public encryption key of receiver 120.
Transmitting unit 240 may be configured to transmit, to data processing device 140, a request to process the message by processing the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext. Transmitting unit 240 may be further configured to transmit, to server 130, the public encryption key of transmitter 110 such that server 130 publishes the public encryption key corresponding to transmitter 110.
Transmitting unit 240 may be further configured to transmit, to server 130, the public encryption key of transmitter 110 such that server 130 publishes the public encryption key corresponding to transmitter 110. In this case, transmitter 110 may further include an decipherer 250 configured to decipher the second ciphertext, based at least in part on the system parameter, the first public encryption key and the temporary secret decryption key corresponding to transmitter 110, the deciphering of the second ciphertext including obtaining the processed message.
FIG. 3 shows a schematic block diagram illustrating an example receiver, arranged in accordance with at least some embodiments described herein. Receiver 120 may include a receiving unit 310, a key manager 320 and a decipherer 330. Although illustrated as discrete components, various components may be divided into additional components, combined into fewer components, or eliminated altogether while being contemplated within the scope of the disclosed subject matter. It will be understood by those skilled in the art that each function and/or operation of the components may be implemented, individually and/or collectively, by a wide range of hardware, software, firmware, or virtually any combination thereof. In that regard, one or more of receiving unit 310, key manager 320 and decipherer 330 may be included in an instance of an application hosted by receiver 120.
In some embodiments, receiving unit 310 may be configured to receive, from server 130, a system parameter and a public encryption key corresponding to transmitter 110. The system parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q. Further, receiving unit 310 may be configured to receive, from transmitter 110, a first ciphertext.
In some embodiments, key manager 320 may be configured to select a secret decryption key of receiver 120 and generate a public encryption key for receiver 120, based at least in part on the secret decryption key of receiver 120 and the system parameter.
Decipherer 330 may be configured to decipher the first ciphertext based at least in part on the secret decryption key of receiver 120, the system parameter and the public encryption key corresponding to transmitter 110.
FIG. 4 shows a schematic block diagram illustrating an example data processing device, arranged in accordance with at least some embodiments described herein. As depicted in FIG. 4, for example, data processing device 140 may include a receiving unit 410, a processor 420 and a transmitting unit 430. Although illustrated as discrete components, various components may be divided into additional components, combined into fewer components, or eliminated altogether while being contemplated within the scope of the disclosed subject matter. It will be understood by those skilled in the art that each function and/or operation of the components may be implemented, individually and/or collectively, by a wide range of hardware, software, firmware, or virtually any combination thereof. In that regard, one or more of receiving unit 410, processor 420 and transmitting unit 430 may be included in an instance of an application hosted by data processing device 140.
In some embodiments, receiving unit 410 may be configured to receive, from transmitter 110, a request to process a message. Receiving unit 410 may be further configured to receive, from server 130, a system parameter and a first ciphertext that corresponds to the message, based at least in part on the received request.
Processor 420 may be configured to process the first ciphertext into a second ciphertext by calculating the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext. Transmitting unit 430 may be configured to transmit, to transmitter 110, the second ciphertext.
In some embodiments, the message may be enciphered to the first ciphertext by transmitter 110, based at least in part on a public encryption key and a secret decryption key corresponding to transmitter 110.
FIG. 5 schematically shows an illustrative example of a homomorphic signature system 500, arranged in accordance with at least some embodiments described herein. As illustrated in FIG. 5, homomorphic signature system 500 may include a server 510, an endorser 520 and an authenticator 530, which may be connected to each other via a network. The network may refer to a component or module that may be configured to communicatively couple two or more of server 510, endorser 520 and authenticator 530. Non-limiting examples of the network may include a wired network such as a LAN (Local Area Network), a WAN (Wide Area Network), a VAN (Value Added Network) or the like, or various other wireless networks such as a mobile radio communication network including at least one of a 3G mobile telecommunications network, a 4th or 5th generation mobile telecommunications network, various other mobile telecommunications networks, a satellite network, WiBro, Mobile WiMAX, HSDPA, or the like. Alternatively, the network may include at least one of an NFC, Bluetooth, or P2P communication protocol.
For example, but not as a limitation, respective one of endorser 520 and authenticator 530 may refer to at least one of a smart phone, a portable device, a notebook computer, a tablet device, a phablet device, a personal computer or a personal communication terminal, such as PCS (Personal Communication System), GMS (Global System for Mobile communications), PDC (Personal Digital Cellular), PDA (Personal Digital Assistant). Endorser 520 and authenticator 530 may be capable of full duplex radio communications. Further, for example, server 510 may include a cloud datacenter.
In some embodiments, endorser 520 may be configured to receive, from server 510, a signing parameter. The signing parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring (e.g., represented by “O”) over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q, or an element C in the octonion ring such that C=1−B mod q. Let X=(x0, . . . , x7)εO[X] be a variable, and Y=(y0, . . . , y7)εO[Y] be another variable, which are selected from the octonion ring “O.”
In some embodiments, endorser 520 may be further configured to select a secret key corresponding to endorser 520, and generate a public signing key for endorser 520, based at least in part on the secret key corresponding to endorser 520 and the signing parameter. Further, endorser 520 may be configured to calculate a signature corresponding to a message, based at least in part on the public signing key corresponding to endorser 520 and the signing parameter. Endorser 520 may be further configured to transmit, to server 510, the signature and the public signing key.
For example, endorser 520 may select a secret key A:=(A1, . . . , Ak)εOk such that the inverse Ai−1 (i=1, . . . , k) exists, where k is an integer. Let A−1:=(A1−1, . . . , Ak−1)εOk. For example, if |A|2≠0 mod q for octonion A=(a0, a1, . . . , a7), the inverse of A can be calculated by A−1=(a0S−1 mod q, −a1S−1 mod q, . . . , −a7S−1 mod q) where S=a02+a12+ . . . +a72 mod q. Further, the public signing key A(X,Y) may be generated using the variable X and Y and the secret key A and its inverse, as follows.




  
    
      
        
          A
          ⁡
          
            (
            
              X
              ,
              Y
            
            )
          
        
        =
        
          
            A
            k
          
          (
          
            
          
          ⁢
          
            ...
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  
                    A
                    1
                  
                  (
                  
                    
                      
                        Y
                        (
                        
                          
                            
                              
                                
                                  A
                                  k
                                  
                                    -
                                    1
                                  
                                
                                (
                                
                                  
                                
                                ⁢
                                
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    (
                                    
                                      
                                        A
                                        1
                                        
                                          -
                                          1
                                        
                                      
                                      ⁢
                                      X
                                    
                                    )
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  ...
                                
                                ⁢
                                
                                  
                                
                                )
                              
                              ⁢
                              
                                
                              
                              ⁢
                              mod
                              ⁢
                              
                                
                              
                              ⁢
                              q
                            
                            ∈
                            
                              O
                              ⁡
                              
                                [
                                
                                  X
                                  ,
                                  
                                    
                                  
                                  ⁢
                                  Y
                                
                                ]
                              
                            
                          
                          =
                          
                            
                               
                               
                            
                            ⁢
                            
                              (
                              
                                
                                  
                                    a
                                    000
                                  
                                  ⁢
                                  
                                    x
                                    0
                                  
                                  ⁢
                                  
                                    y
                                    0
                                  
                                
                                +
                                
                                  
                                    a
                                    0001
                                  
                                  ⁢
                                  
                                    x
                                    0
                                  
                                  ⁢
                                  
                                    y
                                    1
                                  
                                
                                +
                                ...
                                +
                                
                                  
                                
                                ⁢
                                
                                  
                                    a
                                    007
                                  
                                  ⁢
                                  
                                    x
                                    0
                                  
                                  ⁢
                                  
                                    y
                                    7
                                  
                                
                                +
                                
                                  
                                
                                ⁢
                                ...
                                +
                                
                                  
                                    a
                                    070
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    x
                                    7
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    y
                                    0
                                  
                                
                                +
                                
                                  
                                
                                ⁢
                                
                                   
                                  
                                    
                                      a
                                      071
                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      x
                                      7
                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      y
                                      1
                                    
                                  
                                   
                                
                                +
                                
                                  
                                
                                ⁢
                                ...
                              
                               
                            
                            ⁢
                            
                              
                            
                            ⁢
                            
                               
                              
                                 
                                
                                  
                                
                                +
                                
                                  
                                
                                 
                              
                               
                            
                          
                        
                         
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        a
                        077
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        7
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        y
                        7
                      
                    
                    ,
                  
                   
                
                ⁢
                
                  
                
                ⁢
                
                   
                  
                     
                    
                      
                        ...
                        ⁢
                        
                          
                        
                        ⁢
                        ...
                        ⁢
                        
                          
                        
                        ⁢
                        ...
                        ⁢
                        
                          
                        
                        ⁢
                        
                          a
                          700
                        
                        ⁢
                        
                          x
                          0
                        
                        ⁢
                        
                          y
                          0
                        
                      
                      +
                      
                        
                           
                           
                        
                        ⁢
                        
                          a
                          701
                        
                        ⁢
                        
                          x
                          0
                        
                        ⁢
                        
                          y
                          1
                        
                      
                      +
                      ...
                      +
                      
                        
                      
                      ⁢
                      
                        
                          a
                          707
                        
                        ⁢
                        
                          x
                          0
                        
                        ⁢
                        
                          y
                          7
                        
                      
                      +
                      ...
                      +
                      
                        
                          a
                          770
                        
                        ⁢
                        
                          x
                          7
                        
                        ⁢
                        
                          y
                          0
                        
                      
                      +
                      
                        
                          a
                          771
                        
                        ⁢
                        
                          x
                          7
                        
                        ⁢
                        
                          y
                          1
                        
                      
                      +
                      
                        
                      
                      ⁢
                      ...
                      +
                      
                        
                          a
                          777
                        
                        ⁢
                        
                          x
                          7
                        
                        ⁢
                        
                          y
                          7
                        
                      
                    
                    )
                  
                
              
            
          
        
      
    
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          9
        
        ]
      
    
  




Let mhεFq* (h=1, . . . , n) be messages which endorser 520 may store in its database. Also, let vhεFq* (h=1, . . . , n) be random numbers selected by endorser 520. Let Uh=(uh0, . . . , uh7):=mhB+vhCεO (h=1, . . . , n) be a medium message and (mh,vh):=mhB+vhCεO (h=1, . . . , n). Endorser 520 may be configured to calculate σ(X)=(σ1(X), . . . , σn(X))εO[X]n where σi(X):=Ak( . . . (A1(Ui(A1−1( . . . (Ak−1(X) . . . )) . . . )mod qεO[X], (i=1, . . . , n). σh(X) indicates a signature corresponding to the medium message Uh=mhB+vhC, (h=1, . . . , n). Also, σh(X) may be represented as follows.




  
    
      
        
          
            σ
            h
          
          ⁡
          
            (
            X
            )
          
        
        =
        
          (
          
            
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    00
                  
                
                ⁢
                
                  x
                  0
                
              
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    01
                  
                
                ⁢
                
                  x
                  1
                
              
              ⁢
              
                
              
              +
              ...
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    07
                  
                
                ⁢
                
                  x
                  7
                
              
            
            ,
            
              
                ...
                ⁢
                
                  
                
                ⁢
                ...
                ⁢
                
                  
                
                ⁢
                ...
                ⁢
                
                  
                
                ⁢
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    70
                  
                
                ⁢
                
                  x
                  0
                
              
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    71
                  
                
                ⁢
                
                  x
                  1
                
              
              +
              ...
              +
              
                
                  C
                  
                    h
                    ⁢
                    
                      
                    
                    ⁢
                    77
                  
                
                ⁢
                
                  x
                  7
                
              
            
          
          )
        
      
    
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          10
        
        ]
      
    
  




Accordingly, the signature may be represented by σh(X)={chij}εFq8×8 (h=1, . . . , n). Also, let σ(X)=(σ1(X), . . . , σn(X))εO[X]n, m:=(m1, . . . , mn)εFqon, v:=(v1, . . . , vn)εFqon, and η:=Ak( . . . (A1C) . . . )mod qεO. Endorser 520 may be configured to send (σ(X), q, η, v) to server 510 as the signed data of endorser 520 via a connection that may or may not be secure. Server 510 may receive (σ(X), q, η, v) from endorser 520 and store the received (σ(X), q, η, v) as the signed data of endorser 520.
In some embodiments, endorser 520 may be further configured to transmit, to authenticator 530, a request to evaluate the signature. Authenticator 530 may be configured to evaluate the signature to be converted to a derived signature based at least in part on the request. For example, authenticator 530 may be an entity or computing device which performs data-processing (e.g., evaluation of the signature) requested by endorser 520. Authenticator 530 may be requested to compute <f>={eji} by using the signed data of endorser 520 such that f((σ(X)))=f(σ1(X), . . . , σn(X))=Ak( . . . (A1(g(U)(A1−1( . . . (Ak−1X) . . . )) . . . )mod qεO[X] where fεF:O[X]n→O[X]. In this case, authenticator 530 may compute f((σ(X)) by using an algorithm Evaluate(σ(X); f) for a part of the signed data of endorser 520 ((σ(X),q)) such that σ′(X):=f((σ(X))←Evaluate(σ(X); f).
In some embodiments, endorser 520 may be further configured to receive, from authenticator 530, the derived signature and receive, from the server, the public signing key. In this case, endorser 520 may verify the derived signature based at least in part on the public signing key to determine whether authenticator 530 correctly evaluates the signature.
For example, endorser 520 may receive [<f>, f(σ(X))] from authenticator 530 and receive (q, η, v) from server 510 where (η, v) is a public verification key of endorser 520. Endorser 520 may verify that authenticator 530 correctly applied f to the data set of endorser 520 by using an algorithm Verify(pk; σ′(X); g)=1 or 0. For example, in case that U=(U1,U2,U3), endorser 520 may retrieve f′(m1,m2,m3) by using sk=((A1, . . . , Ak)εOk, BεO, CεO) as follows.



  
    
      
    
    ⁢
    
      [
      
        Formula
        ⁢
        
          
        
        ⁢
        11
      
      ]
    
  




  
    
      A
      1
      
        -
        1
      
    
    (
    
      
    
    ⁢
    
      
        ...
        ⁢
        
          
        
        ⁢
        
          (
          
            
              
                A
                k
                
                  -
                  1
                
              
              ⁡
              
                (
                
                  
                    σ
                    ′
                  
                  ⁡
                  
                    (
                    α
                    )
                  
                
                )
              
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          )
        
      
      =
      
        
           
          
             
             
          
           
        
        ⁢
        
          
            A
            1
            
              -
              1
            
          
          (
          
            
          
          ⁢
          
            ...
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  A
                  k
                  
                    -
                    1
                  
                
                (
                
                  
                    (
                    
                      
                        
                          
                            A
                            k
                          
                          (
                          
                            
                          
                          ⁢
                          
                            ...
                            ⁢
                            
                              
                            
                            ⁢
                            
                              (
                              
                                
                                  
                                    A
                                    1
                                  
                                  (
                                  
                                    
                                      g
                                      ⁡
                                      
                                        (
                                        U
                                        )
                                      
                                    
                                    ⁢
                                    
                                       
                                       
                                    
                                    ⁢
                                    
                                      (
                                      
                                        
                                          A
                                          1
                                          
                                            -
                                            1
                                          
                                        
                                        (
                                        
                                          
                                        
                                        ⁢
                                        
                                          ...
                                          ⁢
                                          
                                            
                                          
                                          ⁢
                                          
                                            (
                                            
                                              
                                                A
                                                k
                                                
                                                  -
                                                  1
                                                
                                              
                                              ⁢
                                              α
                                            
                                            )
                                          
                                          ⁢
                                          
                                            
                                          
                                          ⁢
                                          ...
                                        
                                        ⁢
                                        
                                          
                                        
                                        )
                                      
                                      )
                                    
                                  
                                  ⁢
                                  
                                    
                                  
                                   
                                
                                ⁢
                                
                                  
                                
                                ⁢
                                ...
                              
                              ⁢
                              
                                
                              
                              )
                            
                            ⁢
                            
                               
                              
                                
                              
                              ⁢
                              
                                
                                  mod
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  q
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  where
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  α
                                
                                :=
                              
                               
                            
                            ⁢
                            
                               
                               
                            
                          
                           
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                           
                           
                        
                        ⁢
                        
                          
                            A
                            k
                          
                          (
                          
                            
                          
                          ⁢
                          
                            ...
                            ⁢
                            
                              
                            
                            ⁢
                            
                              (
                              
                                
                                  A
                                  1
                                
                                ⁢
                                B
                              
                              )
                            
                            ⁢
                            
                              
                            
                            ⁢
                            ...
                          
                          ⁢
                          
                            
                          
                          )
                        
                        ⁢
                        
                          
                        
                        ⁢
                        mod
                        ⁢
                        
                          
                        
                        ⁢
                        q
                      
                      ,
                      =
                    
                    ⁢
                    
                      
                    
                     
                  
                  ⁢
                  
                     
                    
                      
                        
                          g
                          (
                          
                            
                          
                          ⁢
                          U
                          )
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            (
                            
                              
                                
                                  A
                                  1
                                  
                                    -
                                    1
                                  
                                
                                (
                                
                                  
                                
                                ⁢
                                
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    (
                                    
                                      
                                        
                                          
                                            A
                                            k
                                            
                                              -
                                              1
                                            
                                          
                                          (
                                          
                                            
                                              
                                                A
                                                k
                                              
                                              (
                                              
                                                
                                              
                                              ⁢
                                              
                                                ...
                                                ⁢
                                                
                                                  
                                                
                                                ⁢
                                                
                                                  (
                                                  
                                                    
                                                      A
                                                      1
                                                    
                                                    ⁢
                                                    B
                                                  
                                                  )
                                                
                                                ⁢
                                                
                                                  
                                                
                                                ⁢
                                                ...
                                              
                                              ⁢
                                              
                                                
                                              
                                              )
                                            
                                            ⁢
                                            
                                              
                                            
                                            ⁢
                                            ...
                                          
                                          ⁢
                                          
                                            
                                          
                                          )
                                        
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        mod
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        q
                                      
                                      =
                                    
                                    ⁢
                                    
                                      
                                    
                                     
                                  
                                
                                 
                              
                              ⁢
                              
                                 
                                
                                  
                                    
                                      g
                                      (
                                      
                                        
                                      
                                      ⁢
                                      U
                                      )
                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    B
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    mod
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    q
                                  
                                  =
                                
                                 
                              
                              ⁢
                              
                                 
                                 
                              
                            
                             
                          
                          [
                          
                            
                          
                          ⁢
                          
                            
                              g
                              (
                              
                                
                              
                              ⁢
                              
                                
                                  
                                    m
                                    1
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  B
                                
                                ,
                                
                                  
                                
                                ⁢
                                ...
                                ⁢
                                
                                  
                                
                                ,
                                
                                  
                                
                                ⁢
                                
                                  
                                    m
                                    n
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  B
                                
                              
                              ⁢
                              
                                
                              
                              )
                            
                            ⁢
                            
                              
                            
                            +
                            
                              
                                 
                                 
                              
                              ⁢
                              
                                
                              
                              ⁢
                              
                                g
                                ⁢
                                
                                  
                                
                                (
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      v
                                      1
                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    C
                                  
                                  ⁢
                                  
                                    
                                  
                                  ,
                                  
                                    
                                  
                                  ⁢
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ,
                                  
                                    
                                  
                                  ⁢
                                  
                                    
                                      v
                                      n
                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    C
                                  
                                
                                )
                              
                            
                          
                          ]
                        
                        ⁢
                        
                          
                        
                        ⁢
                        B
                        ⁢
                        
                          
                        
                        ⁢
                        mod
                        ⁢
                        
                          
                        
                        ⁢
                        q
                      
                      =
                      
                        
                          [
                          
                            
                              
                                g
                                ⁡
                                
                                  (
                                  
                                    
                                      
                                        m
                                        1
                                      
                                      ⁢
                                      1
                                    
                                    ,
                                    
                                      
                                        m
                                        2
                                      
                                      ⁢
                                      1
                                    
                                    ,
                                    
                                      
                                        m
                                        3
                                      
                                      ⁢
                                      1
                                    
                                  
                                  )
                                
                              
                              ⁢
                              B
                            
                            +
                          
                           
                        
                        ⁢
                        
                           
                          
                            
                              
                                 
                                
                                  
                                    g
                                    ⁡
                                    
                                      (
                                      
                                        
                                          
                                            v
                                            1
                                          
                                          ⁢
                                          1
                                        
                                        ,
                                        ...
                                        ⁢
                                        
                                          
                                        
                                        ,
                                        
                                          
                                            v
                                            n
                                          
                                          ⁢
                                          1
                                        
                                      
                                      )
                                    
                                  
                                  ⁢
                                  C
                                
                                ]
                              
                              ⁢
                              
                                
                              
                              ⁢
                              B
                              ⁢
                              
                                
                              
                              ⁢
                              
                                mod
                                ⁢
                                q
                              
                            
                            =
                            
                              
                                
                                  g
                                  ⁡
                                  
                                    (
                                    
                                      
                                        
                                          m
                                          1
                                        
                                        ⁢
                                        1
                                      
                                      ,
                                      
                                        
                                          m
                                          2
                                        
                                        ⁢
                                        1
                                      
                                      ,
                                      
                                        
                                          m
                                          3
                                        
                                        ⁢
                                        1
                                      
                                    
                                    )
                                  
                                
                                ⁢
                                
                                  B
                                  2
                                
                                ⁢
                                
                                  mod
                                  ⁢
                                  q
                                
                              
                              =
                              
                                
                                  
                                    
                                      f
                                      ′
                                    
                                    ⁡
                                    
                                      (
                                      
                                        
                                          m
                                          1
                                        
                                        ,
                                        
                                          m
                                          2
                                        
                                        ,
                                        
                                          m
                                          3
                                        
                                      
                                      )
                                    
                                  
                                  ⁢
                                  1
                                  ⁢
                                  
                                    B
                                    ⁢
                                    mod
                                    ⁢
                                    q
                                  
                                
                                =
                                
                                  
                                    
                                      
                                        f
                                        ′
                                      
                                      ⁡
                                      
                                        (
                                        
                                          
                                            m
                                            1
                                          
                                          ,
                                          
                                            m
                                            2
                                          
                                          ,
                                          
                                            m
                                            3
                                          
                                        
                                        )
                                      
                                    
                                    ⁢
                                    
                                      
                                        B
                                        ⁢
                                        mod
                                        ⁢
                                        q
                                      
                                      .
                                      
                                        

                                      
                                      ⁢
                                      
                                        
                                      
                                      ⁢
                                      Then
                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    we
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    have
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      
                                        f
                                        ′
                                      
                                      (
                                      
                                        
                                          m
                                          1
                                        
                                        ,
                                        
                                          m
                                          2
                                        
                                        ,
                                        
                                          m
                                          3
                                        
                                      
                                      )
                                    
                                  
                                  =
                                  
                                    
                                      2
                                      ⁡
                                      
                                        [
                                        
                                          
                                            
                                              f
                                              ′
                                            
                                            ⁡
                                            
                                              (
                                              
                                                
                                                  m
                                                  1
                                                
                                                ,
                                                
                                                  m
                                                  2
                                                
                                                ,
                                                
                                                  m
                                                  3
                                                
                                              
                                              )
                                            
                                          
                                          ⁢
                                          B
                                        
                                        ]
                                      
                                    
                                    
                                      o
                                      ,
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
  



FIG. 6 shows a schematic block diagram illustrating an example endorser 520, arranged in accordance with at least some embodiments described herein. As depicted in FIG. 6, for example, endorser 520 may include a receiving unit 610, a key manager 620, a transmitting unit 630 and a signature generator 640. Although illustrated as discrete components, various components may be divided into additional components, combined into fewer components, or eliminated altogether while being contemplated within the scope of the disclosed subject matter. It will be understood by those skilled in the art that each function and/or operation of the components may be implemented, individually and/or collectively, by a wide range of hardware, software, firmware, or virtually any combination thereof. In that regard, one or more of receiving unit 610, key manager 620, transmitting unit 630 and signature generator 640 may be included in an instance of an application hosted by endorser 520.
In some embodiments, receiving unit 610 may be configured to receive, from server 510, a signing parameter. For example, the signing parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q, or an element C in the octonion ring such that C=1−B mod q.
In some embodiments, key manager 620 may be configured to select a secret key corresponding to endorser 520, and generate a public signing key for endorser 520, based at least in part on the secret key corresponding to endorser 520 and the signing parameter. Further, signature generator 640 may be configured to calculate a signature corresponding to a message, based at least in part on the public signing key corresponding to endorser 520 and the signing parameter.
In some embodiments, transmitting unit 630 may be configured to transmit, to server 510, the signature and the public signing key. Transmitting unit 630 may be further configured to transmit, to authenticator 530, a request to evaluate the signature. In this case, authenticator 530 may be configured to evaluate the signature to be converted to a derived signature based at least in part on the request. Receiving unit 610 may be further configured to receive, from authenticator 530, the derived signature and receive, from server 510, the public signing key. In this case, endorser 520 may further include a verifier (not shown) configured to verify the derived signature based at least in part on the public signing key to determine whether authenticator 530 correctly evaluates the signature.
FIG. 7 schematically shows an example flow diagram of a process 700 of a transmitter to implement a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein. The operations of process 700 may be implemented by system 100 including transmitter 110, receiver 120, server 130 and/or data processing device 140, as illustrated in FIGS. 1 to 4. Process 700 may include one or more operations, actions, or functions as illustrated by one or more blocks 710, 720, 730, 740, 750 and/or 760. Although illustrated as discrete blocks, various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation. Processing may begin at block 710.
At block 710 (Receive, From a Server, a System Parameter), transmitter 110 may receive, from server 130, a system parameter. The system parameter may be represented at least in part in a non-associative octonion ring, and may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q. Processing may proceed from block 710 to block 720.
At block 720 (Select a Secret Decryption Key Corresponding To the Transmitter), transmitter 110 may select a secret decryption key corresponding to transmitter 110, which may be represented in a non-associative octonion ring. In some embodiments, the secret decryption key of transmitter 110 may be selected such that an inverse of the secret decryption key exists. Processing may proceed from block 720 to block 730.
At block 730 (Generate a First Public Encryption Key For The Transmitter), transmitter 110 may generate a first public encryption key for transmitter 110, based at least in part on the secret decryption key corresponding to transmitter 110 and the system parameter. For example, the first public encryption key may be represented in a non-associative octonion ring. In some embodiments, transmitter 110 may transmit, to server 130, the public encryption key of transmitter 110 such that server 130 publishes the public encryption key of transmitter 110. Processing may proceed from block 730 to block 740.
At block 740 (Receive, From the Server, a Public Encryption Key Corresponding To a Receiver), transmitter 110 may receive, from server 130, a public encryption key corresponding to receiver 120. For example, the public encryption key corresponding to receiver 120 may be represented in a non-associative octonion ring. Processing may proceed from block 740 to block 750.
At block 750 (Encipher a Message Into a First Ciphertext), transmitter 110 may encipher a message into a first ciphertext, based at least in part on the public encryption key corresponding to receiver 120 and the secret decryption key corresponding to transmitter 110. For example, the message or the first ciphertext may be represented in a non-associative octonion ring. In some embodiments, transmitter 110 may select a temporary secret decryption key corresponding to transmitter 110, and generate a temporary public encryption key of transmitter 110, based at least in part on the temporary secret decryption key corresponding to transmitter 110 and the system parameter. Further, transmitter 110 may generate a second public encryption key for transmitter 110, based at least in part on the first public encryption key and the temporary secret decryption key corresponding to transmitter 110 and the system parameter. In this case, the enciphering may be further based on the temporary secret decryption key corresponding to transmitter 110. In some other embodiments, transmitter 110 may generate a public encryption key for transmitter 110 and for receiver 120, based at least in part on a public encryption key corresponding to receiver 120, the secret decryption key corresponding to transmitter 110 and the system parameter. Further, transmitter 110 may transmit, to server 130, the first ciphertext. In this case, the enciphering may be further based on the secret decryption key corresponding to transmitter 110. Processing may proceed from block 750 to block 760.
At block 760 (Transmit, To a Data Processing Device, a Request To Process the Message), transmitter 110 may transmit, to data processing device 140, a request to process the message by processing the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext. For example, the second ciphertext may be represented at least in part in a non-associative octonion ring. In some embodiments, transmitter 110 may receive, from data processing device 140, the second ciphertext, and decipher the second ciphertext, based at least in part on the system parameter, the first public encryption key and the temporary secret decryption key corresponding to transmitter 110. In this case, the deciphering of the second ciphertext may include obtaining the processed message.
FIG. 8 schematically shows an example flow diagram of a process 800 of a receiver to implement a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein. The operations of process 800 may be implemented by system 100 including transmitter 110, receiver 120, server 130 and/or data processing device 140, as illustrated in FIGS. 1 to 4. Process 800 may include one or more operations, actions, or functions as illustrated by one or more blocks 810, 820, 830, 840, 850 and/or 860. Although illustrated as discrete blocks, various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation. Processing may begin at block 810.
At block 810 (Receive, From a Server, a System Parameter), receiver 120 may receive, from server 130, a system parameter. For example, the system parameter may be represented includes at least in part in a non-associative octonion ring, and may include one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q. Processing may proceed from block 810 to block 820.
At block 820 (Select a Secret Decryption Key Corresponding To the Receiver), receiver 120 may select a secret decryption key corresponding to receiver 120. For example, the secret decryption key may be represented in a non-associative octonion ring. In some embodiments, the secret decryption key corresponding to receiver 120 may be selected such that an inverse of the secret decryption key exists. Processing may proceed from block 820 to block 830.
At block 830 (Generate a Public Encryption Key For the Receiver), receiver 120 may generate a public encryption key for receiver 120, based at least in part on the secret decryption key corresponding to receiver 120 and the system parameter. For example, the public encryption key for receiver 120 may be represented in a non-associative octonion ring. In some embodiments, receiver 120 may transmit the public encryption key corresponding to receiver 120, to server 130, such that server 130 publishes the public encryption key corresponding to receiver 120. Processing may proceed from block 830 to block 840.
At block 840 (Receive, From a Transmitter, a First Ciphertext), receiver 120 may receive, from transmitter 110, a first ciphertext. For example, the first ciphertext may be represented in a non-associative octonion ring. Processing may proceed from block 840 to block 850.
At block 850 (Receive, From the Server, a Public Encryption Key Corresponding To the Transmitter), receiver 120 may receive, from server 130, a public encryption key corresponding to transmitter 110. For example, the public encryption key for transmitter 110 may be represented in a non-associative octonion ring. Processing may proceed from block 850 to block 860.
At block 860 (Decipher the First Ciphertext), receiver 120 may decipher the first ciphertext based at least in part on the secret decryption key of receiver 120, the system parameter and the public encryption key corresponding to transmitter 110.
FIG. 9 shows an example flow diagram of a process 900 of a data processing device to implement a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein. The operations of process 900 may be implemented by system 100 including transmitter 110, receiver 120, server 130 and/or data processing device 140, as illustrated in FIGS. 1 to 4. Process 900 may include one or more operations, actions, or functions as illustrated by one or more blocks 910, 920, 930 and/or 940. Although illustrated as discrete blocks, various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation. Processing may begin at block 910.
At block 910 (Receive, From a Transmitter, a Request To Process a Message), data processing device 140 may receive, from transmitter 110, a request to process a message. Processing may proceed from block 910 to block 920.
At block 920 (Receive, From a Server, a System Parameter And a First Ciphertext That Corresponds To the Message), data processing device 140 may receive, from server 130, a system parameter and a first ciphertext that corresponds to the message, based at least in part on the received request. In some embodiments, the message may be enciphered to the first ciphertext by transmitter 110, based at least in part on a public encryption key and a secret decryption key corresponding to transmitter 110. Processing may proceed from block 920 to block 930.
At block 930 (Process the First Ciphertext To a Second Ciphertext), data processing device 140 may process the first ciphertext to a second ciphertext by calculating the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext. Processing may proceed from block 930 to block 940.
At block 940 (Transmit, To the Transmitter, the Second Ciphertext), data processing device 140 may transmit, to transmitter 110, the second ciphertext.
FIG. 10 schematically shows an example flow diagram of a process 1000 of an endorser to implement a homomorphic signature scheme, arranged in accordance with at least some embodiments described herein. The operations of process 1000 may be implemented by system 500 including server 510, endorser 520 and authenticator 530, as illustrated in FIGS. 5 and 6. Process 1000 may include one or more operations, actions, or functions as illustrated by one or more blocks 1010, 1020, 1030, 1040 and/or 1050. Although illustrated as discrete blocks, various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation. Processing may begin at block 1010.
At block 1010 (Receive, From a Server, a Signing Parameter), endorser 520 may receive, from server 510, a signing parameter. For example, the signing parameter may be represented at least in part in a non-associative octonion ring, and may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q, or an element C in the octonion ring such that C=1−B mod q. Processing may proceed from block 1010 to block 1020.
At block 1020 (Select a Secret Key Of the Endorser), endorser 520 may select a secret key of endorser 520. For example, the secret key of endorser 520 may be represented at least in part in a non-associative octonion ring. Processing may proceed from block 1020 to block 1030.
At block 1030 (Generate a Public Signing Key Of the Endorser), endorser 520 may generate a public signing key of endorser 520, based at least in part on the secret key corresponding to endorser 520 and the signing parameter. For example, the public signing key of endorser 520 may be represented at least in part in a non-associative octonion ring. Processing may proceed from block 1030 to block 1040.
At block 1040 (Calculate a Signature Corresponding To a Message), endorser 520 may calculate a signature corresponding to a message, based at least in part on the public signing key corresponding to endorser 520 and the signing parameter. For example, the signature and the message may be represented at least in part in a non-associative octonion ring. Processing may proceed from block 1040 to block 1050.
At block 1050 (Transmit, To the Server, the Signature and the Public Signing Key), endorser may transmit, to server 150, the signature and the public signing key. In some embodiments, endorser 520 may transmit, to authenticator 530, a request to evaluate the signature. Authenticator 530 may evaluate the signature to be converted to a derived signature, based at least in part on the request. Then, endorser 520 may receive, from authenticator 530, the derived signature, and receive, from server 510, the public signing key. Further, endorser may verify the derived signature based at least in part on the public signing key, where the verifying of the derived signature indicates whether the authenticator correctly evaluates the signature.
One skilled in the art will appreciate that, for this and other processes and methods disclosed herein, the functions performed in the processes and methods may be implemented in differing order. Furthermore, the outlined steps and operations are only provided as examples, and some of the steps and operations may be optional, combined into fewer steps and operations, or expanded into additional steps and operations without detracting from the essence of the disclosed embodiments.
FIG. 11 illustrates computer program products that may be utilized to provide a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein. Program product 1100 may include a signal bearing medium 1110. Signal bearing medium 1110 may include one or more instructions 1120 that, when executed by, for example, a transmitter, may provide the functionality described above with respect to FIGS. 1-10. By way of example, instructions 1120 may include: one or more instructions for receiving, from a server, a system parameter; one or more instructions for selecting a secret decryption key corresponding to the transmitter; one or more instructions for generating a first public encryption key for the transmitter, based at least in part on the secret decryption key corresponding to the transmitter and the system parameter; one or more instructions for receiving, from the server, a public encryption key corresponding to a receiver; one or more instructions for enciphering a message into a first ciphertext, based at least in part on the public encryption key corresponding to the receiver and the secret decryption key corresponding to the transmitter; or one or more instructions for transmitting, to a data processing device, a request to process the message by processing the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext. Thus, for example, referring to FIG. 2, transmitter 110 may undertake one or more of the blocks shown in FIG. 7 in response to instructions 1120.
In some implementations, signal bearing medium 1110 may encompass a computer-readable medium 1130, such as, but not limited to, a hard disk drive, a CD, a DVD, a digital tape, memory, etc. In some implementations, signal bearing medium 1110 may encompass a recordable medium 1140, such as, but not limited to, memory, read/write (R/W) CDs, R/W DVDs, etc. In some implementations, signal bearing medium 1110 may encompass a communications medium 1150, such as, but not limited to, a digital and/or an analog communication medium (e.g., a fiber optic cable, a waveguide, a wired communications link, a wireless communication link, etc.). Thus, for example, program product 1100 may be conveyed to one or more modules of transmitter 110, receiver 120, server 130 or data processing device 140 by an RF signal bearing medium 1120, where the signal bearing medium 1120 is conveyed by a wireless communications medium 1150 (e.g., a wireless communications medium conforming with the IEEE 802.11 standard).
FIG. 12 is a block diagram illustrating an example computing device 1200 that may be utilized to provide a homomorphic public key encryption scheme, arranged in accordance with at least some embodiments described herein. In these examples, elements of computing device 1200 may be arranged or configured for a device. In a very basic configuration 1202, computing device 1200 typically includes one or more processors 1204 and a system memory 1206. A memory bus 1208 may be used for communicating between processor 1204 and system memory 1206.
Depending on the desired configuration, processor 1204 may be of any type including but not limited to a microprocessor (μP), a microcontroller (μC), a digital signal processor (DSP), or any combination thereof. Processor 1204 may include one more levels of caching, such as a level one cache 1210 and a level two cache 1212, a processor core 1214, and registers 1216. An example processor core 1214 may include an arithmetic logic unit (ALU), a floating point unit (FPU), a digital signal processing core (DSP Core), or any combination thereof. An example memory controller 1218 may also be used with processor 1204, or in some implementations memory controller 1218 may be an internal part of processor 1204.
Depending on the desired configuration, system memory 1206 may be of any type including but not limited to volatile memory (such as RAM), nonvolatile memory (such as ROM, flash memory, etc.) or any combination thereof. System memory 1206 may include an operating system 1220, one or more applications 1222, and program data 1224. Application 1222 may include instructions 1226 that may be arranged to perform the functions as described herein including the actions described with respect to transmitter, receiver, server, data processing device, endorser or authenticator architectures as shown in FIGS. 1-6 or including the actions described with respect to the flow charts shown in FIGS. 7-10. In some examples, application 1222 may be arranged to operate with program data 1224 on an operating system 1220 such that the fully homomorphic public key encryption scheme as described herein may be provided.
Computing device 1200 may have additional features or functionality, and additional interfaces to facilitate communications between basic configuration 1202 and any required devices and interfaces. For example, a bus/interface controller 1230 may be used to facilitate communications between basic configuration 1202 and one or more data storage devices 1232 via a storage interface bus 1234. Data storage devices 1232 may be removable storage devices 1236, non-removable storage devices 1238, or a combination thereof. Examples of removable storage and non-removable storage devices include magnetic disk devices such as flexible disk drives and hard-disk drives (HDD), optical disk drives such as compact disk (CD) drives or digital versatile disk (DVD) drives, solid state drives (SSD), and tape drives to name a few. Example computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data.
System memory 1206, removable storage devices 1236 and non-removable storage devices 1238 are examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which may be used to store the desired information and which may be accessed by computing device 1200. Any such computer storage media may be part of computing device 1200.
Computing device 1200 may also include an interface bus 1240 for facilitating communication from various interface devices (e.g., output interfaces 1242, peripheral interfaces 1244, and communication devices 1246) to basic configuration 1202 via bus/interface controller 1230. Example output interfaces 1242 include a graphics processing unit 1248 and an audio processing unit 1250, which may be configured to communicate to various external devices such as a display or speakers via one or more A/V ports 1252. Example peripheral interfaces 1244 include a serial interface controller 1254 or a parallel interface controller 1256, which may be configured to communicate with external devices such as input devices (e.g., keyboard, mouse, pen, voice input device, touch input device, etc.) or other peripheral devices (e.g., printer, scanner, etc.) via one or more I/O ports 1258. An example communication device 1246 includes a network controller 1260, which may be arranged to facilitate communications with one or more other computing devices 1262 over a network communication link via one or more communication ports 1264.
The network communication link may be one example of a communication media. Communication media may typically be embodied by computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave or other transport mechanism, and may include any information delivery media. A “modulated data signal” may be a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media may include wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio frequency (RF), microwave, infrared (IR) and other wireless media. The term computer readable media as used herein may include both storage media and communication media.
Computing device 1200 may be implemented as a portion of a small-form factor portable (or mobile) electronic device such as a cell phone, a personal data assistant (PDA), a personal media player device, a wireless web-watch device, a personal headset device, an application specific device, or a hybrid device that include any of the above functions. Computing device 1200 may also be implemented as a personal computer including both laptop computer and non-laptop computer configurations.
Actions, functions, or methods with respect to receiver 120 may include: receiving, from a server, a system parameter; selecting a secret decryption key corresponding to the receiver; generating a public encryption key for the receiver, based at least in part on the secret decryption key corresponding to the receiver and the system parameter; receiving, from a transmitter, a first ciphertext; receiving, from the server, a public encryption key corresponding to the transmitter; and deciphering the first ciphertext based at least in part on the secret decryption key of the receiver, the system parameter and the public encryption key corresponding to the transmitter, wherein the selecting the secret decryption key of the receiver includes selecting the secret decryption key corresponding to the receiver such that an inverse of the secret decryption key exists.
According to such method, at least one of the secret decryption key corresponding to the receiver, the system parameter, the first ciphertext and the public encryption key corresponding to the transmitter may be represented at least in part in a non-associative octonion ring. Further, the system parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q. Such method may further include transmitting, to the server, the public encryption key corresponding to the receiver such that the server publishes the public encryption key corresponding to the receiver.
Actions, functions, or methods with respect to processor 1204 may include: receiving, from a transmitter, a request to process a message; receiving, from a server, a system parameter and a first ciphertext that corresponds to the message, based at least in part on the received request; processing the first ciphertext to a second ciphertext by calculating the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext; and transmitting, to the transmitter, the second ciphertext.
According to such method, the message may be enciphered to the first ciphertext by the transmitter, based at least in part on a public encryption key and a secret decryption key corresponding to the transmitter.
Actions, functions, or methods with respect to endorser 520 may include: receiving, from a server, a signing parameter; selecting a secret key of the endorser; generating a public signing key of the endorser, based at least in part on the secret key corresponding to the endorser and the signing parameter; calculating a signature corresponding to a message, based at least in part on the public signing key corresponding to the endorser and the signing parameter; and transmitting, to the server, the signature and the public signing key.
According to such method, the signing parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q, or an element C in the octonion ring such that C=1−B mod q. The method of may further include transmitting, to an authenticator, a request to evaluate the signature, the signature being evaluated to be converted to a derived signature by the authenticator, based at least in part on the request. The method may still further include: receiving, from the authenticator, the derived signature; receiving, from the server, the public signing key; and verifying the derived signature based at least in part on the public signing key, the verifying of the derived signature indicating whether the authenticator correctly evaluates the signature. Further still, the signature, the secret key and the public signing key of the endorser may be represented at least in part in a non-associative octonion ring.
Receiver 120 may include a receiving unit configured to: receive, from a server, a system parameter and a public encryption key corresponding to a transmitter, and receive, from a transmitter, a first ciphertext. Receiver 120 may also include a key manager to select a secret decryption key of the receiver and to generate a public encryption key for the receiver, based at least in part on the secret decryption key of the receiver and the system parameter. Receiver 120 may still further include a decipherer to decipher the first ciphertext based at least in part on the secret decryption key of the receiver, the system parameter and the public encryption key corresponding to the transmitter.
Receiver 120 may transmit, to the server, the public encryption key of the sender such that the server publishes the public encryption key corresponding to the receiver. Further, the system parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q.
Processor 1204 may include a receiving unit to receive, from a transmitter, a request to process a message, and to receive, from a server, a system parameter and a first ciphertext that corresponds to the message, based at least in part on the received request. Also included may be one or more processors to process the first ciphertext into a second ciphertext by calculating the first ciphertext, based at least in part on the received request, without deciphering the first ciphertext; and a transmitting unit to transmit, to the transmitter, the second ciphertext. The message may be enciphered to the first ciphertext by the transmitting unit, based at least in part on a public encryption key and a secret decryption key corresponding to the transmitter.
Endorser 520 may include: a receiving unit to receive, from a server, a signing parameter; a key manager to select a secret key corresponding to the endorser, and to generate a public signing key for the endorser, based at least in part on the secret key corresponding to the endorser and the signing parameter; a signature generator to calculate a signature corresponding to a message, based at least in part on the public signing key corresponding to the endorser and the signing parameter; and a transmitting unit to transmit, to the server, the signature and the public signing key.
With regard to endorser 520, the signing parameter may include at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q and b0≠0 mod q, or an element C in the octonion ring such that C=1−B mod q; the transmitting unit may further transmit, to an authenticator, a request to evaluate the signature, the authenticator may evaluate the signature to be converted to a derived signature based at least in part on the request, and the receiving unit may further receive, from the authenticator, the derived signature and receive, from the server, the public signing key. The endorser may further include a verifier to verify the derived signature based at least in part on the public signing key to determine whether the authenticator correctly evaluates the signature.
The present disclosure is not to be limited in terms of the particular embodiments described in this application, which are intended as illustrations of various aspects. Many modifications and variations can be made without departing from its spirit and scope, as will be apparent to those skilled in the art. Functionally equivalent methods and apparatuses within the scope of the disclosure, in addition to those enumerated herein, will be apparent to those skilled in the art from the foregoing descriptions. Such modifications and variations are intended to fall within the scope of the appended claims. The present disclosure is to be limited only by the terms of the appended claims, along with the full scope of equivalents to which such claims are entitled. It is to be understood that this disclosure is not limited to particular methods, reagents, compounds, compositions or biological systems, which can, of course, vary. It is also to be understood that the terminology used herein is for the purpose of describing particular embodiments only, and is not intended to be limiting.
With respect to the use of substantially any plural and/or singular terms herein, those having skill in the art can translate from the plural to the singular and/or from the singular to the plural as is appropriate to the context and/or application. The various singular/plural permutations may be expressly set forth herein for sake of clarity.
It will be understood by those within the art that, in general, terms used herein, and especially in the appended claims (e.g., bodies of the appended claims) are generally intended as “open” terms (e.g., the term “including” should be interpreted as “including but not limited to,” the term “having” should be interpreted as “having at least,” the term “includes” should be interpreted as “includes but is not limited to,” etc.). It will be further understood by those within the art that if a specific number of an introduced claim recitation is intended, such an intent will be explicitly recited in the claim, and in the absence of such recitation no such intent is present. For example, as an aid to understanding, the following appended claims may contain usage of the introductory phrases “at least one” and “one or more” to introduce claim recitations. However, the use of such phrases should not be construed to imply that the introduction of a claim recitation by the indefinite articles “a” or “an” limits any particular claim containing such introduced claim recitation to embodiments containing only one such recitation, even when the same claim includes the introductory phrases “one or more” or “at least one” and indefinite articles such as “a” or “an” (e.g., “a” and/or “an” should be interpreted to mean “at least one” or “one or more”); the same holds true for the use of definite articles used to introduce claim recitations. In addition, even if a specific number of an introduced claim recitation is explicitly recited, those skilled in the art will recognize that such recitation should be interpreted to mean at least the recited number (e.g., the bare recitation of “two recitations,” without other modifiers, means at least two recitations, or two or more recitations). Furthermore, in those instances where a convention analogous to “at least one of A, B, and C, etc.” is used, in general such a construction is intended in the sense one having skill in the art would understand the convention (e.g., “a system having at least one of A, B, and C” would include but not be limited to systems that have A alone, B alone, C alone, A and B together, A and C together, B and C together, and/or A, B, and C together, etc.). In those instances where a convention analogous to “at least one of A, B, or C, etc.” is used, in general such a construction is intended in the sense one having skill in the art would understand the convention (e.g., “a system having at least one of A, B, or C” would include but not be limited to systems that have A alone, B alone, C alone, A and B together, A and C together, B and C together, and/or A, B, and C together, etc.). It will be further understood by those within the art that virtually any disjunctive word and/or phrase presenting two or more alternative terms, whether in the description, claims, or drawings, should be understood to contemplate the possibilities of including one of the terms, either of the terms, or both terms. For example, the phrase “A or B” will be understood to include the possibilities of “A” or “B” or “A and B.”
As will be understood by one skilled in the art, for any and all purposes, such as in terms of providing a written description, all ranges disclosed herein also encompass any and all possible subranges and combinations of subranges thereof. Any listed range can be easily recognized as sufficiently describing and enabling the same range being broken down into at least equal halves, thirds, quarters, fifths, tenths, etc. As a non-limiting example, each range discussed herein can be readily broken down into a lower third, middle third and upper third, etc. As will also be understood by one skilled in the art all language such as “up to,” “at least,” and the like include the number recited and refer to ranges which can be subsequently broken down into subranges as discussed above. Finally, as will be understood by one skilled in the art, a range includes each individual member. Thus, for example, a group having 1-3 cells refers to groups having 1, 2, or 3 cells. Similarly, a group having 1-5 cells refers to groups having 1, 2, 3, 4, or 5 cells, and so forth.
From the foregoing, it will be appreciated that various embodiments of the present disclosure have been described herein for purposes of illustration, and that various modifications may be made without departing from the scope and spirit of the present disclosure. Accordingly, the various embodiments disclosed herein are not intended to be limiting, with the true scope and spirit being indicated by the following claims.

## Claims

1. A method performed under control of a transmitter of a computing device, the method comprising:
receiving, from a server, a system parameter at the computing device;
selecting, by the computing device, a secret decryption key corresponding to the transmitter;

generating a first public encryption key for the transmitter, based at least in part on the secret decryption key corresponding to the transmitter and the system parameter received from the server;
receiving, from the server, a public encryption key corresponding to a receiver of a data processing device, wherein the data processing device is different from the computing device;
enciphering, by the computing device, a message into a first ciphertext, based at least in part on the public encryption key corresponding to the receiver of the data processing device and the secret decryption key corresponding to the transmitter;
transmitting, from the computing device to the data processing device, a request to process the message by processing, at the data processing device, the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext; and
deciphering, by the computing device, the second ciphertext received from the data processing device upon completion of the message process request, based on at least the system parameter, the first public encryption key, and the secret decryption key corresponding to the transmitter of the computing device.

2. The method of claim 1, wherein at least one of: the system parameter, the secret decryption key corresponding to the transmitter, the public encryption key corresponding to the receiver, the message, and the first ciphertext are represented at least in part in a non-associative octonion ring.

3. The method of claim 1, wherein the system parameter includes at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q, and b0≠0 mod q.

4. The method of claim 1, further comprising:
transmitting, from the computing device to the server, the first public encryption key for the transmitter such that the server publishes the first public encryption key for the transmitter.

5. The method of claim 1, further comprising:
selecting, by the computing device, a temporary secret decryption key corresponding to the transmitter;
generating, by the computing device, a temporary public encryption key of the transmitter, based at least in part on the temporary secret decryption key corresponding to the transmitter and the system parameter; and
generating, by the computing device, a second public encryption key for the transmitter, based at least in part on the first public encryption key, the temporary secret decryption key corresponding to the transmitter, and the system parameter,
wherein the enciphering is further based on the temporary secret decryption key corresponding to the transmitter.

6. The method of claim 5, further comprising:
receiving, from the data processing device, the second ciphertext at the computing device; and
deciphering, by the computing device, the second ciphertext, based at least in part on the system parameter, the first public encryption key, and the temporary secret decryption key corresponding to the transmitter,
wherein the deciphering the second ciphertext includes obtaining the processed message.

7. The method of claim 1, further comprising:
generating, by the computing device, a public encryption key for the transmitter and for the receiver, based at least in part on the public encryption key corresponding to the receiver, the secret decryption key corresponding to the transmitter, and the system parameter; and
transmitting, to the server, the first ciphertext,
wherein the enciphering is further based on the secret decryption key corresponding to the transmitter.

8. A transmitter of a computing device, the transmitter comprising:
a receiving unit of the computing device configured to receive, from a server, a system parameter and a public encryption key corresponding to a receiver of a data processing device, wherein the data processing device is different from the computing device;
a key manager of the computing device configured to select a secret decryption key of the transmitter and to generate a first public encryption key for the transmitter, based at least in part on the secret decryption key corresponding to the transmitter and the system parameter received from the server;
an encipherer of the computing device configured to encipher a message into a first ciphertext, based at least in part on the public encryption key corresponding to the receiver of the data processing device and the secret decryption key corresponding to the transmitter;
a transmitting unit of the computing device configured to transmit, to the data processing device, a request to process the message by processing, at the data processing device, the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext; and
a deciphering unit, of the computing device, configured to decipher the second ciphertext received from the data processing device upon completion of the message process request, based on at least the system parameter, the first public encryption key, and the secret decryption key corresponding to the transmitter of the computing device.

9. The transmitter of claim 8, wherein the transmitting unit is further configured to transmit, to the server, the first public encryption key for the transmitter such that the server publishes the first public encryption key for the transmitter.

10. The transmitter of claim 8, wherein the system parameter includes at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q, and b0≠0 mod q.

11. The transmitter of claim 8, wherein the key manager is further configured to:
select a temporary secret decryption key for the transmitter;
generate a temporary public encryption key for the transmitter, based at least in part on the temporary secret decryption key corresponding to the transmitter and the system parameter; and
generate a second public encryption key for the transmitter, based at least in part on the first public encryption key, the temporary secret decryption key corresponding to the transmitter, and the system parameter,
wherein the encipherer is configured to encipher the message into the first ciphertext further based on the temporary secret decryption key corresponding to the transmitter.

12. The transmitter of claim 11, wherein the receiving unit is further configured to receive, from the data processing device, the second ciphertext,
wherein the transmitter further comprises a decipherer configured to decipher the second ciphertext, based at least in part on the system parameter, the first public encryption key, and the temporary secret decryption key corresponding to the transmitter, and
wherein the deciphering of the second ciphertext includes obtaining the processed message.

13. The transmitter of claim 8, wherein the key manager is further configured to generate a public encryption key for the transmitter and a receiver, based at least in part on the public encryption key corresponding to the receiver, the secret decryption key corresponding to the transmitter, and the system parameter,
wherein the encipherer is configured to encipher the message into the first ciphertext, based at least in part on the public encryption key corresponding to the receiver and the secret decryption key corresponding to the transmitter, and
wherein the transmitting unit is configured to transmit, to the server, the first ciphertext.

14. A non-transitory computer-readable medium having computer-executable instructions stored thereon that, when executed, cause one or more hardware processors to:
receive, from a server, a system parameter at a computing device;
select a secret decryption key corresponding to a transmitter of the computing device;
generate a first public encryption key for the transmitter, based at least in part on the secret decryption key corresponding to the transmitter and the system parameter received from the server;
receive, from the server, a public encryption key corresponding to a receiver of a data processing device, wherein the data processing device is different from the computing device;
encipher a message into a first ciphertext, based at least in part on the public encryption key corresponding to the receiver of the data processing device and the secret decryption key corresponding to the transmitter;
transmit, from the computing device to the data processing device, a request to process the message by processing, at the data processing device, the first ciphertext that corresponds to the message into a second ciphertext without deciphering the first ciphertext; and
decipher, by the computing device, the second ciphertext received from the data processing device upon completion of the message process request, based on at least the system parameter, the first public encryption key, and the secret decryption key corresponding to the transmitter of the computing device.

15. The computer-readable medium of claim 14, wherein at least one of the system parameter, the secret decryption key corresponding to the transmitter, the public encryption key corresponding to the receiver, the message, and the first ciphertext are represented at least in part in a non-associative octonion ring.

16. The computer-readable medium of claim 14, wherein the system parameter includes at least one of a prime number q greater than 2, or an element B=(b0, . . . , b7) in an octonion ring over a finite field such that |B|2=0 mod q, B≠0 mod q, and b0≠0 mod q.

17. The computer-readable medium of claim 14, further comprising instructions that cause the one or more hardware processors to further:
transmit, from the computing device to the server, the first public encryption key for the transmitter such that the server publishes the first public encryption key for the transmitter.

18. The computer-readable medium of claim 14, further comprising instructions that cause the one or more hardware processors to further:
select a temporary secret decryption key corresponding to the transmitter;
generate a temporary public encryption key of the transmitter, based at least in part on the temporary secret decryption key corresponding to the transmitter and the system parameter; and
generate a second public encryption key for the transmitter, based at least in part on the first public encryption key, the temporary secret decryption key corresponding to the transmitter, and the system parameter,
wherein the message is enciphered into the first ciphertext based, further, on the temporary secret decryption key corresponding to the transmitter.

19. The computer-readable medium of claim 18, further comprising instructions that cause the one or more hardware processors to further:
receive, from the data processing device, the second ciphertext; and
decipher the second ciphertext, based at least in part on the system parameter, the first public encryption key, and the temporary secret decryption key corresponding to the transmitter, wherein the second ciphertext is deciphered by obtaining the processed message.

20. The computer-readable medium of claim 14, further comprising instructions that cause the one or more hardware processors to further:
generate a public encryption key for the transmitter and for the receiver, based at least in part on the public encryption key corresponding to the receiver, the secret decryption key corresponding to the transmitter, and the system parameter; and
transmit, to the server, the first ciphertext,
wherein the message is enciphered into the first ciphertext based, further, on the secret decryption key corresponding to the transmitter.