RNS-BASED CKKS VARIANT WITH MINIMAL RESCALING ERROR

Abstract

Methods and systems for reducing noise in homomorphic multiplication include: receiving a plurality of ciphertexts, each having a corresponding level; receiving data specifying a homomorphic multiplication on two ciphertexts; for two ciphertexts having different levels: adjusting a scaling factor of a first ciphertext so that the respective scaling factors of the two ciphertexts are the same; performing the homomorphic multiplication; and rescaling a result of the homomorphic multiplication; for two ciphertexts having the same level: performing the homomorphic multiplication; rescaling a result of the homomorphic multiplication; and using the scaling factors of the two ciphertexts during a decryption process.

Claims

1. A method for reducing noise in homomorphic multiplication operations on ciphertext data, the method comprising: receiving a plurality of ciphertexts, wherein each ciphertext has a corresponding level of a plurality of levels; receiving data specifying a homomorphic multiplication operation to be performed on two ciphertexts of the plurality of ciphertexts; for two ciphertexts having different corresponding levels: adjusting a scaling factor of a first ciphertext of the two ciphertexts so that the respective scaling factors of the two ciphertexts are the same; performing the specified homomorphic multiplication operation on the adjusted first ciphertext and a second ciphertext of the two ciphertexts; and rescaling a result of the specified homomorphic multiplication operation; for two ciphertexts having the same corresponding levels: performing the specified homomorphic multiplication operation on the two ciphertexts; rescaling a result of the specified homomorphic multiplication operation; and using the scaling factors of the two ciphertexts during a decryption process.

2. The method of claim 1, wherein the step of adjusting a scaling factor of a first ciphertext of the two ciphertexts comprises adjusting the scaling factor of the ciphertext with the highest corresponding level among corresponding levels of the two ciphertexts.

3. The method of claim 1, wherein the scaling factor of a ciphertext having corresponding level i of the plurality of levels is given by SF.sub.i and the scaling factor of level i−1 is defined recursively as ${\mathrm{SF}}_{i-1}=\frac{{\mathrm{SF}}_i^2}{q_i}$ wherein the q.sub.i are the prime towers of a residue number system (RNS) used in an encryption of the ciphertext.

4. The method of claim 3, wherein SF.sub.l, the scaling factor of the highest corresponding level l, is equal to 2.sup.p for some predefined p∈.

5. The method of claim 3, wherein SF.sub.l, the scaling factor of the highest corresponding level l, is equal to q.sub.l.

6. The method of claim 3, wherein adjusting the scaling factor of the first ciphertext of the two ciphertexts comprises multiplying the first ciphertext by an adjustment factor, wherein the adjustment factor a.sub.adj for scaling factor SF.sub.k is equal to: $a_{\mathrm{adj}}=\frac{q_k.Math.{\mathrm{SF}}_{k-i}}{{\mathrm{SF}}_k^2}$ when k−i is the corresponding level of the second ciphertext of the two ciphertexts.

7. The method of claim 1, wherein rescaling a resulting ciphertext of the specified homomorphic multiplication operation is performed using a rescaling operation given by $c^{\prime }=.Math.q_l^{-1}.Math.c.Math.\left(\mathrm{mod}\frac{Q_l}{q_l}\right)$ wherein c is a resulting ciphertext of the specified homomorphic multiplication operation to be rescaled, c′ is a rescaled ciphertext, and Q.sub.l=Π.sub.i=0.sup.l q.sub.i is a ciphertext modulus, which is a product of all prime numbers q.sub.i that comprise a residue number system (RNS) used in an encryption of the plurality of ciphertexts.

8. A method for choosing residue number system moduli, comprising: TABLE-US-00004  receiving an n, an L and a p;  setting a q.sub.L as the first prime number occurring between n and p;  setting a q.sub.next equal to q.sub.L;  setting a q.sub.prev equal to q.sub.L;  setting an sf.sub.L equal to q.sub.L;  setting an sf.sub.L−1 equal to q.sub.L;  setting a ctr equal to 0;  for each of an i = L − 2, ... , 1:   $\mathrm{setting}{\mathrm{sf}}_i\mathrm{equal}\mathrm{to}\frac{{\left({\mathrm{sf}}_{i+1}\right)}^2}{q_{i+1}};$    for ctr mod 2 equal to 0:     updating q.sub.prev to equal └sf.sub.i┐ − 2n − [└sf.sub.i┐].sub.2n + 1     setting a q.sub.i equal to the previous prime number occurring outside the range q.sub.prev to n;    for ctr mod 2 different from 0:     updating q.sub.next to equal └sf.sub.i┐ + 2n − [└sf.sub.i┐].sub.2n + 1     setting a q= equal to the next prime number occurring inside the range q.sub.next to n;   updating ctr = ctr + 1;  setting a q.sub.0 equal to the previous prime number occurring outside the range p.sub.0 to n, wherein p.sub.0 is a predefined value greater than p; and  returning a value of q, wherein the value of q is a product of each q.sub.i.

9. The method of claim 8, wherein p.sub.0 is based on a native word length of a computer processor.

10. The method of claim 1, wherein the plurality of ciphertexts are encrypted using residue number system moduli generated by the method of claim 8.

11. A system for reducing noise in homomorphic multiplication operations on ciphertext data, the system comprising at least one processor and a memory containing instructions which, when executed by the at least one processor, cause the at least one processor to: receive a plurality of ciphertexts, wherein each ciphertext has a corresponding level of a plurality of levels; receive data specifying a homomorphic multiplication operation to be performed on two ciphertexts of the plurality of ciphertexts; for two ciphertexts having different corresponding levels: adjust a scaling factor of a first ciphertext of the two ciphertexts so that the respective scaling factors of the two ciphertexts are the same; perform the specified homomorphic multiplication operation on the adjusted first ciphertext and a second ciphertext of the two ciphertexts; and rescale a result of the specified homomorphic multiplication operation; for two ciphertexts having the same corresponding levels: perform the specified homomorphic multiplication operation on the two ciphertexts; rescale a result of the specified homomorphic multiplication operation; and use the scaling factors of the two ciphertexts during a decryption process.

12. The system of claim 11, wherein the processor is configured to adjust the scaling factor of the ciphertext with the highest corresponding level among corresponding levels of the two ciphertexts.

13. The system of claim 11, wherein the scaling factor of a ciphertext having corresponding level i of the plurality of levels is given by SF.sub.i and the scaling factor of level i−1 is defined recursively as ${\mathrm{SF}}_{i-1}=\frac{{\mathrm{SF}}_i^2}{q_i}$ wherein the q.sub.i are the prime towers of a residue number system (RNS) used in an encryption of the ciphertext.

14. The system of claim 13, wherein SF.sub.i, the scaling factor of the highest corresponding level l, is equal to 2.sup.p for some predefined p∈.

15. The system of claim 13, wherein SF.sub.l, the scaling factor of the highest corresponding level l, is equal to q.sub.l.

16. The system of claim 13, wherein adjusting the scaling factor of the first ciphertext of the two ciphertexts comprises multiplying the first ciphertext by an adjustment factor, wherein the adjustment factor a.sub.adj for scaling factor SF.sub.k is equal to: $a_{\mathrm{adj}}=\frac{q_k.Math.{\mathrm{SF}}_{k-i}}{{\mathrm{SF}}_k^2}$ when k−i is the corresponding level of the second ciphertext of the two ciphertexts.

17. The system of claim 11, wherein the processor is configured to rescale a resulting ciphertext of the specified homomorphic multiplication operation using a rescaling operation given by $c^{\prime }=.Math.q_l^{-1}.Math.c.Math.\left(\mathrm{mod}\frac{Q_l}{q_l}\right)$ wherein c is a resulting ciphertext of the specified homomorphic multiplication operation to be rescaled, c′ is a rescaled ciphertext, and Q.sub.l=Π.sub.i=0.sup.l q.sub.i is a ciphertext modulus, which is a product of all prime numbers q.sub.i that comprise a residue number system (RNS) used in an encryption of the plurality of ciphertexts.

18. A system for choosing residue number system moduli, the system comprising at least one processor and a memory containing instructions which, when executed by the at least one processor, cause the at least one processor to: TABLE-US-00005  receive an n, an L and a p;  set a q.sub.L as the first prime number occurring between n and p;  set a q.sub.next equal to q.sub.L,  set a q.sub.prev equal to q.sub.L;  set an sf.sub.L equal to q.sub.L;  set an sf.sub.L−1 equal to q.sub.L;  set a ctr equal to 0;  for each of an i = L − 2, ... , 1:   $\mathrm{set}{\mathrm{sf}}_i\mathrm{equal}\mathrm{to}\frac{{\left({\mathrm{sf}}_{i+1}\right)}^2}{q_{i+1}};$    for ctr mod 2 equal to 0:     updating q.sub.prev to equal └sf.sub.i┐ − 2n − [└sf.sub.i┐].sub.2n + 1     set a q.sub.i equal to the previous prime number occurring outside the range q.sub.prev to n;    for ctr mod 2 different from 0:     update q.sub.next to equal └sf.sub.i┐ + 2n − [└sf.sub.i┐].sub.2n + 1     set a q.sub.i equal to the next prime number occurring inside the range q.sub.next to n;   update ctr = ctr + 1;  set a q.sub.0 equal to the previous prime number occurring outside the range p.sub.0 to n, wherein p.sub.0 is a predefined value greater than p; and  return a value of q, wherein the value of q is a product of each q.sub.i.

19. The system of claim 18, wherein p.sub.0 is based on a native word length of the at least one processor.

20. The system of claim 11, wherein the plurality of ciphertexts are encrypted using residue number system moduli generated by the system of claim 18.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0027] Non-limiting examples of embodiments of the disclosure are described below with reference to figures attached hereto. Dimensions of features shown in the figures are chosen for convenience and clarity of presentation and are not necessarily shown to scale. The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may be understood by reference to the following detailed description when read with the accompanied drawings. Embodiments are illustrated without limitation in the figures, in which like reference numerals indicate corresponding, analogous, or similar elements, and in which:

[0028] FIG. 1 is a block diagram of an exemplary computing device which may be used with embodiments of the present invention;

[0029] FIG. 2 is a flowchart of a method, according to some embodiments of the invention;

[0030] FIG. 3 is a flowchart of a method, according to some embodiments of the invention; and

[0031] FIG. 4 is schematic drawing of a system, according to some embodiments of the invention.

[0032] It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements.

DETAILED DESCRIPTION

[0033] In general, embodiments of the invention can provide a CKKS-RNS algorithm which can eliminate or reduce an approximation error of rescaling and/or can achieve good performance and/or high accuracy. Embodiments of the CKKS-RNS algorithm may be referred to as “CKKS-RNS-EXACT”.

[0034] FIG. 1 shows a block diagram of an exemplary computing device which may be used with embodiments of the present invention. Computing device 100A may include a controller or computer processor 105A that may be, for example, a central processing unit processor (CPU), a chip or any suitable computing device, an operating system 115A, a memory 120A, a storage 130A, input devices 135A and output devices 140A such as a computer display or monitor displaying for example a computer desktop system.

[0035] Operating system 115A may be or may include code to perform tasks involving coordination, scheduling, arbitration, or managing operation of computing device 100A, for example, scheduling execution of programs. Memory 120A may be or may include, for example, a Random Access Memory (RAM), a read only memory (ROM), a Flash memory, a volatile or non-volatile memory, or other suitable memory units or storage units. At least a portion of Memory 120A may include data storage housed online on the cloud. Memory 120A may be or may include a plurality of different memory units. Memory 120A may store for example, instructions (e.g., code 125A) to carry out a method as disclosed herein. Memory 120A may use a datastore, such as a database.

[0036] Executable code 125A may be any application, program, process, task, or script. Executable code 125A may be executed by controller 105A possibly under control of operating system 115A. For example, executable code 125A may be, or may execute, one or more applications performing methods as disclosed herein, such as a machine learning model, or a process providing input to a machine learning model. In some embodiments, more than one computing device 100A or components of device 100A may be used. One or more processor(s) 105A may be configured to carry out embodiments of the present invention by for example executing software or code.

[0037] Storage 130A may be or may include, for example, a hard disk drive, a floppy disk drive, a compact disk (CD) drive, a universal serial bus (USB) device or other suitable removable and/or fixed storage unit. Data described herein may be stored in a storage 130A and may be loaded from storage 130A into a memory 120A where it may be processed by controller 105A. Storage 130A may include cloud storage. Storage 130A may include storing data in a database.

[0038] Input devices 135A may be or may include a mouse, a keyboard, a touch screen or pad or any suitable input device or combination of devices. Output devices 140A may include one or more displays, speakers and/or any other suitable output devices or combination of output devices. Any applicable input/output (I/O) devices may be connected to computing device 100A, for example, a wired or wireless network interface card (NIC), a modem, printer, a universal serial bus (USB) device or external hard drive may be included in input devices 135A and/or output devices 140A.

[0039] Embodiments of the invention may include one or more article(s) (e.g., memory 120A or storage 130A) such as a computer or processor non-transitory readable medium, or a computer or processor non-transitory storage medium, such as for example a memory, a disk drive, or a USB flash memory encoding, including, or storing instructions, e.g., computer-executable instructions, which, when executed by a processor or controller, carry out methods disclosed herein.

[0040] Encrypted numbers in the CKKS scheme can be large (e.g., multiple hundreds of bits in size). Two known options for implementing the CKKS scheme on a modern computer system are as follows. First, CKKS may be implemented using a software library that provides multi-precision arithmetic and supports large numbers directly. Second, CKKS may be implemented using a technique called multi-modular arithmetic. The multi-modular arithmetic technique, also known as a residue number system (RNS), can involve representing relatively large numbers (e.g., 65-bit or greater) as a set of relatively smaller (e.g., 64-bit) numbers, and performing operations on these small numbers directly.

[0041] Multi-precision arithmetic can incur a significant computational overhead for one or more operations between large numbers. Since small (e.g., 64-bit) numbers typically fit into a native word size of modern computers, RNS based implementations of CKKS may achieve order-of-magnitude performance improvements compared to the multi-precision implementations and can be preferred for most practical applications.

[0042] Lattice cryptography in an RLWE setting can work on integer numbers. However, CKKS is typically intended to be used with real numbers. To support real numbers in RLWE, embodiments of the invention can scale real numbers up and/or use fixed-precision arithmetic. For example, real number 1.2345 may be scaled up by Δ=10.sup.6 and become 1234500. The number Δ used to scale up by is called the scaling factor; according to some embodiments, all operations are performed on numbers scaled-up by A, and the result is scaled back down by Δ.sup.−1 to return to the original real domain. For example, according to some embodiments, after encoding and encryption, a vector of real numbers [m.sub.1, m.sub.2, . . . , m.sub.N] becomes a vector of integer numbers [Δm.sub.1+e.sub.1,Δm.sub.2+e.sub.2, . . . ,Δm.sub.N+e.sub.N]. In other words, even though encryption noise e.sub.i is added for security, it is treated as a small error incurred on the underlying data.

[0043] Embodiments of the invention may reduce noise growth (e.g., accumulation of errors) in homomorphically encrypted data. Noise growth may be understood by the following example, where given two numbers Δm.sub.1+e.sub.1 and Δm.sub.2+e.sub.2, their product typically has considerably more noise than each number individually: (Δm.sub.1+e.sub.1)(Δm.sub.2+e.sub.2)=Δ.sup.2m.sub.1m.sub.2+e, where the noise is e=Δm.sub.1e.sub.2+Δm.sub.1e.sub.1+e.sub.1e.sub.2 with e>>e.sub.i because Δm.sub.i>>e.sub.i. If noise growth is not controlled in some way, a series of successive multiplications can make noise exponentially larger and corrupt the least significant bits of the intended result of the computation. Corrupting the least significant bits of the intended results can result in an inaccurate decryption.

[0044] Encryption noise growth (e.g., exponential encryption noise growth) may be prevented by using a rescaling operation which can reduce the accumulated error and/or render noise growth linear instead of exponential.

[0045] An example of a conventional rescaling operation which takes a ciphertext c and rescales it to a ciphertext c′ is given in EQN. 1 as shown below:

[00009]$\begin{array}{cc}{c}^{\prime }=.Math.2^{-p}.Math.c.Math.\left(\mathrm{mod}\frac{Q_l}{2^p}\right)& \mathrm{EQN}.1\end{array}$

[0046] In EQN. 1, the scaling factor Δ=2.sup.p, the notation [*] means to take the nearest integer value, and Q.sub.l=Δ.sup.l=2.sup.l.Math.p is the ciphertext modulus.

[0047] As an example, if c is an encryption of Δ.sup.2m.sub.1m.sub.2, then c′ will be a valid encryption of message Δm.sub.1m.sub.2.

[0048] Since rescaling according to EQN. 1 can involve a division by Δ=2.sup.p, it can eliminate p least significant bits of c. These least significant bits can contain the encryption error et described above, and so the effect of rescaling can be to greatly reduce the accumulated error in a ciphertext. Some error survives the rescaling operation, but the overall result is that error increases linearly with every multiplication and not exponentially. A side effect of the rescaling operation is that the ciphertext modulus decreases by 2.sup.p, and therefore only l rescaling operations may be performed on a freshly encrypted ciphertext. This value l may be referred to as the corresponding “level” of the ciphertext.

[0049] FIG. 2 is a flowchart of a method 200 for reducing (e.g., via computing device 100A shown in FIG. 1 herein) noise in homomorphic operations on ciphertext data, according to some embodiments of the invention.

[0050] According to some embodiments, method 200 includes receiving a plurality of ciphertexts, wherein each ciphertext has a corresponding level of a plurality of levels (Step 202).

[0051] The ciphertexts may be encrypted using homomorphic encryption schemes known in the art. A corresponding level of a ciphertext may quantify how many homomorphic operations, such as homomorphic multiplication, have been performed on that ciphertext. A corresponding level of a ciphertext may decrease after each homomorphic operation performed on that ciphertext.

[0052] According to some embodiments, method 200 includes receiving (e.g., via computing device 100A shown in FIG. 1) data specifying a homomorphic multiplication operation to be performed on two ciphertexts of the plurality of ciphertexts (Step 204). It will be appreciated by one skilled in the art that method 200 may also be applicable to homomorphic multiplication operations for more than two ciphertexts: for example for three ciphertexts a, b, c the result a.Math.b may be calculated according to embodiments of the invention and then the result may be multiplied by c, again according to embodiments of the invention.

[0053] The homomorphic multiplication operation may be, for example, EvalMult, and may multiply the two (or more) ciphertexts together.

[0054] According to some embodiments, method 200 includes, for two ciphertexts having different corresponding levels, adjusting a scaling factor of a first ciphertext of the two ciphertexts so that the respective scaling factors of the two ciphertexts are the same (Step 206).

[0055] A scaling factor of a ciphertext may be received as part of metadata of the plurality of ciphertexts. The scaling factor of a ciphertext may differ between ciphertexts of the plurality of ciphertexts: for example a first ciphertext may have a first scaling factor and a second ciphertext may have a second scaling factor.

[0056] According to some embodiments, the step (e.g., Step 206) of adjusting the scaling factor of the first ciphertext of the two ciphertexts includes adjusting the scaling factor of the ciphertext with a highest corresponding level among corresponding levels of the two ciphertexts. For example, in a homomorphic operation (e.g., a multiplication) between a first ciphertext having a first scaling factor at level 5 of the plurality of levels and a second ciphertext having a second scaling factor at level 3 of the plurality of levels, embodiments of the invention can involve adjusting the first scaling factor because in this example, this scaling factor belongs to the ciphertext having the higher corresponding level among the two ciphertexts involved in the operation.

[0057] According to some embodiments, for two ciphertexts having different corresponding levels, method 200 includes performing the specified homomorphic multiplication operation on the adjusted first ciphertext (e.g., adjusted according to Step 206) and the second ciphertext (e.g., the ciphertext with unadjusted scaling factor) of the two ciphertexts (Step 208).

[0058] According to some embodiments, for two ciphertexts having different corresponding levels, method 200 includes rescaling a result of the specified homomorphic multiplication operation (Step 210).

[0059] In some embodiments, a modified rescaling operation as described above in EQN. 1 is performed. A modification may be beneficial because, for example, in the CKKS-RNS scheme all moduli of the RNS can be prime numbers and can be different. In some embodiments, rescaling can occur by dividing the modulus Q.sub.l by something other than 2.sup.p every time. To approximate the effect of the CKKS-MP rescaling operation in CKKS-RNS, in some embodiments, the prime RNS moduli is picked to be as close to 2.sup.p as possible (e.g., using techniques described in detail herein.) Given this choice of moduli, the rescaling operation in CKKS-RNS may be, for example, described below in EQN. 2:

[00010]$\begin{array}{cc}{c}^{\prime }=.Math.q_l^{-1}.Math.c.Math.\left(\mathrm{mod}\frac{Q_l}{q_l}\right)& \mathrm{EQN}.2\end{array}$

[0060] In EQN. 2, Q.sub.l=Π.sub.i=0.sup.l q.sub.i is the ciphertext modulus, which is the product of all prime numbers q.sub.i that comprise the RNS system. The RNS system and constituent primes may be generated by methods disclosed herein, for example using pseudocode as shown in Table 2 below corresponding to method 300 shown in FIG. 3.

[0061] Since the ciphertext modulus Q.sub.l may not be a power of the scaling factor Δ, it may not be possible to divide by Δ=2.sup.p every time a rescaling is to be performed. Instead, a division by prime q.sub.i can be performed, which can be different (e.g., a different q.sub.i having different index i) every additional time a rescaling is performed on a given ciphertext. This can result in a rescaling in RNS incurring an approximation error to c′; instead of, for example, being an encryption of Δm.sub.1m.sub.2, c′ it can be an encryption of

[00011]$\frac{{\Delta }^2}{q_l}{m}_1{m}_2=f.Math.\Delta m_1{m}_2,$

where f is a factor equal to

[00012]$\frac{\Delta }{q_l}.$

CKKS-RNS can have smaller approximation error when the factor is closer to 1, i.e., when q.sub.l is chosen to be as close to A as possible. However, in most practical settings, it may not be possible to select q.sub.i's that are all very close to A and the rescaling approximation error of CKKS-RNS is generally larger than the encryption noise in a ciphertext. Therefore, even though CKKS-RNS can be faster than CKKS-MP, it typically incurs larger error, making it, for example, unsuitable for computations that require a high degree of precision. Like the non-RNS version, the number of rescale operations is limited by the number of primes comprising Q.sub.l. The number of primes comprising Q.sub.l (e.g., in the product Q.sub.l=Π.sub.i=0.sup.l q.sub.i) can be referred to the “number of towers in Q.sub.l”, and a ciphertext with modulus Q.sub.l is can be at level l and can have all towers, a ciphertext with modulus Q.sub.l-1 can be at level l−1 and can have one tower less, and so on.

[0062] The rescaling operation of Step 210 may be a rescaling operation as described by, for example, EQN. 2.

[0063] According to some embodiments, for two ciphertexts having the same corresponding levels, method 200 includes performing the specified homomorphic multiplication operation on the two or more ciphertexts (Step 212). In other words, for homomorphic operations (e.g., multiplication) between ciphertexts belonging to the same level, no adjustment of the respective scaling factors may be necessary prior to performing the operation. The scaling factors may be recorded (e.g., stored in memory 120A or storage 130A of computing device 100A shown in FIG. 1) for later use, such as during decryption.

[0064] According to some embodiments, for two ciphertexts having the same corresponding levels, method 200 includes rescaling a result of the specified homomorphic multiplication operation (Step 214). The rescaling operation may be a rescaling operation as described by, for example, EQN. 2.

[0065] According to some embodiments, for two ciphertexts having the same corresponding levels, method 200 includes using the scaling factors of the two ciphertexts during a decryption process (Step 216).

[0066] The scaling factors may have been recorded, e.g., stored in memory 120A or storage 130A shown in FIG. 1A, for later adjustment of the result of the operation during decryption, and may thereby, for example, reduce a noise in the result.

[0067] A benefit of embodiments of the invention can be that factor f may not depend on the encrypted data. Instead, the factor f can be a function of the scaling factor Δ of a ciphertext, and the moduli q.sub.i can be selected to setup the RNS system. Therefore, it can be possible to compute factor f and/or use EvalMult to homomorphically multiply the ciphertext by a.sub.adj=Δ/f to adjust its scaling factor back to the one originally intended of A. In these embodiments, the approximation error of rescaling can be cancelled, and CKKS-RNS-EXACT rescaling can become as accurate (or almost as accurate) as CKKS-MP (e.g., some rounding error may still exist but is minimal compared to the unadjusted approximation error of CKKS-RNS).

[0068] However, using EvalMult after every rescale operation may have disadvantages. The result of EvalMult can be rescaled in order to, for example, prevent noise growth, which can imply that the depth of the computation can also be increased.

[0069] In some embodiment, instead of performing EvalMult after every rescale, a correct scaling factor can be kept track of (e.g., by recording or storing the scaling factor in a memory or storage, such as memory 120A or storage 130A of computing device 100A shown in FIG. 1) and used when decrypting (e.g., as described in Step 216). This may ensure an accurate result, without having to perform an additional rescale operation during the computation. However, even when using this approach, there may still some cases where scaling factors are adjusted. Operations between ciphertexts with different scaling factors (e.g., because the ciphertext has previously been involved in an operation and is at a different associated level) may not work, unless it is ensured their scaling factors match. In some embodiments, keeping track of scaling factors can be desirable over adjusting after every rescale operation (e.g., operations between ciphertexts of the same scaling factor, even if that scaling factor is not the original Δ).

[0070] To increase the occasions where the scaling factors of ciphertexts match, embodiments of the invention can include ciphertexts of a given level sharing the same scaling factor. To maintain this invariant, two measures can be taken.

[0071] The first measure taken can include for setting up scaling factors of each level to follow the “natural” order of rescale operations. For instance, if the scaling factor at level l (e.g., when no rescale operation has been performed) is Δ, the scaling factor of level l−1 (e.g., after one rescale operation) is Δ.sup.2/q.sub.l. It should be noted that this can be exactly the same scaling factor obtained if a rescale operation is performed after a multiplication of two ciphertexts of the same level l. Table 1 illustrates an example of the scaling factors of a computation that involves five levels (e.g., l=5). Note that setting Δ=q.sub.l can avoid error altogether for the first rescaling operation.

TABLE-US-00001 TABLE 1 Prime tower dropped Scaling factor after Level with rescaling Scaling factor multiplication 5 q.sub.5 Δ = q.sub.5 Δ.sup.2 4 q.sub.4 Δ.sup.2/q.sub.5 = q.sub.5 Δ.sup.4/q.sub.5.sup.2 3 q.sub.3 Δ.sup.4/q.sub.5.sup.2 .Math. q.sub.4 Δ.sup.8/q.sub.5.sup.4 .Math. q.sub.4.sup.2 2 q.sub.2 Δ.sup.8/q.sub.5.sup.4 .Math. q.sub.4.sup.2 .Math. q.sub.3 Δ.sup.16/q.sub.5.sup.8 .Math. q.sub.4.sup.4 .Math. q.sub.3.sup.2 1 N/A Δ.sup.16/q.sub.5.sup.8 .Math. q.sub.4.sup.4 .Math. q.sub.3.sup.2 .Math. q.sub.2 Δ.sup.32/q.sub.5.sup.16 .Math. q.sub.4.sup.8 .Math. q.sub.3.sup.4 .Math. q.sub.2.sup.2

[0072] The second measure taken can be to enforce the correct order of rescale operations, by performing them, for example, automatically after every multiplication. Users are typically not responsible for calling the rescale method themselves—the CKKS-RNS-EXACT implementation can perform both rescaling and scaling factor adjustment.

[0073] According to some embodiments, when ciphertexts are at different levels (e.g., have different scaling factors) the scaling factor of at least one ciphertext is adjusted so that each respective scaling factor among the ciphertexts is the same. For example, if ciphertext c.sub.1 is at level k and ciphertext c.sub.2 is at level k−i, then embodiments of the invention adjust their scaling factors so that they match before performing the specified homomorphic operation (e.g., multiplication). There is no need to adjust both scaling factors: one scaling factor can be adjusted to match the scaling factor of the other. According to some embodiments, the scaling factor of the ciphertext that has the higher level is adjusted. By doing so, the “natural” scaling factor order is maintained and avoids incurring an extra level in the overall computation.

[0074] Thus, according to some embodiments, for two ciphertexts encrypting numbers SF.sub.km.sub.1 and SF.sub.k-im.sub.2, EQN. 4 describes how to perform an adjustment on the scaling factor of SF.sub.km.sub.1.

[00013]$\begin{array}{cc}\mathrm{Rescale}\left(\mathrm{EvalMult}\left({\mathrm{SF}}_k{m}_1,a_{\mathrm{adj}}\right)\right)=\mathrm{Rescale}\left(a_{\mathrm{adj}}.Math.{\mathrm{SF}}_k^2{m}_1\right)=a_{\mathrm{adj}}.Math.\frac{{\mathrm{SF}}_k^2}{q_k}{m}_1& \mathrm{EQN}.4\end{array}$

[0075] The procedure according to Equation 4 is to first multiply the ciphertext with the adjustment factor a.sub.adj and then rescale by dropping tower q.sub.k.

[0076] Since the term

[00014]$a_{\mathrm{adj}}.Math.\frac{{\mathrm{SF}}_k^2}{q_k}{m}_1$

should match the scaling factor of SF.sub.k-i of the other ciphertext, this implies that the adjustment factor a.sub.adj is given as:

[00015]$\begin{array}{cc}{a}_{\mathrm{adj}}=\frac{q_k.Math.{\mathrm{SF}}_{k-i}}{{\mathrm{SF}}_k^2}& \mathrm{EQN}.5\end{array}$

It should be noted that if instead of SF.sub.k-i the second ciphertext had a scaling factor of SF.sub.k-i.sup.2 (e.g. because a different encoding was used), then embodiments of the invention would perform the adjustment without the rescale operation, for example as:

EvalMult(SF.sub.km.sub.1,a.sub.adj)=a.sub.adj.Math.SF.sub.k.sup.2m.sub.1  EQN. 6

[0077] In such a case the adjustment factor becomes:

[00016]$\begin{array}{cc}{a}_{\mathrm{adj}}=\frac{{\mathrm{SF}}_{k-i}^2}{{\mathrm{SF}}_k^2}& \mathrm{EQN}.7\end{array}$

[0078] One or more embodiments of the invention relate to a method for selecting the prime towers q.sub.i of the RNS system for the CKKS-RNS-EXACT scheme.

[0079] FIG. 3 is a flowchart of a method 300 for choosing residue number system moduli, according to some embodiments of the invention. Method 300 may be performed, for example, by a computing device such as computing device 100A shown in FIG. 1.

[0080] According to some embodiments, method 300 includes receiving an n, an L and a p (Step 302). The received n, L and p may be natural numbers, and may be selected by a user based on the needs of the application.

[0081] According to some embodiments, method 300 includes setting a q.sub.L as the first prime number occurring between n and p (Step 304). The first prime number may be determined using a known function, such as a FirstPrime(a,b) function which determines the first prime number in the range a to b.

[0082] According to some embodiments, method 300 includes setting a q.sub.next equal to q.sub.L, setting a q.sub.prev equal to q.sub.L, setting an sf.sub.L equal to q.sub.L, and setting an sf.sub.L-1 equal to q.sub.L (Step 306). This step may represent an initialization step, preparing parameter values which may later be updated.

[0083] According to some embodiments, method 300 includes setting a ctr equal to 0 (Step 308). The parameter ctr may represent a counter, counting a number of iterations.

[0084] According to some embodiments, method 300 includes looping for each of an i=L−2, . . . , 1 and setting sf.sub.i equal to

[00017]$\frac{{\left({\mathrm{sf}}_{i+1}\right)}^2}{q_{i+1}}$

(Step 310).

[0085] According to some embodiments, whilst still in the for loop for i=L−2, . . . , 1, method 300 includes, for the case where ctr mod 2 equals zero, updating q.sub.prev to equal [sf.sub.i]−2n−[└sf.sub.i┐].sub.2n+1 (Step 312). As used herein, the notation [*].sub.2n denotes taking the 2n.sup.th root of the sum of the vector elements, each vector element raised to the 2n.sup.th power.

[0086] According to some embodiments, whilst still in the for loop for i=L−2, . . . , 1, and still for the case where ctr mod 2 equals zero, method 300 includes setting a q.sub.i equal to the previous prime number occurring outside the range q.sub.prev to n (Step 314). The previous prime number may be determined using a known function, such as a PreviousPrime(a,b) function which determines the previous prime number outside the range a to b.

[0087] According to some embodiments, whilst still in the for loop for i=L−2, . . . , 1, method 300 includes, for the case where ctr mod 2 is not equal to (e.g., different from) zero, updating q.sub.next to equal └sf.sub.i┐+2n−[└sf.sub.i┐].sub.2n+1 (Step 316).

[0088] According to some embodiments, whilst still in the for loop for i=L−2, . . . , 1, and still for the case where ctr mod 2 is different from zero, method 300 includes setting a q.sub.i equal to the next prime number occurring inside the range q.sub.next to n (Step 318). The next prime number may be determined using a known function, such as a NextPrime(a,b) function which determines the next prime number inside the range a to b.

[0089] According to some embodiments, after each i in the loop is considered, method 300 may include updating ctr=ctr+1, in other words increasing a value of the counter after each iteration.

[0090] According to some embodiments, method 300 includes setting a q.sub.0 equal to the previous prime number occurring outside the range p.sub.0 to n, wherein p.sub.0 is a predefined value greater than p (Step 322).

[0091] The value p.sub.0 may represent a word length (e.g., based on a native word length of a computer processor) for efficient modular operations predefined by the user. For example, in embodiments which use PALISADE (an open-source cross platform software library that provides implementations of lattice cryptography building blocks and homomorphic encryption schemes), p.sub.0 maybe set equal to 60, because for 64-bit native words, PALISADE supports efficient modular operations up to 60 bits.

[0092] According to some embodiments, method 300 includes returning a value of q, wherein the value of q is a product of each q.sub.i (Step 324), e.g. q=Π.sub.i=0.sup.L-2 q.sub.i. The value q may therefore be the modulus of the RNS system.

[0093] Ciphertexts used in some embodiments may be encrypted using the RNS system produced by method 300. For example, the ciphertexts of method 200 may be encrypted using the RNS system of moduli generated by method 300.

[0094] Table 2 shows example pseudocode for choosing residue number system moduli, according to some embodiments of the invention, for example, method 300.

TABLE-US-00002 TABLE 2   SelectModuli(n, l, p, p.sub.0) q.sub.l := FirstPrime(p, n) q.sub.next := q.sub.l q.sub.prev := q.sub.l SF.sub.l := q.sub.l; SF.sub.l−1 := q.sub.l ctr := 0  for i = l − 2, l − 3, ... , 1   [00018]$S{F}_i:=\frac{{\left(S{F}_{i+1}\right)}^2}{q_{i+1}}$   if ctr mod 2 = 0    q.sub.prev = └SF.sub.i┐ − 2n − [└SF.sub.i┐] .sub.2n + 1    q.sub.t := PreviousPrime(q.sub.prev, n)   else    q.sub.prev = └SF.sub.i┐ + 2n − [└SF.sub.i┐] .sub.2n + 1    q.sub.t = NextPrime(q.sub.next, n)   ctr := ctr + 1  q.sub.0 := PreviousPrime(p.sub.0, n)  return q

[0095] Table 3 shows example scaling factors obtained using the recursion relation described in EQN. 3, if (i) a conventional moduli selection algorithm and (ii) a moduli selection algorithm according to embodiments of the invention is used. The example is for an RNS system with 30 primes, in other words 30 levels of homomorphic computation.

TABLE-US-00003 TABLE 3 Scaling factors Ratio to q30 Scaling factors Ratio to q30 Level (Conventional) (Conventional) (Embodiments) (Embodiments) 30 1125899908022270 1 1125899908022270 1 20 1125901149538390 1.000001103 1125899919034520 1.00000001 10 1127173721789190 1.001131374 1125899946195380 1.000000034 0 3583898673668410 3.183141457 1125902283235330 1.00000211

[0096] It can be observed that, even though the first scaling factor (e.g., at level 30) is the same for both algorithms, the subsequent scaling factors can be different to the point that the final scaling factor for the conventional moduli selection algorithm is about three times larger than the original scaling factor and the scaling factor obtained using the moduli selection algorithm.

[0097] Having diverging scaling factors (e.g., becoming much larger or smaller than the original) can be a problem because precision may be eventually lost, for example, by underflow (e.g., if the scaling factors become too small), or overflow (e.g., if they become too large). The moduli selection algorithm according to embodiments of the invention enables the use of CKKS-RNS-EXACT for deeper computations.

[0098] One or more embodiments of the invention relate to a system the system comprising at least one processor (e.g., processor/controller 105A shown in FIG. 1) and a memory (e.g., memory 120A shown in FIG. 1) containing instructions (e.g., executable code 125A shown in FIG. 1) which, when executed by the at least one processor, cause the at least one processor to carry out methods described herein.

[0099] FIG. 4 is a schematic drawing of a system 100 according to some embodiments of the invention. System 100 may include one or more server(s) 110, database(s) 115, and/or computer(s) 140, 150, . . . , etc. Any or all of system 100 devices may be connected via one or more network(s) 120. Network 120, which connects server(s) 110 and computers 140 and 150, may be any public or private network such as the Internet. Access to network 120 may be through wire line, terrestrial wireless, satellite or other systems well known in the art.

[0100] Server(s) 110 and computers 140 and 150, may include one or more controller(s) or processor(s) 116, 146, and 156, respectively, for executing operations according to embodiments of the invention and one or more memory unit(s) 118, 148, and 158, respectively, for storing data (e.g., encryption and/or decryption keys, and encrypted and/or decrypted data) and/or instructions (e.g., software for applying computations or calculations, keys to encrypt or decrypt data according to embodiments of the invention) executable by the processor(s). Processor(s) 116, 146, and/or 156 may include, for example, a central processing unit (CPU), a digital signal processor (DSP), a microprocessor, a controller, a chip, a microchip, an integrated circuit (IC), or any other suitable multi-purpose or specific processor or controller. Memory unit(s) 118, 148, and/or 158 may include, for example, a random access memory (RAM), a dynamic RAM (DRAM), a flash memory, a volatile memory, a non-volatile memory, a cache memory, a buffer, a short term memory unit, a long term memory unit, or other suitable memory units or storage units.

[0101] Computers 140 and 150 may be servers, personal computers, desktop computers, mobile computers, laptop computers, and notebook computers or any other suitable device such as a cellular telephone, personal digital assistant (PDA), video game console, etc., and may include wired or wireless connections or modems. Computers 140 and 150 may include one or more input devices 142 and 152, respectively, for receiving input from a user (e.g., via a pointing device, click-wheel or mouse, keys, touch screen, recorder/microphone, other input components). Computers 140 and 150 may include one or more output devices 144 and 154 (e.g., a monitor or screen) for displaying data to a user provided by or for server(s) 110.

[0102] Database 115 may include software processes or applications for storing and retrieving data 117 such as large-word data structures and large-work CKKS computations, and/or encryption and/or decryption keys. Data 117 may also include code (e.g., software code) or logic, e.g., to enable the application of large-work CKKS algorithms according to embodiments of the invention. Database 115 may be internal or external to one or more of server(s) 110 and/or computer(s) 140 and/or 150 (not shown) and may be connected thereto by a local or remote and a wired or wireless connection. In some embodiments, data 117 is stored in an alternate location separate from database 115, e.g., memory unit(s) 118, 148, and/or 158.

[0103] Any of system 100 devices may operate as a secure or insecure party. Secure parties may each securely store unencrypted (or encrypted) data and private keys associated with each dataset, party, etc. Insecure parties may not access the unencrypted data or private keys.

[0104] Unless specifically stated otherwise, as apparent from the foregoing discussion, it is appreciated that throughout the specification discussions utilizing terms such as “processing,” “computing,” “calculating,” “determining,” or the like, refer to the action and/or processes of a computer or computing system, or similar electronic computing device, that manipulates and/or transforms data represented as physical, such as electronic, quantities within the computing system's registers and/or memories into other data similarly represented as physical quantities within the computing system's memories, registers or other such information storage, transmission or display devices.

[0105] Embodiments of the invention may include an article such as a computer or processor readable non-transitory storage medium, such as for example a memory, a disk drive, or a USB flash memory encoding, including, or storing instructions, e.g., computer-executable instructions, which when executed by a processor or controller, cause the processor or controller to carry out methods disclosed herein.

[0106] It should be recognized that embodiments of the invention may solve one or more of the objectives and/or challenges described in the background, and that embodiments of the invention need not meet every one of the above objectives and/or challenges to come within the scope of the present invention. While certain features of the invention have been particularly illustrated and described herein, many modifications, substitutions, changes, and equivalents may occur to those of ordinary skill in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes in form and details as fall within the true spirit of the invention.

[0107] In the above description, an embodiment is an example or implementation of the inventions. The various appearances of “one embodiment,” “an embodiment” or “some embodiments” do not necessarily all refer to the same embodiments.

[0108] Although various features of the invention may be described in the context of a single embodiment, the features may also be provided separately or in any suitable combination. Conversely, although the invention may be described herein in the context of separate embodiments for clarity, the invention may also be implemented in a single embodiment.

[0109] Reference in the specification to “some embodiments”, “an embodiment”, “one embodiment” or “other embodiments” means that a particular feature, structure, or characteristic described in connection with the embodiments is included in at least some embodiments, but not necessarily all embodiments, of the inventions.

[0110] It is to be understood that the phraseology and terminology employed herein is not to be construed as limiting and are for descriptive purpose only.

[0111] The principles and uses of the teachings of the present invention may be better understood with reference to the accompanying description, figures, and examples.

[0112] It is to be understood that the details set forth herein do not construe a limitation to an application of the invention.

[0113] Furthermore, it is to be understood that the invention may be carried out or practiced in various ways and that the invention may be implemented in embodiments other than the ones outlined in the description above.

[0114] It is to be understood that the terms “including”, “comprising”, “consisting” and grammatical variants thereof do not preclude the addition of one or more components, features, steps, or integers or groups thereof and that the terms are to be construed as specifying components, features, steps, or integers.

[0115] If the specification or claims refer to “an additional” element, that does not preclude there being more than one of the additional elements.

[0116] It is to be understood that where the claims or specification refer to “a” or “an” element, such reference is not to be construed that there is only one of that element.

[0117] It is to be understood that where the specification states that a component, feature, structure, or characteristic “may”, “might”, “may” or “could” be included, that a particular component, feature, structure, or characteristic is not required to be included.

[0118] Where applicable, although state diagrams, flow diagrams or both may be used to describe embodiments, the invention is not limited to those diagrams or to the corresponding descriptions. For example, flow need not move through each illustrated box or state, or in exactly the same order as illustrated and described.

[0119] Methods of the present invention may be implemented by performing or completing manually, automatically, or a combination thereof, selected steps or tasks.

[0120] The descriptions, examples, methods and materials presented in the claims and the specification are not to be construed as limiting but rather as illustrative only.

[0121] Meanings of technical and scientific terms used herein are to be commonly understood as by one of ordinary skill in the art to which the invention belongs, unless otherwise defined. The present invention may be implemented in the testing or practice with methods and materials equivalent or similar to those described herein.

[0122] While the invention has been described with respect to a limited number of embodiments, these should not be construed as limitations on the scope of the invention, but rather as exemplifications of some of the preferred embodiments. Other possible variations, modifications, and applications are also within the scope of the invention. Accordingly, the scope of the invention should not be limited by what has thus far been described, but by the appended claims and their legal equivalents.