Patent Publication Number: US-9900147-B2

Title: Homomorphic encryption with optimized homomorphic operations

Description:
BACKGROUND 
     The development of cloud storage and services has allowed users to offload and/or outsource both storage of their data and associated computations on that data. As a result, businesses can choose to forego the expensive proposition of maintaining their own data centers, relying instead on cloud storage and computational services. In addition to storing data in remote servers, computations can be performed in remote servers as well. 
     Maintaining data confidentiality is an especially important concern for storing data and performing computations on data in remote servers. Encryption schemes represent one form of technology directed towards securing data when stored in memory, when operated on, and/or transmitted over networks. 
     SUMMARY 
     The techniques and/or systems described herein are directed to improvements in homomorphic operations to improve processing speed and storage requirements. For example, the techniques and/or systems can be used on homomorphically encoded and encrypted data received from a client device, to be operated on while maintaining confidentiality of data. The homomorphic operations, including approximate division, sign testing, comparison testing, and equality testing can provide flexible tools for performing secure operations on encrypted data. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference number in different figures indicates similar or identical items. 
         FIG. 1  illustrates an example environment for managing secure computations on encrypted data. 
         FIG. 2  illustrates an example process for managing secure computations on encrypted data. 
         FIG. 3  illustrates an example process for approximate division on encrypted data. 
         FIG. 4  illustrates an example process for performing sign testing on encrypted data. 
         FIG. 5  illustrates an example process for performing comparison testing on encrypted data. 
         FIG. 6  illustrates an example process for performing equality testing on encrypted data. 
     
    
    
     DETAILED DESCRIPTION 
     The techniques and/or systems described herein provide improved homomorphic encryption with optimized homomorphic operations. The optimized homomorphic operations include approximate division using plain modulus switching, sign testing (e.g., positive or negative) on encrypted data, comparison testing (e.g., greater than/less than) on encrypted data, and equality testing (e.g., n 1 =n 2 ) on encrypted data. The techniques and/or systems described herein can be used in fully homomorphic encryption, partial homomorphic encryption, and practical homomorphic encryption. 
     Fully Homomorphic Encryption (FHE) refers to an encryption scheme that allows an untrusted server to execute arbitrary computation on encrypted data on behalf of a computing device often referred to as a client. Solutions for constructing an FHE scheme can incur significant costs due to a reliance on certain mathematical concepts (e.g., ideal lattices) to evaluate any function on encrypted data. In practice, these constructions can be improved using techniques, such as those related to batch-wise or bit-wise encryption, but often remain unworkable for a number of reasons, for example, necessitating deep circuits, such as those based on symmetric encryption standards, and/or substantial storage space to process ciphertexts. While some FHE constructions are capable of computing block ciphers homomorphically, evaluating a single block using these constructions can be several orders of magnitude slower in terms of throughput and latency when compared to evaluating a single block non-homomorphically. 
     The techniques and/or systems described herein can improve a functioning of a computing device by reducing an amount of processing and/or by reducing an amount of memory required for performing computations on encrypted data. For example, the approximate division techniques discussed herein can reduce a number of multiplication steps or obviate multiplication operations all together, thereby reducing the computational complexity of homomorphic operations. By way of another example, the sign testing, comparison testing, and equality testing can provide flexible operations that can be used individually or combined in any manner to reduce an amount of processing or memory required to perform homomorphic operations. The techniques and/or systems discussed herein can improve the functioning of a computer and/or a network by improving the security of the data transmitted, operated on, and stored in a network. For example, the techniques described herein can allow encrypted data to be transmitted, operated on, and a result can be obtained, all without requiring the data to be decrypted or decoded on a remote server, thereby ensuring a confidentiality of the data. Further, the techniques and/or systems described herein allow clients to outsource computations to a network computer when a client does not have all the data required to run an algorithm. 
     Various examples for implementing homomorphic encryption with optimized homomorphic operations are described herein with reference to  FIGS. 1-6 . 
       FIG. 1  illustrates an example environment  100  that is usable to implement the techniques and/or systems associated with the homomorphic encryption scheme described herein. The environment  100  includes computing device(s)  102  having processor(s)  104  and a memory  106  including an encoding/encrypting module  108  and a decoding/decrypting module  110 . In various embodiments, the encoding/encrypting module  108  can include one or more programs or hardware that operates to encode and/or encrypt data in a scheme for secure remote computation. The environment  100  also includes service provider(s)  112  to provide one or more services to the computing device  102 , such as the secure remote computing. To that end, the service provider  112  can include processor(s)  114  and a memory  116  including a parameter selection module  118  and a computation module  120  to provide the secure remote computing, which is explained in connection with the figures provided in this disclosure. 
     The computing device  102  can include, but is not limited to, any one of a variety of computing devices, such as a smart phone, a mobile phone, a personal digital assistant (PDA), an electronic book device, a laptop computer, a desktop computer, a tablet computer, a portable computer, a gaming device, a personal media player device, a server computer, a wearable device, or any other electronic device. 
     As introduced above, the computing device  102  can include one or more processor(s)  104  and memory  106 . The processor(s)  104  can be a single processing unit or a number of units, each of which could include multiple different processing units. The processor(s)  104  can include one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units (CPUs), graphics processing units (GPUs), security processors (e.g., secure cryptoprocessors), and/or other processors. Alternatively, or in addition, some or all of the techniques described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-Programmable Gate Arrays (FPGAs), Application-Specific Integrated Circuits (ASICs), Application-Specific Standard Products (ASSPs), state machines, Complex Programmable Logic Devices (CPLDs), other logic circuitry, systems on chips (SoCs), and/or any other devices that perform operations based on software and/or hardware coded instructions. Among other capabilities, the processor(s)  104  can be configured to fetch and/or execute computer-readable instructions stored in the memory  106 . 
     The memory  106  can include one or a combination of computer-readable media. As used herein, “computer-readable media” includes computer storage media and communication media. 
     Computer storage media includes volatile and non-volatile, 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. Computer storage media includes, but is not limited to, Phase Change Memory (PCM), Static Random-Access Memory (SRAM), Dynamic Random-Access Memory (DRAM), other types of Random-Access Memory (RAM), Read-Only Memory (ROM), Electrically Erasable Programmable ROM (EEPROM), flash memory or other memory technology, Compact Disc ROM (CD-ROM), Digital Versatile Discs (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store information for access by a computing device. 
     In contrast, communication media includes computer-readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave. As defined herein, computer storage media does not include communication media. 
     In various embodiments, the computing device  102  can communicate with the service provider  112  via one or more wired or wireless networks  122 , such as the Internet, a Mobile Telephone Network (MTN), or other various communication technologies. 
     In various embodiments, the memory  106  can include an operating system configured to manage hardware and services within and coupled to the computing device  102  for the benefit of other components and other devices. 
     The encoding/encrypting module  108  and the decoding/decrypting module  110  can include hardware and/or software components. For example, the encoding/encrypting module  108  and/or the decoding/decrypting module  110  can be implemented by one or more modules stored in the memory  106  and/or by one or more components of the processor(s)  104 . As used herein, the term “module” is intended to represent example divisions of software and/or firmware for purposes of discussion, and is not intended to represent any type of requirement or required method, manner or organization. Accordingly, while various “modules” are discussed, their functionality and/or similar functionality could be arranged differently (e.g., combined into a fewer number of modules, broken into a larger number of modules, etc.). Further, while certain functions are described herein as being implemented as software modules configured for execution by a processor, in other embodiments, any or all of the functions can be implemented (e.g., performed) in whole or in part by hardware logic components, such as FPGAs, ASICs, ASSPs, state machines, CPLDs, other logic circuitry, SoCs, and so on. 
     The encoding/encrypting module  108  can perform operations to encode and/or encrypt data in accordance with embodiments of the disclosure. For example, the encoding/encrypting module  108  can utilize parameters generated by the service provider  112  to encode data using the techniques disclosed herein. Further, the encoding/encrypting module  108  can generate a public key based at least in part on the parameters generated by the service provider  112  to encrypt the encoded data. 
     The decoding/decrypting module  110  can perform operations to decrypt and/or decode data in accordance with embodiments of the disclosure. For example, the decoding/decrypting module  110  can utilize parameters generated by the service provider  112  to generate a secret key for decrypting the encrypted data. Further, the decoding/decrypting module  110  can decode the decrypted data to obtain a plaintext result. 
     The service provider  112  can include one or more computing devices, such as one or more desktop computers, laptop computers, servers, and the like. The one or more computing devices can be configured in a cluster, data center, cloud computing environment, or a combination thereof. In one example, the one or more computing devices provide cloud computing resources, including computational resources, storage resources, and the like, that operate remotely from the computing device  102 . 
     The one or more computing devices of the service provider  112  can include one or more processor(s)  114  and memory  116 . The one or more processor(s)  114  can comprise a single processing unit or a number of units, each of which could include multiple different processing units. The one or more processor(s)  114  can include, for example, one or more microprocessors, microcomputers, microcontrollers, digital signal processors, CPUs, GPUs, security processors (e.g., secure cryptoprocessors), etc. 
     The memory  116  can include a parameter selection module  118  for automatically selecting parameters for implementing the homomorphic encryption scheme. For example, the parameter selection module  118  can receive a program, sequence, or series of operations from the computing device  102 , for example, to perform on homomorphically encrypted data. The parameter selection module  118  can determine a plaintext modulus T based on the operations in the user program, for example, by determining a divisor required by the intended operations. Other parameters can be selected by the parameter selection module  118 , including but not limited to a length N of a polynomial, a modulus Q, a standard deviation of error σ, a decomposition bit count W, a base B for encoding integers or real numbers into plaintext polynomials, a desired security level, an allowable error level, and the like. After parameters are generated and/or selected by the parameter selection module  118 , the parameters can be transmitted to the computing device  102 , to be used by the encoding/encrypting module  108  and/or by the decoding/decrypting module  110 . 
     The memory  116  can also include a computation module  120  to perform computations on encoded and encrypted data received from the computing device  102 . For example, the computation module  120  can be a program such as a machine learning program, a prediction engine, an image analysis program, a financial program, or any other program that performs calculations on encrypted data. For example, the computation module  120  can include a tax preparation program, and can receive tax and financial data encoded by the encoding/encrypting module  108 . In another example, the computation module  120  can include a genomic data analysis program to perform predictive analysis on genomic data encoded and/or encrypted by the encoding/encrypting module  108 . As can be understood in the context of this disclosure, the computation module  120  can include any program, computation, or operation that can be performed on data. In various embodiments, the computation module  120  can perform computations on the received encoded and/or encrypted data and can generate an encoded and/or encrypted result, which can be transmitted to the computing device  102  for decryption and/or decoding by the decoding/decrypting module  110 . 
     The computation module  120  can include one or more modules to perform homomorphic operations, such as an addition  124  module, a subtraction  126  module, a multiplication  128  module, a division  130  module, a sign testing  132  module, a comparison testing  134  module, and an equality testing  136  module. The addition  124  module, the subtraction  126  module, and the multiplication  128  module can perform operations on homomorphically encrypted data in accordance with the plain and ordinary meaning of these terms (e.g., adding two or more values, subtracting two or more values, and multiplying two or more values). Further, the division  130  module can perform division on homomorphically encrypted data by multiplying a number by a fractional value (e.g., a multiplication by ½ results in the same value as dividing by 2) or through approximate division, as discussed herein. The sign testing  132  module can evaluate encrypted data to determine if a value is negative or positive. The comparison testing  136  module can determine, for example, which value is larger between two given encrypted values. The equality testing  136  module can determine if two given values are equal. The operations of these modules  124 ,  126 ,  128 ,  130 ,  132 ,  134 , and  136  are further explained in connection with  FIGS. 2-6  of this disclosure. 
     The environment  100  also includes one or more users  140  to employ the computing device  102 . The one or more users  140  can interact with the computing device  102  to perform a variety of operations. 
     The example processes (e.g., in  FIGS. 2-6 ) are illustrated as logical flow graphs, each operation of which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the operations represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, configure a device to perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described operations can be combined in any order and/or in parallel to implement the process. Further, any of the individual operations can be omitted. 
       FIG. 2  illustrates an example process  200  for managing secure computations on encrypted data, according to one example implementation. By way of example, the process  200  can be performed by and between computing device(s)  202  and service provider(s)  204 , which can correspond to the computing device  102  and the service provider  112  in  FIG. 1 . 
     At  206 , the service provider  204  can generate encoding and/or encrypting parameters using the parameter selection module  118 , for example, of  FIG. 1 . In some embodiments, the service provider  204  generates the encoding and encrypting parameters in response to a request from the computing device  102 . By way of example, the encoding and encrypting parameters can include, but is not limited to, a plaintext modulus T, based at least in part on a largest value for coefficients in a polynomial and/or based on the operations to be performed. In some embodiments, the plaintext modulus T can be set to be larger than any coefficient appearing in any plaintext polynomial at any point in the computations (e.g., coefficients in a “fresh” polynomial, or in a polynomial after operations have been performed, such as addition and/or multiplication). Further, as is described in connection with various figures of this disclosure, a plaintext modulus T can be based in part on an approximate division operation to be performed, or can be based in part on a sign testing operation to be performed, etc. However, as the plaintext modulus T increases, an error grows during homomorphic operations. Therefore, the plaintext modulus T can be set above any coefficient value that can occur in any encoded polynomial and/or can be set above any value required to perform the homomorphic operations discussed herein, without being higher than required, to prevent any unnecessary increase in the rate at which noise grows during operations. 
     At  208 , the encoding and encrypting parameters can be transmitted to the computing device  202 . In some embodiments, the parameters  208  can be encrypted using a public key associated with the computing device  202 , to further ensure the security of the data processing. 
     The computing device  202  can receive the parameters  208 , and at  210  can use the encoding parameters to encode data as a plaintext polynomial. 
     At  212 , the data encoded in operation  210  is encrypted as a ciphertext, based at least in part on the parameters generated by the service provider  204 . Because the data is encoded and encrypted by the computing device  202 , the security and confidentiality of the data is preserved. In some embodiments, the operation  212  can include generating a public key for encrypting the encoded data, and a private key for decrypting the encrypted data. As can be understood in the context of this disclosure, the public and private keys can be generated at least in part based on the encoding and encrypting parameters generated by the service provider  204  in operation  206 . 
     At  214 , the ciphertext is transmitted to the service provider  204 . After the ciphertext is received by the service provider  204 , at operation  216 , computations can be performed on the ciphertext. As can be understood in the context of this disclosure, computations to be performed on the ciphertext can be determined by a program running on the service provider  204 , and can include, but is not limited to, an image analysis process, a genomic analysis algorithm, a prediction algorithm, financial transactions, etc. In the context of this disclosure, the operation  216  can include any combination or sequence of addition, subtraction, multiplication, division/approximate division, sign testing, comparison testing, and/or equality testing operations. Further, because of the process of encoding and encrypting the data, the computations can be performed on the data without decoding or decrypting the data. That is to say, homomorphic operations applied to the encoded and encrypted data can correspond to operations performed on the underlying data, without revealing any information about the contents of the data to the service provider  204 . 
     At  218 , an encoded and encrypted result is generated by the service provider  204 . As discussed above, a result can be generated without decoding or decrypting the data, which therefore ensures the confidentiality of the data and the result of the operations. For example, if a prediction algorithm performs operations on encoded and encrypted data, the service provider  204  learns nothing about the prediction, other than the fact that operations were performed, which can correspond to a prediction. 
     At  220 , an encoded and encrypted result is returned to the computing device  202 , after which, the computing device  202  can use an associated secret key to decrypt and decode the result to obtain a plaintext result. In some embodiments, the secret key (and the public key, discussed above) can be based at least in part on the encoding and/or encrypting parameters received from the service provider  204 , resulting in optimized homomorphic encryption. As can be understood in the context of this disclosure, a plurality of users can encrypt data using the public key, and contribute the data to a computation performed on the service provider  204 , but only one user can have the secret key to decrypt any result from the service provider  204 . In this manner, optimized computations can be performed remotely without revealing any information about a user&#39;s data. 
       FIG. 3  illustrates an example process  300  for performing approximate division on encrypted data, according to one example implementation. In one embodiment, the process  300  can be performed by service provider  112  and/or the computing device  102  of  FIG. 1 . However, processes can be performed in other environments and by other devices as well. 
     In general, the process  300  includes performing approximate division on encrypted data using plaintext modulus switching. One advantage of the process  300  is that it can provide a division operation without requiring a homomorphic multiplication operation, such as a fractional multiplication operation. For example, a series of operations can include a combination of addition and/or subtraction operations, followed by a division operation before returning an encrypted result. A fractional multiplication operation can be performed to provide a division operation (e.g., multiplying by ½ as an equivalent operation of dividing by 2). However, if the series of operations has not involved a multiplication step up until this point, the addition of a multiplication step can greatly increase the processing requirements and memory requirements to perform the operations. Therefore, by using the approximate division technique discussed herein, a multiplication step can be avoided either in part or in whole, thereby improving a functioning of the computer by reducing processing and memory requirements while performing homomorphic operations. 
     At  302 , the operation determines a divisor as T 1 . For example, a sequence of homomorphic operations can include dividing an encrypted number by T 1 , wherein the sequence of homomorphic operations can be received as a program by the service provider  112  of  FIG. 1 . Thus, the parameter selection module  118  can analyze the program to determine if any approximate divisions can be performed, and if so, can also determine the divisor of such operations. By way of example and without limitation, an operation can include calculating an average of three numbers, in which case, the divisor would be 3. 
     At  304 , the operation determines a plaintext modulus T 1 *T 2 . Collectively, the plaintext modulus can be represented as plaintext modulus T. As discussed above, the plaintext modulus T can be set to be larger than any coefficient appearing in any plaintext polynomial at any point in the computations (e.g., coefficients in a “fresh” polynomial, or in a polynomial after operations have been performed, such as addition and/or multiplication). In one simplified example, assuming a base=2, the coefficients present in a freshly encoded polynomial (i.e., before any operations are performed) are limited to either 0 or 1. However, in an example where the number 3 is encoded as x+1, and two encoded polynomials are added together, the coefficients in the polynomial grow to 2x+2. Thus, the plaintext modulus T can be set larger than the coefficients present in any polynomial (e.g., larger than 2) to avoid modular reduction, which can occur if the coefficients increase larger than the plaintext modulus T. Further, the plaintext modulus T can be determined such that the plaintext modulus T can be evenly divided by the divisor T 1  determined in the operation  302 . By way of example and without limitation, the plaintext modulus T 1 *T 2  can be determined as 3*2 10 , which would allow for an approximate division operation including 3 as a divisor. It can be understood in the context of this disclosure that the plaintext modulus of 3072 (i.e., 3*2 10 ) would allow for a number of divisors beyond 3, such as 2, 3, 4, 6, 8, 12, 16, etc. 
     At  306 , the operations can constrain nε[0, T 2 −1]. That is to say, the value(s) to be encoded/encrypted can be constrained between 0 and T 2 −1. It can be understood in the context of this disclosure that the homomorphic scheme can encode positive and negative numbers within the range constrained in the operation  306  (e.g., with numbers between 0 and T 2 /2 (not including T 2 /2) encoded as positive numbers and numbers between T 2 /2 and T 2 −1 (not including T 2 /2) encoded as negative number, or the like). Further, it can be understood in the context of this disclosure that the operations  302 ,  304 , and/or  306  can be performed by the parameter selection module  118  in the service provider  112  of  FIG. 1  to generate parameters, which can be sent to the client computing device for subsequent encoding and encrypting of the data to be operated on. Further, the operation  306  can include an operation of sending parameters (such as the plaintext modulus T 1 *T 2 ) to the computing device after the parameters have been determined and/or generated. 
     At  308 , the operation can encrypt values to be operated on using parameters determined by the parameter selection module  118 , including the plaintext modulus T 1 *T 2 . Further, the operation  308  can include an operation of receiving parameters (such as the plaintext modulus T 1 *T 2 ) at the computing device after the parameters have been sent by the service provider  112 , for example, and the operation  308  can include sending the encrypted values to the service provider after the encryption has been performed at the computing device, for example, in accordance with  FIG. 2 . 
     At  310 , the operation can divide a ciphertext coefficient-wise by T 1 , and round the coefficients during the operation. This operation provides the approximate division operation as discussed herein, without using a multiplication-type operation, which accordingly reduces a processing requirement and memory requirement of performing the homomorphic operation. By way of example and without limitation, the operation  310  can be explained in connection with a division of an encrypted polynomial as encrypt(n)=7x 5 +2x 4 +x 3 +7, using a divisor as T 1 =3. Thus, the operation  310  is performed coefficient-wise as follows: 
                   7   3     ⁢     x   5       +       2   3     ⁢     x   4       +       1   3     ⁢     x   3       +     7   3       ,         
which can round to 2x 5 +1x 4 +0x 3 +2. It can be understood in the context of this disclosure that other rounding schemes can be used, instead of that shown above. For example, different rounding schemes can be used for each coefficient of the polynomial, or rounding schemes can include rules that prevent coefficients rounding down to zero, for example. In this manner, the coefficient-wise division can be optimized for each coefficient by applying an optimized rounding scheme to minimize error in the approximate division result.
 
     Continuing with the example above, the ciphertext polynomial subject to the approximate division operation can be compared with a traditional division operation. For example, the polynomial encrypt(n)=7x 5 +2x 4 +x 3 +7 can be evaluated at x=2, and the result can be divided by 3 to illustrate a result of 
                   7   ⋆     2   5       +     2   ⋆     2   4       +     2   3     +   7     3     =       271   3     =     90.33   .             
In contrast, the approximate division operation returns a result of 2*2 5 +1*2 4 +0*2 3 +2=82. As can be understood in the context of this disclosure, various rounding operations can be utilized to reduce an error of the approximate division operation. By way of example, and without limitation, adding a rule to the rounding operation preventing a coefficient-wise division reducing a coefficient to zero would result in an approximate division operation of 2x 5 +1x 4 +1x 3 +2, which when evaluated at x=2, returns a result of 2*2 5 +1*2 4 +1*2 3 +2=90.
 
     At  312 , the operation can perform additional homomorphic operations on the ciphertext from the operation  310 . However, subsequent operations can be performed between ciphertexts of plaintext modulus T 2 . That is to say, after performing approximate division on the ciphertext with plaintext modulus T 1 *T 2  using the divisor of T 1 , the resulting ciphertext can use a plaintext modulus T 2  for subsequent operations. Further, the operation  312  can include transmitting the encrypted result to the computing device for decryption and decoding, in accordance with aspects of the disclosure. 
       FIG. 4  illustrates an example process  400  for performing sign testing on encrypted data, according to one example implementation. In one embodiment, the process  400  can be performed by the service provider  112  and/or the computing device  102  of  FIG. 1 . However, processes can be performed in other environments and by other devices as well. 
     In general, the process  400  includes performing sign testing on encrypted data to determine if the encrypted data represents a positive number or a negative number. This process provides an additional homomorphic operation that can be performed on encrypted data, thereby providing additional tools for applications. Further, this operation improves a functioning of a computer by quickly providing sign testing and by providing an encrypted result. 
     At  402 , the operation determines a plaintext modulus T 2  (i.e., a plaintext modulus T*T). This operation can include determining the plaintext modulus T, which can be set to be larger than any coefficient appearing in any plaintext polynomial at any point in the computations (e.g., coefficients in a “fresh” polynomial, or in a polynomial after operations have been performed, such as addition and/or multiplication). As is discussed below, the plaintext polynomial T 2  is provided to perform operations involved in the sign testing. 
     At  404 , the operations can constrain nε[0, T−1]. That is to say, the value(s) to be encoded/encrypted can be constrained between 0 and T−1, which is less than the maximum possible range provided by the plaintext modulus T 2 . Further, the encryption scheme can encode values within the range constrained above such that 
             [     positive   ❘   negative     ]                   0   ⁢           ⁢     T   2     ⁢           ⁢   T     -   1     ,         
which is to say that numbers between 0 and T/2 (not including T/2) can be encoded as positive numbers and numbers between T/2 and T−1 (not including T/2) can be encoded as negative number, or the like. Further, it can be understood in the context of this disclosure that the operations  402  and/or  404  can be performed by the parameter selection module  118  in the service provider  112  of FIG.  1  to generate parameters, which can be sent to the client computing device for subsequent encoding and encrypting of the data to be operated on. Further, the operation  404  can include an operation of sending parameters (such as the plaintext modulus T 2  and the constraint that values to be encoded be nε[0, T−1]) to the computing device after the parameters have been determined and/or generated.
 
     At  406 , the operation can encrypt values to be operated on using parameters determined by the parameter selection module  118 , including the plaintext modulus T 2 . Further, the operation  406  can include an operation of receiving parameters (such as the plaintext modulus T 2  and the constraint that nε[0, T−1]) at the computing device after the parameters have sent by the service provider  112 , for example, and the operation  406  can include sending the encrypted values to the service provider after the encryption has been performed at the computing device, for example, in accordance with  FIG. 2 . 
     At  408 , the operation can divide a ciphertext coefficient-wise by T. For example, for a polynomial encrypted as a n T 2 x n +a n−1 T 2 x n−1 + . . . a 1 T 2 x 1 +n+a 0 T 2 , dividing the polynomial coefficient-wise by T results in 
                 a   n     ⁢     Tx   n       +       a     n   -   1       ⁢     Tn     n   -   1         +   …   +       a   1     ⁢     Tx   1       +     n   T     +       a   0     ⁢     T   .             
In some instances, the ciphertext polynomials include coefficients where each coefficient is a large non-zero number close to the size of the modulus Q, which is used in encoding the plaintext data prior to encryption, and is a large prime number. In some embodiments, the modulus Q can determine a coefficient space in a polynomial ring and/or a dimension of a lattice, which can determine a degree of polynomial to be handled. As a result of dividing the polynomial coefficient-wise by T, the coefficients are slightly smaller (roughly Q/T).
 
     At  410 , the operation determines the constant coefficient 
             n   T         
from the polynomial determined in the operation  408 . In some embodiments, the constant coefficient can be isolated from the ciphertext by its position in the polynomial, as understood in the context of the encryption scheme.
 
     At  412 , the operation rounds the constant coefficient 
             n   T         
to the nearest integer. For example, because of the constraint that nε[0, T−1], the constant coefficient
 
             n   T         
will be between 0 and 1, in this encryption scheme. Thus, the operation  412  returns a result of 0 or 1, depending on the value of n, and the rounding at the boundary. Furthermore, as described above, because the encryption scheme encodes positive values between 0 to T/2, and negative values between T/2 and T−1, at operation  414 , the operation determines the sign testing of whether n is a positive value or a negative value. That is to say, if
 
               n   T     =   0         
then n is positive, while if
 
                 n   T     =   1     ,         
then n is negative. In this manner, sign testing is provided as an operation within the homomorphic encryption system.
 
     Furthermore, one or more additional operations can be performed on the polynomial determined in the operation  408  between ciphertexts of plaintext modulus T (instead of T 2 ). Further, the operation  414  can include transmitting the encrypted result to the computing device for decryption and decoding, in accordance with aspects of the disclosure. 
       FIG. 5  illustrates an example process  500  for performing comparison testing on encrypted data, according to one example implementation. In one embodiment, the process  500  can be performed by the computation module  120  in the service provider  112  of  FIG. 1 . However, processes can be performed in other environments and by other devices as well. Further, process  500  can be used either singularly or in combination with the various systems and/or techniques discussed herein. As may be understood in the context of this disclosure, the process  500  can include any additional steps of receiving and/or transmitting parameters, encoding and/or encrypting data based at least in part on the parameters, transmitting and/or receiving encoded and/or encrypted data to/from the service provider, performing homomorphic operations on the data, and transmitting and/or receiving an encrypted/encoded result. 
     In general, the process  500  includes performing a comparison testing between at least two encrypted values to determine if one value is larger than another value. This process provides an additional homomorphic operation that can be performed on encrypted data, thereby providing additional tools for applications. Further, this operation improves a functioning of a computer by quickly providing comparison testing and by providing an encrypted result 
     At  502 , the operation determines a difference between a first encrypted number n 1  and a second encrypted number n 2 . As illustrated in  FIG. 5 , this operation can be represented as encrypt(n 1 )−encrypt(n 2 ). 
     At  504 , the operation determines a sign of the difference. For example, the sign of the difference may be determined using the sign testing described in connection with  FIG. 4  on the result obtained in the operation  502 . 
     At  506 , the operation determines if the difference between encrypt(n 1 )−encrypt(n 2 ) is positive or negative, based at least in part on the determination made in the operation  504 . For example, if n 1 &lt;n 2 , then the difference will be negative, while if n 1 &gt;n 2 , then the difference will be positive. In this manner, the sign testing, described in  FIG. 4 , can be combined with various homomorphic operations to build powerful tools within the homomorphic encryption scheme. 
       FIG. 6  illustrates an example process  600  for performing equality testing on encrypted data, according to one example implementation. In one embodiment, the process  600  can be performed by the computation module  120  in the service provider  112  of  FIG. 1 . However, processes can be performed in other environments and by other devices as well. Further, process  600  can be used either singularly or in combination with the various techniques and/or systems discussed herein. As may be understood in the context of this disclosure, the process  600  can include any additional steps of receiving and/or transmitting parameters, encoding and/or encrypting data based at least in part on the parameters, transmitting and/or receiving encoded and/or encrypted data to/from the service provider, performing homomorphic operations on the data, and transmitting and/or receiving an encrypted/encoded result. 
     In general, the process  600  includes performing an equality testing between at least two encrypted values to determine if one value is equal to another value. This process provides an additional homomorphic operation that can be performed on encrypted data, thereby providing additional tools for applications. Further, this operation improves a functioning of a computer by quickly providing equality testing and by providing an encrypted result. 
     At  602 , the operation determines a first difference between a first encrypted number n 1  and a second encrypted number n 2 . As illustrated in  FIG. 6 , this operation can be represented as encrypt(n 1 )−encrypt(n 2 ). 
     At  604 , the operation determines if the sign of the first difference (determined in the operation  602 ) is positive. As may be understood in the context of this disclosure, the operation  604  can use the sign testing operation described in connection with  FIG. 4  to determine the sign of the result determined in the operation  602 . Thus, if the sign of the first difference is positive, this indicates that n 1 ≧n 2 . 
     At  606 , the operation determines a second difference between the second encrypted number n 2  and the first encrypted number n 1 . As illustrated in  FIG. 6 , this operation can be represented as encrypt(n 2 )−encrypt(n 1 ). 
     At  608 , the operation determines if the sign of the second difference (determined in the operation  606 ) is positive. As may be understood in the context of this disclosure, the operation  608  can use the sign testing operation described in connection with  FIG. 4 . Thus, if the sign of the second difference is positive, this indicates that n 2 ≧n 1 . 
     At  610 , the operation determines whether the first and second encrypted numbers are equal, that is to say, whether n 1 =n 2 . Thus, by performing a two-way comparison testing in the operations  602 ,  604 ,  606 , and  608 , equality testing can be performed on the first and second encrypted numbers, n 1  and n 2 , without the homomorphic encryption scheme knowing the values of the number or the result of the equality testing because the values and the results remain encrypted. 
     Moving forward, the equality testing and comparison testing can be combined to perform frequency counting on encrypted data. For example, performing a frequency count within a number set includes determining a number of occurrences that a value is present in the number set (e.g., a number of values above zero, a number of values equal to a particular number, etc.). After selecting a target number, for each number in the number set, the process can include performing equality testing between that particular number and the target number. Next, the total amount of numbers matching the target value can be determined as the frequency count. In this manner, the tools discussed herein can be combined to provide additional operations within the homomorphic encryption scheme. 
     Therefore, as described herein, optimized homomorphic operations can be performed on encrypted data without revealing the data and/or the result of the operations to the remote computing device in the homomorphic encryption system. Further, these homomorphic operations improve operation of a computer by improving processing and/or memory requirements for the homomorphic encryption by providing additional operations to be performed on encrypted data. Further, the optimizing of parameters and encodings discussed herein can also be used outside the strict context of homomorphic encryption applications, in any application where secure computations are required. 
     EXAMPLE CLAUSES 
     Example A, at least one device comprising: one or more processors; and memory storing modules that, when executed by the one or more processors, cause the at least one device to perform operations comprising: determining a plaintext modulus based on at least one homomorphic operation to be performed; receiving an encrypted polynomial representing at least one number, the encrypted polynomial encrypted based at least in part on the plaintext modulus; dividing the encrypted polynomial by a divisor of the plaintext modulus to generate an encrypted divided polynomial, the dividing performed coefficient-wise on at least one coefficient of the encrypted polynomial, the dividing including rounding the at least one coefficient according to a rounding scheme; and transmitting the encrypted divided polynomial to a computing device. 
     Example B, the at least one device of Example A, wherein the dividing the encrypted polynomial by the divisor of the plaintext modulus avoids a homomorphic multiplication operation, thereby reducing a processing time of the one or more processors when performing the dividing. 
     Example C, the at least one device of Example A or Example B, wherein the operations further comprise constraining the at least one number to a range smaller than the plaintext modulus divided by the divisor. 
     Example D, the at least one device of any one of Examples A through C, wherein the operations further comprise: determining a constant coefficient term of the encrypted divided polynomial; and decrypting the constant coefficient term of the encrypted divided polynomial at the computing device, wherein the constant coefficient term of the encrypted divided polynomial indicates whether the at least one number is a positive number or a negative number upon decrypting the encrypted divided polynomial. 
     Example E, the at least one device of any one of Examples A through D, wherein the rounding scheme rounds the at least one coefficient divided by the divisor of the plaintext modulus to a nearest integer. 
     Example F, the at least one device of any one of Examples A through E, wherein the at least one homomorphic operation includes at least one of an approximate division, a sign testing, a comparison testing, and an equality testing. 
     Example G, the at least one device of any one of Examples A through F, wherein the plaintext modulus is a plaintext modulus T 2 , wherein the divisor is a divisor T, and wherein the operations further comprise performing a homomorphic operation on the encrypted divided polynomial using a plaintext modulus T. 
     Example H, the at least one device of any one of Examples A through G, wherein the operations further comprise: determining a difference between a first encrypted polynomial and a second encrypted polynomial, wherein the difference is the encrypted polynomial representing the at least one number; determining a constant coefficient term of the encrypted divided polynomial; and decrypting the constant coefficient term of the encrypted divided polynomial at the computing device, wherein the constant coefficient term of the encrypted divided polynomial indicates that a first number encrypted as the first encrypted polynomial is larger than a second number encrypted as the second encrypted polynomial upon decrypting the encrypted divided polynomial. 
     While Example A through Example H are described above with respect to a device, it is understood in the context of this document that the content of Example A through Example H may also be implemented via a system, computer storage media, and/or a method. 
     Example I, a computer-implemented method for performing at least one homomorphic encryption operation by at least one processor, the method comprising: determining a plaintext modulus based on at least one homomorphic operation to be performed; receiving an encrypted polynomial representing at least one number, the encrypted polynomial encrypted based at least in part on the plaintext modulus; dividing the encrypted polynomial by a divisor of the plaintext modulus to generate an encrypted divided polynomial, the dividing performed coefficient-wise on at least one coefficient of the encrypted polynomial, the dividing including rounding the at least one coefficient according to a rounding scheme; and transmitting the encrypted divided polynomial to a computing device. 
     Example J, the method of Example I, further comprising constraining the at least one number to a range smaller than the plaintext modulus divided by the divisor. 
     Example K, the method of Example I or Example J, further comprising: determining a constant coefficient term of the encrypted divided polynomial; and decrypting the constant coefficient term of the encrypted divided polynomial at the computing device, wherein the constant coefficient term of the encrypted divided polynomial indicates whether the at least one number is a positive number or a negative number upon decrypting the encrypted divided polynomial. 
     Example L, the method of any one of Examples I through K, wherein the rounding scheme rounds the at least one coefficient to a nearest integer. 
     Example M, the method of any one of Examples I through L, wherein the at least one homomorphic operation includes at least one of an approximate division, a sign testing, a comparison testing, and an equality testing. 
     Example N, the method of any one of Examples I through M, wherein the plaintext modulus is a plaintext modulus T 2 , wherein the divisor is a divisor T, and wherein the method further comprises performing a homomorphic operation on the encrypted divided polynomial using a plaintext modulus T. 
     Example O, the method of any one of Examples I through N, further comprising: determining a difference between a first encrypted polynomial and a second encrypted polynomial, wherein the difference is the encrypted polynomial representing the at least one number; determining a constant coefficient term of the encrypted divided polynomial; and decrypting the constant coefficient term of the encrypted divided polynomial at the computing device, wherein the constant coefficient term of the encrypted divided polynomial indicates that a first number encrypted as the first encrypted polynomial is larger than a second number encrypted as the second encrypted polynomial upon decrypting the encrypted divided polynomial. 
     While Example I through Example O are described above with respect to a method, it is understood in the context of this document that the content of Example I through Example O may also be implemented via a device, system, and/or computer storage media. 
     Example P, one or more computer storage media comprising computer-executable instructions that, when executed by one or more processors, perform operations comprising: determining a plaintext modulus based on at least one homomorphic operation to be performed; transmitting the plaintext modulus to a computing device; receiving an encrypted polynomial representing at least one number, the encrypted polynomial encrypted based at least in part on the plaintext modulus; dividing the encrypted polynomial by a divisor of the plaintext modulus to generate an encrypted divided polynomial, the dividing performed coefficient-wise on at least one coefficient of the encrypted polynomial, the dividing including rounding the at least one coefficient according to a rounding scheme; and transmitting the encrypted divided polynomial to the computing device. 
     Example Q, the one or more computer storage media as recited in Example P, wherein the operations further comprise constraining the at least one number to a range smaller than the plaintext modulus divided by the divisor. 
     Example R, the one or more computer storage media as recited in Example P or Example Q, wherein the rounding scheme rounds the at least one coefficient to a nearest integer. 
     Example S, the one or more computer storage media as recited in any one of Examples P through R, wherein the plaintext modulus is a plaintext modulus T 2 , wherein the divisor is a divisor T, and wherein the operations further comprise performing a homomorphic operation on the encrypted divided polynomial using a plaintext modulus T. 
     Example T, the one or more computer storage media as recited in any one of Examples P through S, wherein the operations further comprise: determining a difference between a first encrypted polynomial and a second encrypted polynomial, wherein the difference is the encrypted polynomial representing the at least one number; determining a constant coefficient term of the encrypted divided polynomial; and decrypting the constant coefficient term of the encrypted divided polynomial at the computing device, wherein the constant coefficient term of the encrypted divided polynomial indicates that a first number encrypted as the first encrypted polynomial is larger than a second number encrypted as the second encrypted polynomial upon decrypting the encrypted divided polynomial. 
     While Example P through Example T are described above with respect to a computer storage media, it is understood in the context of this document that the content of Example P through Example T may also be implemented via a device, system, and/or a method. 
     CONCLUSION 
     Although the present disclosure can use language that is specific to structural features and/or methodological operations, the disclosure is not limited to the specific features or operations described herein. Rather, the specific features and operations are disclosed as illustrative forms of implementing the disclosure.