US 12,701,002 B2Grant

Method of optimizing linear transformation

Issue Date:2026-08-04

•21 Claims

•6 Drawing Sheets

Abstract

A method and system for optimizing compute runtime and memory footprint of a linear transformation process are provided. The method includes determining a set of optimal rotation parameters, wherein the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process; initializing the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, wherein the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, and wherein the at least one iteration is based on the determined set optimal rotation parameters and at least one key switching key (KSK); and loading the initialized linear transformation process to an internal memory of a hardware accelerator.

Metadata

Assignee

Chain Reaction, Ltd.

Inventors

Oren Vrubel
Noam Kleinburd
Ilan Rosenfeld

Application Information

Application Number:US 18/789,018

Filing Date:2024-07-30

Priority Date:2024-03-22

Art Unit:2437

Classifications

IPC:

H04L9/30G06F21/57H04L9/00

Field of Search:

H04L 9/3026H04L 9/008G06F 21/575G06F 2221/034

Patent Drawings (6 sheets)

Description

Cross-Reference to Related Applications

[0001] This application claims the benefit of U.S. Provisional Application No. 63/568,472 filed on Mar. 22, 2024, the contents of which are hereby incorporated by reference.

Technical Field

[0002] The present disclosure relates generally to fully homomorphic encryption (FHE) schemes and, more specifically, to a linear transformation.

Background

[0003] FHE enables computations on encrypted data without needing to decrypt it first. The Cheon-Kim-Kim-Song (CKKS) scheme is one of the encryption methods used in FHE, particularly well-suited for dealing with arithmetic on complex numbers. The core feature of FHE is performing computations on encrypted data. With CKKS, one can perform addition, subtraction, and multiplication on ciphertexts. These operations correspond to similar operations on the original plaintext numbers. To make the scheme more efficient, a sequence of values can be encrypted into a single ciphertext, this sequence can be rotated. Importantly, CKKS allows for these operations to be performed with relatively low noise growth, which is a significant challenge in FHE. As operations are performed on ciphertexts, noise within the encrypted data accumulates. If the noise grows too large, it can make the decrypted result incorrect. CKKS also manages this noise by scaling down ciphertexts after multiplications.

[0004] The CKKS scheme includes a technique for controlling this noise called Rescaling, which also reduces the size of the ciphertext. When the size of a ciphertext reaches a threshold, the bootstrapping process can be applied. The bootstrapping process refreshes the ciphertext, increasing its size and enabling more computations to be performed. Bootstrapping is a crucial process that allows FHE schemes to practically perform an unlimited number of homomorphic computations on encrypted data.

[0005] CKKS is a potent FHE scheme, enabling arithmetic operations on approximate number vectors of length n. The scheme supports various operations such as addition, multiplication, scalar-by-vector multiplication, and rotation, among others. Operands can be plaintexts, ciphertexts, or a combination of both. Complex vector data is encoded into polynomials with integer coefficients modulo a chosen modulus, which is then encrypted into an array of such polynomials. Homomorphic operations involve arithmetic between polynomials, with efficient multiplication achieved through the Number Theoretical Transform (NTT) domain, also known as Evaluation-mode. Due to high modulus values, Residue-Number-System (RNS) representation is used to reduce complexity.

[0006] Each multiplication operation in CKKS consumes RNS residues, requiring decryption and re-encryption to maintain homomorphic arithmetic precision. An alternative, “bootstrapping” refreshes multiple RNS levels without decryption. The bootstrapping process is a complex process involving Coefficient-to-Slots (C2S) transformation, Sine Evaluation, and Slots-to-Coefficients (S2C) transformation. C2S and S2C transformations are similar to homomorphic Inverse Discrete Fourier Transform (IDFT) and Discrete Fourier Transform (DFT) evaluations, respectively. Both C2S and S2C transformations utilize auxiliary-data represented by matrices of complex powers of a root of unity, with the same format.

[0007] The related art describes a number of techniques to perform the linear transformation in the case of the bootstrapping process. FIG. 1 illustrates steps of a bootstrapping process 100 typically involves three major steps. The first step, 110, is the coefficients to slots (C2S) step, followed by a polynomial evaluation (Sine) 120, and the final step is the slots to coefficients (S2C) step 130. In an FHE scheme, an encrypted message is presented as a polynomial. The C2S step 110 homomorphically evaluates the inverse discrete-Fourier-transform (IDFT) and produces a ciphertext that can be evaluated. The Sine step 120 implements the homomorphic modular reduction on the ciphertext. The modular reduction is approximated by a sinusoidal (Sine) function, which scales the message down and produces a remainder polynomial of the modular operation (typically modulo 1). Then, the message is scaled back. The scheme parameters determine the range and degree of the approximation, where the Sine step 120 has to account for the secret-key density ‘h’. The S2C step 130 homomorphically evaluates the DFT on the ciphertext to revert to approximately the original encrypted message.

[0008] The bootstrapping process is a crucial part of an application that performs FHE operations. Such a process is executed to ensure that noise resulting from operations does not grow too large, which may lead to an incorrect decrypted result. The frequency of executing the bootstrapping process is determined by the application programmer and must be frequent enough to maintain the accuracy of the decrypted result.

[0009] Bootstrap processing as well as other processes of FHE operations utilize linear transformation algorithms. Linear transformation may be a linear function used on encrypted data without decrypting it, which is useful for privacy-preserving computations in various applications, such as cloud computing and secure data analysis. Additionally, linear transformation algorithms can be used in applications, such as Linear Regression, Logistic Regression, Convolutional Neural Networks, and Large Language Models.

[0010] Generally, linear transformation processes are complex and require a significant amount of computational and memory resources. In order to effectively apply FHE schemes, such as bootstrapping, in real-time commercial applications, there is a need to accelerate the linear transformation operation.

[0011] It would, therefore, be advantageous to provide a solution that would minimize the amount of computational and memory resources when executing linear transformation processes.

Summary

[0012] A summary of several example embodiments of the disclosure follows. This summary is provided for the convenience of the reader to provide a basic understanding of such embodiments and does not wholly define the breadth of the disclosure. This summary is not an extensive overview of all contemplated embodiments and is intended to neither identify key or critical elements of all embodiments nor to delineate the scope of any or all aspects. Its sole purpose is to present some concepts of one or more embodiments in a simplified form as a prelude to the more detailed description that is presented later.

[0013] A system of one or more computers can be configured to perform particular operations or actions by virtue of having software, firmware, hardware, or a combination of them installed on the system that in operation causes or cause the system to perform the actions. One or more computer programs can be configured to perform particular operations or actions by virtue of including instructions that, when executed by data processing apparatus, cause the apparatus to perform the actions.

[0014] In one general aspect, method may include determining a set of optimal rotation parameters, where the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process. Method may also include initializing the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, where the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, and where the at least one iteration is based on the determined set optimal rotation parameters and at least one key switching key (KSK). Method may furthermore include loading the initialized linear transformation process to an internal memory of a hardware accelerator. Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods.

[0015] In one general aspect, non-transitory computer-readable medium may include one or more instructions that, when executed by one or more processors of a device, cause the device to: determine a set of optimal rotation parameters, where the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process; initialize the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, where the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, and where the at least one iteration is based on the determined set optimal rotation parameters and at least one key switching key (KSK); and load the initialized linear transformation process to an internal memory of a hardware accelerator. Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods.

[0016] In one general aspect, a system may include one or more processors configured to: determine a set of optimal rotation parameters, where the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process. System may furthermore include initialize the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, where the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, and where the at least one iteration is based on the determined set optimal rotation parameters and at least one key switching key (KSK). System may in addition include load the initialized linear transformation process to an internal memory of a hardware accelerator. Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods.

Brief Description of the Drawings

[0017] The subject matter disclosed herein is particularly pointed out and distinctly claimed in the claims at the conclusion of the specification. The foregoing and other objects, features, and advantages of the disclosed embodiments will be apparent from the following detailed description taken in conjunction with the accompanying drawings.

[0018] FIG. 1 illustrates the steps of a bootstrapping process in an FHE scheme;

[0019] FIG. 2 is an example diagram of a server utilized to explain the various disclosed embodiments;

[0020] FIGS. 3A and 3B are a flowchart diagrams related to a method of optimizing FHE linear transformations for optimizing a bootstrapping process, in accordance with some of the disclosed embodiments;

[0021] FIG. 4 shows a block diagram depicting a boosting technique for ciphertexts rotation, in accordance with some of the disclosed embodiments; and

[0022] FIG. 5 illustrates a scatter plot, of runtime/memory tradeoff, in accordance with some of the disclosed embodiments.

Detailed Description

[0023] It is important to note that the embodiments disclosed herein are only examples of the many advantageous uses of the innovative teachings herein. In general, statements made in the specification of the present application do not necessarily limit any of the various claimed embodiments. Moreover, some statements may apply to some inventive features but not to others. In general, unless otherwise indicated, singular elements may be in plural and vice versa with no loss of generality. In the drawings, like numerals refer to like parts through several views.

[0024] The disclosed subject matter focuses on optimizing Fully Homomorphic Encryption (FHE) programs and bootstrapping processes, particularly in linear transformation. The aim is to enhance the linear transformation by efficiently performing addition, multiplication, and rotation of an unencrypted matrix with an encrypted vector to produce an encrypted output. Key objectives include reducing the external memory bandwidth, memory size, and computational efforts of FHE accelerators. This reduction leads to a smaller chip area and lower power consumption for ASIC accelerators. The disclosed embodiments can be implemented in various FHE schemes, such as CKKS and BGV/BFV, to make linear transformation more efficient for secure computations.

[0025] In the CKKS scheme, a vector x∈ custom character

ⁿof up to n=N/2 complex numbers is encoded into a plaintext polynomial of length N, typically with n in the range of 2¹⁰to 2¹⁶. The encoded plaintext polynomial consists of N=2n integer values modulo Q. This plaintext polynomial can then be encrypted into a ciphertext, which includes two polynomials, each containing N=2n integer values modulo Q. It should be noted that encryption and decryption processes require a key and the notation x∈ custom character

ⁿrepresents a vector of complex numbers, ct=Encrypt(x) stands for ct=Encrypt (Encode(x)), and x=Decrypt(ct) stands for x=Decode (Decrypt(ct)).

[0026] The following are operations supported within this encryption framework.

- [0027] a. Addition of ciphertexts, y=add_ct,ct(ct_A, ct_B) results in Decrypt(y)≈Decrypt(ct_A)+Decrypt(ct_B) adding the decrypted values of two ciphertexts;
- [0028] b. Multiplication of ciphertexts, y=mul_ct,ct(ct_A, ct_B)⇒Decrypt(y)≈Decrypt(ct_A)·Decrypt(ct_B);
- [0029] c. Multiplication between ciphertext and plaintext, y=mul_ct,pt(ct_A, pt*)⇒Decrypt(y)≈Decrypt(ct_A)·Decode(pt*);
- [0030] d. And rotation of a ciphertext, y=rot(ct_A, r)⇒Decrypt(y)[k]≈Decrypt(ct_A)[(k+r) % n] effectively rotating the decrypted vector by r positions.

[0031] These operations facilitate homomorphic encryption, enabling computations on encrypted data without decryption, which is particularly advantageous for ensuring data privacy in secure computation environments like cloud computing.

[0032] An FHE linear transformation is a frequently invoked algorithm or process in FHE computation in general, and in bootstrapping in particular. FHE linear transformation is used to evaluate the multiplication of an unencrypted matrix by an encrypted vector, resulting in an encrypted output. This operation is crucial for bootstrapping in client-to-server and server-to-client communications, as well as various other homomorphic encryption applications. Commercially available demonstrated an algorithm for homomorphic matrix multiplication, which utilizes existing homomorphic operations such as rotation (rot), multiplication of ciphertext and plaintext (mul_ct,pt), and addition of ciphertexts (add_ct,ct). This process is vital for secure computation and the practical implementation of homomorphic encryption.

[0033] The FHE linear transformation process usually involves four steps: 1) encoding diagonals, 2) rotating ciphertext, 3) multiplying diagonals by rotated ciphertext, and 4) summing the products. First, encode the diagonals of matrix A into plaintext polynomials. Next, rotate the ciphertext vector X to align with each diagonal. Then, multiply each diagonal by the corresponding rotated ciphertext and sum the results. For example, matrix A and vector X include encoding each diagonal, rotating X by the required positions, multiplying the encoded diagonals by the rotated ciphertexts, and summing these products. This process typically involves n−1 rotations and n ciphertext-plaintext multiplications; however, the computational effort can be reduced if there are fewer non-zero diagonals.

[0034] Linear transformation process can be summarized as follows:

- [0035] a. Input: Ciphertext ct_x=Encrypt(x∈n), complex matrix A_n×n
- [0036] b. Output: Ciphertext ct_ysuch that y=Decrypt(ct_y)≈Ax
- [0037] c. Process:
  - [0038] i. Encode diagonals of A into n plaintext polynomials {diag₀, diag₁, . . . , diag_n-1}
  - [0039] ii. Calculate the sum of multiplications (SOM):

[0040]

c t_{y} = \sum_{i = 0}^{n - 1} {mul}_{ct, pt} (r o t (c t_{x}, i), {diag}_{i}) i . e .,

using sum add_ct,ct

- - [0041] iii. return ct_y
- [0042] d. Computation difficulty:
  - [0043] i. n−1 rotations and n operations of mul_ct,pt.
  - [0044] ii. Else, when n_nzd<n non-zero diagonals, the computation difficulty is reduced to n_nzd−1 rotations and n_nzdoperations of mul_ct,pt

[0045] FIG. 2 is an example diagram of a server 200 utilized to implement the disclosed embodiments. In some exemplary embodiments, server 200 may be a computerized system adapted to perform methods such as depicted in FIG. 3. Server 200 includes a processing circuitry 210 coupled to a memory 220, a storage 230, a network interface 240, and a FHE card 250. In an embodiment, the components of server 200 may be communicatively connected via a bus 260 such as, for example, a PCIe bus.

[0046] The processing circuitry 210 may be realized as one or more hardware logic components and circuits. 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), system-on-a-chip systems (SOCs), graphics processing units (GPUs), tensor processing units (TPUs), general-purpose microprocessors, microcontrollers, digital signal processors (DSPs), and the like, or any other hardware logic components that can perform calculations or other manipulations of information.

[0047] Memory 220 may be volatile (e.g., random access memory, etc.), non-volatile (e.g., read-only memory, flash memory, etc.), or a combination thereof. Storage 230 may include a non-volatile memory device, magnetic disk drive, optical disk drive, tape drive, and the like. Examples of memory 220 may include EEPROM, ROM, PROM, RAM, DRAM, SRAM, flash, firmware, programmable logic, and so on. Storage 230 may comprise an internal storage device, an attached storage device and/or a network-accessible storage device, and the like. Network interface 240 allows server 200 to communicate with external systems. Various communication protocols can be utilized by the network interface 240.

[0048] The memory 220 and/or storage 230 may store software required to execute an FHE program or application, that is, a software program that requires the execution of an FHE scheme to perform one or more homomorphic operations such as bootstrapping, and linear transformation.

[0049] The FHE program's repetitive execution, such as the linear transformation and bootstrapping processes, which according to the disclosed embodiment, is performed by an FHE accelerator 270 included or embedded in FHE card 250. It should be noted that software shall be construed broadly to mean any type of instructions, whether referred to as software, firmware, middleware, microcode, hardware description language, or otherwise. Instructions may include code (e.g., in source code format, binary code format, executable code format, or any other suitable format of code).

[0050] A FHE card 250 is configured to rapidly perform complex encryption, decryption, and homomorphic operations. In some exemplary embodiments, FHE card 250 performs addition, multiplication, and rotation of unencrypted matrixes with an encrypted vector, producing an encrypted output used during Linear Transformation. FHE card 250 can be installed in server 200 or operate as a standalone device. As noted above, FHE card 250 includes the FHE accelerator 270,

[0051] FHE accelerator 270 includes a processor 271 and an internal memory 272, or several processors with internal memory designed for accelerating FHE scheme computational tasks. Processor 271 may include multiple cores that can handle multiple computation threads simultaneously. Internal memory 272 is a dedicated memory used by processor 271 to store the data for executing the FHE program and routines, such as bootstrapping and linear transformation. Such data may include auxiliary-data, encryption keys, indeterminate data, and the like. Internal memory 272 is a cache memory like, designed for high bandwidth, which means it can read and write data at high speeds, enabling processor 271 to quickly access the data stored therein. In some exemplary embodiments, internal memory 272 may be realized as on-die memory.

[0052] In one embodiment, FHE accelerator 270 can be realized as an ASIC. In other embodiments, FHE accelerator 270 can be realized as an FPGA, an ASSP, a SoC, and the like, or any other hardware logic components that can perform calculations or other manipulations of information.

[0053] FHE card 250 also includes an external memory 257 and a memory bus 258. Memory bus 258 is an interface through which processor 271 communicates with external memory 257. In some exemplary embodiments, external memory 257 may be an SDRAM, high bandwidth SDRAM (e.g., GDDR5, GDDR6), and high bandwidth memory (HBM). In some configurations, FHE card 250 may also include an interface 259 to interface with Bus 260, such as a PCIe.

[0054] In some exemplary embodiments, the size of internal memory 272 may be significantly smaller than the size of External Memory 257. Internal memory 272 may be realized as “on-die” memory, and the data stored therein allows for the efficient execution of an FHE scheme, specifically a bootstrapping process of such a program. For example, the difference between the memory size of the external memory and the internal memory may be the order of magnitude. In current technologies, the size of internal memory 272 is limited to 1 GB. Increasing the size of internal memory 272 would reduce the number of compute resources.

[0055] The disclosed embodiments describe a method for efficient execution of linear transformation process, which consequently impacts the execution of bootstrapping and other FHE programs execution. Additionally, or alternatively, the present disclosure includes computations, such as homomorphic I-DFT and DFT algorithms during the C2S and S2C steps of bootstrapping and evaluation of key switching operations. It should be understood that the embodiments described herein are not limited to the specific architecture illustrated in FIG. 2, and other architectures may be equally used without departing from the scope of the disclosed embodiments.

[0056] It will be appreciated that in FHE, a vector of complex numbers, plaintext polynomial, and ciphertext of any length can have a matrix representation. Such a matrix may be viewed as a three-dimensional (3D) matrix for the mathematical convenience of representing a plurality of diagonals (2D matrices) in the same space. Yet, it should be noted that each diagonal represents a different polynomial, a section of a polynomial, or any combination thereof. When performing matrix operations in FHE, such as matrix multiplication or matrix-vector multiplication, diagonals of matrices may be relevant. This can include various computations and operations, such as multiplication, addition, and rotation performed on encrypted data, ciphertext, plaintext, and the like, or any combination thereof.

[0057] It should be noted that in FHE, computations may employ RNS (Residue Number Systems) that efficiently represent and manipulate encrypted data by performing computations modulo a set of pairwise relatively prime moduli. RNS enhances operations like addition and multiplication. In each diagonal polynomial coefficients are associated with the columns and the residues with the rows of the matrix. Thus, the number of columns may be equal to the number of coefficients, while the number of rows may be equal to the number of residues. For example. a Matrix incorporating a C2S auxiliary-data may have 56 residues (rows), i.e., (L+K) polynomial residues, whereas a matrix incorporating an S2C auxiliary-data may have 28 residues (rows), while in both cases they may have 65536 coefficients (columns).

[0058] It will be appreciated that while the embodiments of linear transformation process described in the present disclosure refer to bootstrapping and FHE operations, the linear transformation process may also be utilized by other programs, such as linear regression, logistic regression, convolutional neural networks, and large language models.

[0059] In FIG. 3A a flowchart diagram of a method 300A of an optimized linear transformation process carried out in accordance with some of the disclosed embodiments. The linear transformation process is executed at runtime where its optimization is performed at the compilation or initialization stage, i.e., before runtime. The optimization of the linear transformation process is discussed in detail in FIG. 3B.

[0060] In some exemplary embodiments, the subject matter discloses a method designed to optimize a linear transformation process derived from the “Baby-step Giant-Step (BSGS) algorithm”. BSGS algorithm was proposed as a part of the “Bootstrapping for HELib” article by Shai Halevi and Victor Shoup, at an annual international conference on the theory and applications of cryptographic techniques. Springer. 2015.

[0061] In some configurations, prior to runtime execution of the liner transformation process, diagonals may be encoded. The diagonal encoding step of BSGS includes two rotation parameters: β (the number of baby steps) and γ (the number of giant steps), where β*γ=n, and n is the number of encoded diagonals. Thus, dividing the diagonals into γ groups of β diagonals each, mathematically expressed: {diag₀, diag₁, . . . diag_β−1}, {diag_β, diag_β+1, . . . diag_2β−1}, . . . {diag_(γ−1)β, diag_(γ−1)β+1, diag_n-1}. Hence, following diagonals of the k^thgroup of a plurality of groups γ are pre-rotated by −kn₁.

[0062] According to the disclosed embodiment, a set of optimal rotation parameters is determined to allow an optimal tradeoff between compute resource and a memory utilization of an internal memory (e.g., memory 272). The various disclosed embodiments for selecting the set of optimal rotation parameters are discussed below. For example, a diagonal encoding step of n=8 diagonals, γ=2 groups, and β=4 diagonals per group, the diagonals of the first group are not rotated, where the diagonals of the second group are rotated by −4 positions. This is further demonstrated in TABLE 1, below.

[0063]

TABLE 1

Group 1	Diagonal 0	a₀₀	a₁₁	a₂₂	a₃₃	a₄₄	a₅₅	a₆₆	a₇₇	0 rot. >	a₀₀	a₁₁	a₂₂	a₃₃	a₄₄	a₅₅	a₆₆	a₇₇
	Diagonal 1	a₀₁	a₁₂	a₂₃	a₃₄	a₄₅	a₅₆	a₆₇	a₇₀	0 rot. >.	a₀₁	a₁₂	a₂₃	a₃₄	a₄₅	a₅₆	a₆₇	a₇₀
	Diagonal 2	a₀₂	a₁₃	a₂₄	a₃₅	a₄₆	a₅₇	a₆₀	a₇₁	0 rot. >	a₀₂	a₁₃	a₂₄	a₃₅	a₄₆	a₅₇	a₆₀	a₇₁
	Diagonal 3	a₀₃	a₁₄	a₂₅	a₃₆	a₄₇	a₅₀	a₆₁	a₇₂	0 rot. >	a₀₃	a₁₄	a₂₅	a₃₆	a₄₇	a₅₀	a₆₁	a₇₂
Group 2	Diagonal 4	a₀₄	a₁₅	a₂₆	a₃₇	a₄₀	a₅₁	a₆₂	a₇₃	rot. by −4>	a₄₀	a₅₁	a₆₂	a₇₃	a₀₄	a₁₅	a₂₆	a₃₇
	Diagonal 5	a₀₅	a₁₆	a₂₇	a₃₀	a₄₁	a₅₂	a₆₃	a₇₄	rot. by −4>	a₄₁	a₅₂	a₆₃	a₇₄	a₀₅	a₁₆	a₂₇	a₃₀
	Diagonal 6	a₀₆	a₁₇	a₂₀	a₃₁	a₄₂	a₅₃	a₆₄	a₇₅	rot. by −4>	a₄₂	a₅₃	a₆₄	a₇₅	a₀₆	a₁₇	a₂₀	a₃₁
	Diagonal 7	a₀₄	a₁₀	a₂₁	a₃₂	a₄₃	a₅₄	a₆₅	a₇₆	rot. by −4>	a₄₃	a₅₄	a₆₅	a₇₆	a₀₄	a₁₀	a₂₁	a₃₂

[0064] In some configurations, the encoding of diagonals is performed during the initialization process of the linear transformation process, thus not during runtime. To this end, the encoded diagonals are pre-loaded to the internal memory of the hardware accelerator, e.g., memory 272 of FHE accelerator 270.

[0065] In S302, the ciphertext may be rotated. The ciphertexts may be rotated β−1 positions per group. Thus, for each group, the ciphertext associated with the first diagonal is rotated 0 positions (no rotation), the ciphertext associated with the second diagonal is rotated 1 position, the ciphertext associated with the third diagonal is rotated 2 positions, and so on until the β^thdiagonal, where its associated ciphertext is rotated β−1 positions. Upon the completion of ciphertext rotations for one group, the rotated ciphertexts can be copied to the remaining groups respectively.

[0066] It should be noted that conventional ciphertext rotation includes phases that are repeated for each rotation, where the number of rotations (r) is determined by the number of baby steps β minus 1, as the first rotation is equal to the input ciphertext (Ct-in). Additionally, ciphertext rotation requires a dedicated Key Switching Key (KSK) for each rotation. Thus, a conventional ciphertext rotation includes (β−1) rotations, where each of which may have a dedicated KSK and its outcome is rotated ciphertext (Ct-out).

[0067] The ciphertext rotation can include the following phases: Digit decomposition, MultSum, Permute, and ModDown.

[0068] In the digit decomposition phase, the coefficients of the input polynomial undergo computations to generate several temporary polynomials in a larger temporary modulus QP. This decomposition is necessary to limit the noise growth resulting from the subsequent multiplication with the Key-Switching-Key (MultSum).

[0069] In the MultSum phase, the decomposed array of polynomials undergoes two inner products, each with a part of the Key-Switching-Key, to obtain a ciphertext decryptable by the desired secret key. This phase consists of several polynomial additions and multiplications. The process is then repeated with one of the inputs changed to generate a second result.

[0070] In the permute phase, the elements of a polynomial that encodes data may be rearranged. This rearrangement is done in a deterministic pattern according to a parameter r to obtain a new polynomial, which encodes the rotation of the original data by r.

[0071] In the ModDown phase, a polynomial with coefficients modulo a large modulus QP undergoes division by P and rounding/flooring/ceiling to obtain a polynomial in the original modulus Q. This is done to enable further key-switching operations.

[0072] Each rotation in the overall ciphertext rotations process includes digit decomposition, MultSum, and Permute computation phases. A first ciphertext polynomial undergoes digit decomposition, yielding an input to the MultSum. Together with the KSK input, the MultSum performs multiplications and additions, producing two polynomials for the Permute phase. This phase obtains one MultSum outcome, and one sum of MultSum with an input polynomial and yields two output ciphertext polynomials (Ct-out).

[0073] It will be noted that the routine detailed above has to be repeated for each rotation. A rotation, including key-switching, requires the following computation:

[0074]

L (3 + d_{num} + \frac{2}{d_{num}}) NTTs and N (L^{2} (1 + \frac{2}{d_{num}}) + 2 L (d_{num} + 2))

multiplications per rotation. For an example d_num=2 there are 6L NTTs and N(2L²+8L) multiplications per one rotation.

[0075] Therefore, it can be concluded that ciphertext rotations pose a significant burden on computational executions, primarily due to the involvement of the Key-Switching procedure.

[0076] According to the disclosed embodiments, a boosting technique configured with one or more of the determined rotation parameters is utilized to perform S302. The disclosed boosting technique is discussed in greater detail below.

[0077] In S303, diagonals are multiplied by rotated ciphertext. Each rotated ciphertext is multiplied by its associated diagonal γ times, i.e., one diagonal per group, where γ is the number of groups.

[0078] According to the example depicted in S302, the product of multiplying diagonals by rotated ciphertext step will yield:

[0079]


Group 1	mul_{pt, ct}	a₀₀x₀	a₁₁x₁	a₂₂x₂	a₃₃x₃	a₄₄x₄	a₅₅x₅	a₆₆x₆	a₇₇x₇
	mul_{pt, ct}	a₀₁x₁	a₁₂x₂	a₂₃x₃	a₃₄x₄	a₄₅x₅	a₅₆x₆	a₆₇x₇	a₇₀x₀
	mul_{pt, ct}	a₀₂x₂	a₁₃x₃	a₂₄x₄	a₃₅x₅	a₄₆x₆	a₅₇x₇	a₆₀x₀	a₇₁x₁
	mul_{pt, ct}	a₀₃x₃	a₁₄x₄	a₂₅x₅	a₃₆x₆	a₄₇x₇	a₅₀x₀	a₆₁x₁	a₇₂x₂
Group 2	mul_{pt, ct}	a₄₀x₀	a₅₁x₁	a₆₂x₂	a₇₃x₃	a₀₄x₄	a₁₅x₅	a₂₆x₆	a₃₇x₇
	mul_{pt, ct}	a₄₁x₁	a₅₂x₂	a₆₃x₃	a₇₄x₄	a₀₅x₅	a₁₆x₆	a₂₇x₇	a₃₀x₀
	mul_{pt, ct}	a₄₂x₂	a₅₃x₃	a₆₄x₄	a₇₅x₅	a₀₆x₆	a₁₇x₇	a₂₀x₀	a₃₁x₁
	mul_{pt, ct}	a₄₃x₃	a₅₄x₄	a₆₅x₅	a₇₆x₆	a₀₇x₇	a₁₀x₀	a₂₁x₁	a₃₂x₂

[0080] It should be noted that the example depicts only 2 groups for the sake of simplifying the explanation herein. However, in a typical linear transformation the number of groups, (γ) may be significantly greater than 2. For further processing, the groups may be assigned an index k, where 0≤k≤γ−1

[0081] In S304, the products may be summed. The products of each group k are summed separately, followed by rotating the SOM (sum of multiplications) of each group by β×k positions, where k is the group index. In an embodiment, S304 is concluded by summing the rotated SOM of all the groups. It should be noted that k of the first group is zero, thus the first group is not rotated. In an embodiment, S304 contiguous accumulation (“ConAcc”) configured based on one or more of the determined rotation parameters is utilized to perform S304. The disclosed ConAcc routine is discussed in greater detail below. It should be noted that whether or not to utilize the ConAcc routine is a configurable parameter (ConAcc activation flag) that is determined as part of the set of optimal rotation parameters.

[0082] In view of the above linear transformation founded on basic BSGS process can be summarized as follows:

- [0083] a. Input: Ciphertext ct_x=Encrypt(x∈ⁿ), matrix A∈^n×n, and integers β, γ such that β=┌n/γ┐
- [0084] b. Output: Ciphertext ct_ysuch that y=Decrypt(ct_y)≈Ax
- [0085] c. Process:
  - [0086] i. Encode the diagonals of matrix A into n plaintext polynomials {diag₀, diag₁, . . . , diag_n-1}
  - [0087] ii.

[0088]

For 0 \leq k \leq γ - 1 calculate {acc}_{k} = \sum_{i = 0}^{β - 1} m u l_{ct, pt} (r o t (c t_{x}, i), ro t ({diag}_{k β + i}, - k β))

- - [0089] iii.

[0090]

Calculate c t_{y} = \sum_{k = 0}^{γ - 1} rot ({acc}_{k}, + k β)

- - [0091] iv. Return ct_y
- [0092] d. Computation effort:
  - [0093] i. Total of β+γ−2 rotations and n operations of mul_ct,pt
  - [0094] ii. Computation effort is reduced if the number of non-zero encoded diagonals n_nzd<n and

[0095]

β = ⌈ \frac{n_{nzd}}{γ} ⌉ .

- [0096] iii. Based on symmetry analysis, computation effort may be minimized by choosing β=γ.

[0097] In summary, a conventional and basic linear transformation operates on a BSGS process, and yields exactly the same results as the process demonstrated in FIG. 3. However, the disclosed linear transformation operated on a BSGS process involves β+γ−2 rotations and n times mul_ct,pt, whereas the conventional linear transformation involves n−1 rotations and n times mul_ct,pt. Therefore, the computational effort difference between the two (i.e., conventional linear transformation algorithm and Halevi's BSGS linear transformation algorithm) is reflected in the number of rotations, since the number of multiplications is similar. The difference between the two can be expressed as: β γ−1>β+γ−2, since n=β*γ. For example, given 8 diagonals, β=4, γ=2 shows the number of rotations is reduced from 7 to 4.

[0098] The technical problems addressed by the disclosed subject matter are the computational efforts and memory footprint associated with rotations, multiplications, and sum operations, as manifested in S302 through S304, as described below. As disclosed herein, the computational efforts and memory footprint are optimized through a determination of the optimal rotational parameters.

[0099] Specifically, each mul_pt,ctoperation includes 2NL multiplications, where N is the number of polynomials in a plaintext, L is the number of residues, and 2 is the number of ciphertexts. Since only n_nzd(nonzero) polynomials are relevant, then the total number multiplications are 2n_nzdNL. However, the operation requires significantly more operations due to the Key-Switching procedure, which comes to a total of

[0100]

L (3 + d_{num} + \frac{2}{d_{num}}) NTTs,

and

N (L^{2} (1 + \frac{2}{d_{num}}) + 2 L (d_{num} + 2))

multiplications (d_numis a residue parameter). For example, for d_num=2 the total operations are 6L NTTs plus N(2L²+8L) multiplications per one rotation, resulting in substantial computational efforts and memory footprint

[0101] Additionally, during a basic BSGS process, β two polynomials ciphertexts are generated. Each of these is multiplied by up to γ plaintexts encoded diagonals. The products are then rotated and summed to obtain the linear transformation result

[0102]

c t_{y} = \sum_{k = 0}^{γ - 1} rot (\sum_{i = 0}^{β - 1} {mul}_{ct, pt} (c t_{i}, {pt}_{k, i}), {GiantStep}_{k}) .

It should be noted that the basic BSGS process operates by generating and storing baby steps, meaning it generates all β ciphertexts, stores them, and only then performs the summation. This approach requires peak intermediate memory of β ciphertexts in addition to at least one ciphertext holding the intermediate sum, leading to a large memory footprint.

[0103] In view of the shortcomings of the basic BSGS process for linear transformation, such cannot meet the technical objective of the present disclosure, which aims to reduce the memory size and computational efforts of hardware accelerators, thereby reducing chip area, and power consumption. This would result in reduced computational complexity, shorter execution times, smaller memory footprint, and reduced memory bandwidth, thereby making linear transformation more efficient.

[0104] One technical solution is employing an innovative technique for classifying optimal parameters for the linear transformation algorithm. In some exemplary embodiments, parameter classification may be determined by evaluating possible parameter combinations that minimize runtime while staying within the memory footprint limit.

[0105] Another technical solution is implementing an innovative Baby-Step Boosting (hereinafter “Boosting”) technique for ciphertext rotations. In some embodiments of the disclosed subject matter, the output of the baby-step stage is a set of β rotated versions of the input ciphertext. The Boosting technique, with parameter bf, performs the ciphertext rotations in ┌(β−1)/bf┐ iterations, numbered i=1 to ┌(β−1)/bf┐. Each iteration takes ciphertext input from the outputs of the previous iteration, and bf key-switching keys, and generates the next bf rotated versions of the ciphertext input. Upon completion of all iterations, β rotated ciphertext outputs are available. This Boosting technique enhances the data-computation tradeoff, consequently optimizing the performance of the linear transformation process.

[0106] Yet another technical solution is implementing the ConAcc routine for sum operations in a linear transformation process, and the like. In some exemplary embodiments, ConAcc starts by setting up γ accumulator ciphertexts, then creates β ciphertexts one at a time. Each time a ciphertext is created, the ConAcc routine updates each of the γ partial sums. This technique uses less intermediate memory since it requires only a number of γ accumulator ciphertexts plus one for the current ciphertext being processed.

[0107] FIG. 3B is an example flowchart 300B of a method for optimizing compute runtime and memory footprint of a linear transformation process according to the disclosed embodiments. The method may be performed during compilation or initializing of an application, such as an FHE application or program. The method may be performed by a processing circuitry that is outside of a hardware accelerator, such as an FHE accelerator. For example, the method may be performed by processing circuitry 210 of server 200 of FIG. 2. The linear transformation process is executed at runtime by a hardware accelerator, such as the FHE accelerator 270 of FIG. 2. The linear transformation process is discussed in FIG. 3 and is configured with a set of optimal rotation parameters.

[0108] As shown in FIG. 3B, the method may include determining a set of optimal rotation parameters (S310). The optimal rotation parameters define an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation.

[0109] The optimal rotation parameters may include determining parameters β, γ, a boosting factor {bf} (to be described in detail further below), and a ConAcc activation flag (i.e., whether or not the ConAcc routine should be used as part of the linear transformation process, as described in detail further below).

[0110] Initially, the linear transformation and hardware constraints of the FHE accelerator (e.g., FHE accelerator 270, FIG. 2) constraints may be defined or obtained:

- [0111] a. Operation: linear transformation of a ciphertext by a matrix with nonzero diagonals.
- [0112] b. Global program parameters: given values of d_numand L.
- [0113] c. Possible parameter values: defined ranges for β, bf, and a Boolean for ConAcc activation flag, such as depicted in the table below.
- [0114] d. Hardware constraints: total memory limit for the hardware processing capabilities, number of accelerators, multipliers, and CPU cores.

[0115] In an embodiment, parameter combinations may be generated:

- [0116] a. Determine all possible combinations of β, γ (where γ=┌n/β┐), and ConAcc.
- [0117] b. Example: For n=128, d_num=2, and L=40: β∈{16,32,64,128}, γ=128/β,bf∈{1,4,8,16}, ConAcc∈{True,False}, which results in a total of 4×4×2=32 configurations.

[0118] In an embodiment, each configuration may be evaluated as part of the program configurations space by computing the runtime for each configuration, which could be measured by the number of NTT operations or the like. Additionally, or alternatively, the total intermediate memory and Key-Switching Key (KSK) memory required for each configuration for evaluating memory footprint.

[0119] In an embodiment, an optimal configuration as part of optimal program configuration may be selected:

- [0120] a. Filter configurations based on the hardware memory constraint (e.g., 200 MB).
- [0121] b. Among the configurations that satisfy the memory constraint, select the one with the shortest program runtime.

[0122] For a linear transformation program example, a given memory limit is 200 MB, the optimal configuration may be β=64, γ=2, bf=4, and ConAcc activation flag=True. This configuration achieves the shortest runtime while meeting the memory constraint.

[0123]

TABLE 2

Config. #	β	γ	bf	ConAcc


1	128	1	1	TRUE
2	64	2	1	TRUE
3	32	4	1	TRUE
4	16	8	1	TRUE
5	128	1	4	TRUE
6	64	2	4	TRUE
7	32	4	4	TRUE
8	16	8	4	TRUE
9	128	1	8	TRUE
10	64	2	8	TRUE
11	32	4	8	TRUE
12	16	8	8	TRUE
13	128	1	16	TRUE
14	64	2	16	TRUE
15	32	4	16	TRUE
16	16	8	16	TRUE
17	128	1	1	FALSE
18	64	2	1	FALSE
19	32	4	1	FALSE
20	16	8	1	FALSE
21	128	1	4	FALSE
22	64	2	4	FALSE
23	32	4	4	FALSE
24	16	8	4	FALSE
25	128	1	8	FALSE
26	64	2	8	FALSE
27	32	4	8	FALSE
28	16	8	8	FALSE
29	128	1	16	FALSE
30	64	2	16	FALSE
31	32	4	16	FALSE
32	16	8	16	FALSE

[0124] The runtime/memory tradeoff of the example in TABLE 2 is depicted in a scatter plot 500 in FIG. 5. Each point in the collection is indexed by its configuration number.

[0125] As also shown in FIG. 3B, method 300B may include programming the Boosting technique with the determined set of optimal rotation parameters (S320). S320 may include setting the Boosting technique with the determined parameters. As noted above the Boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts. The iterations are performed based on the determined set of optimal rotation parameters and at least one key switching key (KSK). The Boosting technique may be executed as part of S302 discussed above. The operation of the Boosting technique is further discussed with reference to FIG. 4.

[0126] In an embodiment, S320 may include setting Boosting technique or the linear transformation process to utilize ConAcc routine based on the value of the ConAcc activation flag. This flag defines if the ConAcc routine should be implemented or not, and the decision is based on the optimal utilization of the internal memory. The ConAcc routine may be executed as part of S303 and S304 discussed above.

[0127] The outcome of S310 and S320 is a complied or initialized linear transformation process that when executed at runtime enables optimal tradeoff between compute resources and a reduced memory footprint on the program level.

[0128] As further shown in FIG. 3B, method 300B may include loading the complied or initialized linear transformation process programmed with the determined set of optimal rotation parameters to an internal memory of a hardware accelerator (S330). In an embodiment, the internal memory is memory 272 of FHE accelerator 270. The determined rotation parameters ensure that the memory required to store at least the KSK for the rotation is less than the size of the internal memory and during runtime, the compute resources of processor 271 are not exhausted.

[0129] It should be understood that the operations described herein cannot be performed using the human mind or by performing the operation using paper and pencil. A human operator applies subjective criteria to select/simulate/predict, leading to results that are not consistent between different human operators, and often not consistent between the same human performing the same task repeatedly, and in particular at the speeds required to provide an operable solution. The number of possible permutations for rotation parameters and parameter values selection, by far exceeds any practical use of the human mind. FIG. 4 shows a block diagram 400 depicting the Boosting technique for ciphertexts rotation, in accordance with some of the disclosed embodiments. In some exemplary embodiments, Boosting 400 includes a plurality of iterations indexed as follows: Iteration #1 (401), Iteration #2 (402), through Iteration #┌(β−1)/bf┐ (403) hereinafter referred to as Iteration 401 through Iteration 403 respectively. In some exemplary embodiments, the iterations are identical except for the last Iteration, i.e., Iteration 403, which differs from the other iterations by lacking ModDown 444 phase.

[0130] In some exemplary embodiments, {bf} is a boosting factor, which may be determined with the optimal rotation parameters. Practically, the boosting factor {bf} defines an optimal number of KSKs to participate in the baby-step stage. This means choosing the best configuration, such as depicted in the example of the table above. the table itemized the number of KSKs that satisfy an optimal compute-data tradeoff and the runtime/memory tradeoff depicted in the example in FIG. 5.

[0131] In some exemplary embodiments, Iteration 401 may be fed by ciphertext input ct₁412, and ciphertext input ct₀411, while the following iterations use a Carry-out Ciphertext (Ct-co_i) 445 generated by the previous iteration as a ciphertext input. Additionally, or alternatively, each iteration may be fed by a total of {bf} Key Switching Keys (KSKs), and together with ciphertext inputs generate the next {bf} rotated versions of ct_in410. After all iterations are generated, a p ciphertexts outputs (ct_out) 446 are available for the linear transformation process (e.g., S303).

[0132] In some exemplary embodiments, the Iterations may include the following phases: Digit decomposition 441, Sum of multiplications (MultSum) 442, Permute 443, and ModDown 444.

[0133] In a digit decomposition 441 phase, coefficients of the input polynomial undergo computations to generate several temporary polynomials in a temporary, larger modulus QP. The decomposition is required in order to limit the noise growth resulting from the following multiplication with the KSK 420 in a MultSum 442 phase.

[0134] In MultSum 442 phase, the decomposed array of polynomials undergoes two inner products, each with a part of the Key-Switching-Key to obtain a ciphertext decryptable by a desired secret key. This phase comprises several polynomial additions and polynomial multiplications. The process is then repeated with one of the inputs changed to generate a second result.

[0135] In some exemplary embodiments, the number of MultSum 442 phases per iteration is dictated by the number of KSKs 420, which is defined by {bf} (practically defining the number of rotations), therefore the indexed KSK₁through KSK_bf. For example, electing configuration #10 from the table above, the number of KSKs will be 8. In some exemplary embodiments, the number of iterations may be defined by

[0136]

⌈ \frac{β - 1}{b f} ⌉ .

According to the same example, there will be 8 iterations. It should be noted that ciphertext inputs ct₁412 and ct₀411 are added to Ct-out as is. In Permute 443, elements of a polynomial that encodes some data may be rearranged. The rearranging is done in a deterministic pattern according to a parameter r to obtain a new polynomial, which encodes the rotation of the original data by r

[0137] In the ModDown phase, a polynomial with coefficients modulo a large modulus QP undergoes division by P and rounding/flooring/ceiling to obtain a polynomial in the original modulus Q. This is done so further key-switching operations can be performed.

[0138] The description above indicates, Iteration 401 obtains and processes two polynomials of a ciphertexts inputs, ct₀411 and ct₁412. Ct₁412 is used as an input to Digit decomposition 441 phase and ct₀411 is added, by an Adder 447, to an outcome of MultSum 442 of Iteration 401. The result of Adder 447 is then fed to Permute 443 phase of Iteration 401.

[0139] It should be noted that the two polynomials of a ciphertexts inputs, ct₀411 is in a modulus Q and some scale. However, the result of the MultSum phase 442 is in a larger modulus QP, and scale larger by P. In some exemplary embodiments, ct₀411 may be first multiplied by the constant P in order to match the scale and modulus of the ct₀411 and the MultSum 442 polynomials.

[0140] In some exemplary embodiments of the Boosting 400 technique, iterations following Iteration 401 conduct a similar process, with the exception of obtaining two ciphertext inputs that are derived from Ct-co_i445 of the previous iteration. In some exemplary embodiments, Ct-co_i445 generates the two ciphertext polynomials from the last Permute 443 and ModDown 444 phases of the previous iteration. For example, Permute (r_bf) and ModDown 444 of Iteration 402 feed Ct-co₂445 that generates the ciphertext inputs for Iteration 403. In light of the above, it is requested that only the MultSum 442 and Permute 440 phases be dependent on the rotation r Therefore, Digit decomposition 441 and ModDown 444 can be computed once and used for all rotations, r₀through r_β−1.

[0141] In some exemplary embodiments, Boosting 400 allows for performing only a single digit decomposition per iteration, as Digit Decomposition 441 does not depend on which rotation is performed. Additionally, Boosting 400 also allows for using only {bf} rotation KSKs, i.e., the optimal number of KSKs. Given the heavy computation burden posed by Digit Decomposition 441, this approach improves the data-computation tradeoff and optimizes overall linear transformation algorithm. It should be noted that the total amount of Digit Decomposition 441 operations when using Boosting 400 technique for ciphertexts rotation of the present disclosure is

[0142]

⌈ \frac{β - 1}{b f} ⌉ .

[0143] In an exemplary embodiment with maximum KSKs, there is 1 iteration and β−1 KSK, i.e., bf=β−1. In this approach, the Digit Decomposition 441 phase is calculated once for all rotations, and the ModDown 444 phase is deferred to the multiplication of diagonals by rotated ciphertext in S303.

[0144] In summary, the maximum KSKs approach reduces the number of digit decompositions from β−1 to 1 and eliminates ModDown operations from 2(β−1) to 0, thereby reducing computational efforts. However, since only operations on baby-steps benefit from the Boosting technique, the optimal ratio between β and γ shifts towards more baby-steps and fewer giant-steps, thus for minimal computation effort β/γ>>1. Moreover, the maximum KSKs approach requires (β−1) KSKs, which incurs a heavy memory footprint cost.

[0145] For example, in a typical scenario during C2S bootstrapping where multiplication by a matrix with 63 nonzero diagonals is required, utilizing an optimal ratio β/γ>>1 yields β=32 and γ=2, thus necessitating 31 KSKs. Given that the memory size of a KSK ranges from 26 to 45 Megabytes (MB) results in a total KSK size of 806 MB to 1395 MB at the baby-step stage.

[0146] In an exemplary embodiment of minimum KSKs having β−1 iterations and one KSK, i.e., bf=1. this may be intended to reduce large KSK memory size, which incurs harsh memory bandwidth requirements, by minimizing the total KSK size at the expense of increased computation.

[0147] Considering the baby-step rotation set B={0, res, 2res, . . . , (β−1)res}, where (res) is the rotation increment using only one KSK (rotation by res). By implementing the mathematical identity rot(ct, a+b)=rot(rot(ct, a), b), a rotation by m·res∈B by applying rot(ct, res) m consecutive times, thereby allowing for retaining only one rotation at any given time. However, performing a rotation on the result of a previous rotation mandates the ModDown operation on one of the polynomials.

[0148] Referring back to the previous example, only a 26 to 45 MB KSK will be used for the Baby-Step stage, and performing Digit Decompositions 441 will sum up to 4.5(β−1)L NTTs.

[0149] It will be appreciated that maximum KSKs practice and minimum KSKs practice are opposites in terms of computational efforts. Maximum KSKs practice emphasizes computational operations, while minimum KSKs practice prioritizes reducing memory footprint and memory bandwidth.

[0150] In some exemplary embodiments, the boosting technique includes a contiguous accumulation (ConAcc) routine, which may be utilized in S303 and S304 for multiplying diagonals by rotated ciphertext and summing the products of the multiplications, respectively. It will be reminded that the ciphertexts outputs are multiplied by up to γ plaintexts, and groups of the products are rotated and summed:

[0151]

c t_{y} = \sum_{k = 0}^{γ - 1} rot (\sum_{i = 0}^{β - 1} {mul}_{ct, pt} (c t_{i}, {pt}_{k, i}), {GiantStep}_{k})

as per S303 and S304 of the linear transformation algorithm.

[0152] In the commercially available basic BSGS algorithm, all β ciphertexts outputs are stored and then multiplied, rotated, and summed. In contrast, the ConAcc routine accumulates products of ciphertexts outputs by their associated diagonals on the fly. In some exemplary embodiments, the ConAcc routine initializes γ accumulator ciphertexts. It generates the β baby ciphertexts one by one, and for each generated ciphertext, computes its contribution to each of the following γ partial sums, as represented by the following equation:

[0153]

a c c_{k} = \sum_{i = 0}^{β - 1} m u l_{ct, pt} (c t_{i}, {pt}_{k, i}) for 0 \leq k < γ .

In some exemplary embodiments, the accumulators are summed upon completion of all β ciphertexts' contributions:

[0154]

{ct}_{y} = \sum_{k = 0}^{γ - 1} rot ({acc}_{k}, {GiantStep}_{k}) .

[0155] It will be appreciated that the ConAcc routine requires peak intermediate memory of only γ ciphertexts in addition to one ciphertext holding the current baby ciphertext. Therefore, the ConAcc routine reduces the peak intermediate memory during runtime since usually β>>γ. In summary, the number of ciphertexts stored is >β+1 in the commercially available basic BSGS algorithm, whereas the number of ciphertexts stored is γ+1 when utilizing the disclosed ConAcc routine in S303 and S304.

[0156] In some exemplary embodiments, the baby step rotations and giant step rotations are grouped in two sets B and G such that the set of each possible sums b+g, where b∈B and g∈G is a superset of the required rotation set for the linear transform, which is the set of nonzero diagonals indices (B and G span the required indices).

[0157] Baby step rotations do not necessarily have finer granularity than giant steps. For example, for a required rotation set (nonzero diagonal indices set) of {10,14,17,20,24,27,30,34,37}, it is possible to choose the set of baby step rotations as B={10,20,30} and the set of giant step rotations as G={0,4,7}. The various embodiments disclosed herein can be implemented as hardware, firmware, software, or any combination thereof. Moreover, the software is preferably implemented as an application program tangibly embodied on a program storage unit or computer-readable medium consisting of parts, or of certain devices and/or a combination of devices. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units (“CPUs”), memory, and input/output interfaces. The computer platform may also include an operating system and microinstruction code. The various processes and functions described herein may be either part of the microinstruction code or part of the application program or any combination thereof, which may be executed by a CPU, whether or not such a computer or processor is explicitly shown. In addition, various other peripheral units may be connected to the computer platform, such as an additional data storage unit and a printing unit. Furthermore, a non-transitory computer-readable medium is any computer-readable medium except for a transitory propagating signal.

[0158] All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the principles of the disclosed embodiment and the concepts contributed by the inventor to further the art and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the disclosed embodiments, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure.

[0159] It should be understood that any reference to an element herein using a designation such as “first,” “second,” and so forth does not generally limit the quantity or order of those elements. Rather, these designations are generally used herein as a convenient method of distinguishing between two or more elements or instances of an element. Thus, a reference to the first and second elements does not mean that only two elements may be employed there or that the first element must precede the second element in some manner. Also, unless stated otherwise, a set of elements comprises one or more elements.

[0160] As used herein, the phrase “at least one of” followed by a listing of items means that any of the listed items can be utilized individually, or any combination of two or more of the listed items can be utilized. For example, if a system is described as including “at least one of A, B, and C,” the system can include A alone; B alone; C alone; 2A; 2B; 2C; 3A; A and B in combination; B and C in combination; A and C in combination; A, B, and C in combination; 2A and C in combination; A, 3B, and 2C in combination; and the like.

Claims

What is claimed is:

1. A method for optimizing compute runtime and memory footprint of a linear transformation process, comprising:

determining a set of optimal rotation parameters, wherein the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process; wherein the linear transformation process is a linear transformation of a ciphertext by a matrix with nonzero diagonals; wherein the rotation parameters include: a number of baby steps (β), a number of giant steps (γ), a boosting factor (bf), and a ConAcc activation flag; wherein the ConAcc activation flag indicates whether a contiguous accumulation routine is utilized as part of the linear transformation process; and wherein the optimal tradeoff comprises selecting, among configurations that satisfy a hardware memory constraint, one with a shortest program runtime;

initializing the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, wherein the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, wherein the at least one iteration is based on the determined set of optimal rotation parameters and at least one key switching key (KSK), and wherein the boosting factor (bf) defines a number of key switching keys (KSKs) used in the at least one iteration; and

loading the initialized linear transformation process to an internal memory of a hardware accelerator.

2. The method of claim 1, further comprising: determining the optimal rotation parameters based on a size of the internal memory, hardware constraints of the hardware accelerator including a total memory limit for the hardware processing capabilities, a number of accelerators, multipliers, and CPU cores, and global parameters of a program including the linear transformation process.

3. The method of claim 2, wherein determining the optimal rotation parameters further comprises:

generating a plurality of configurations based on possible combinations of the global program parameters, including rotation parameters;

evaluating runtime compute resources and memory footprint required for each configuration of the plurality of configurations; and

selecting a configuration out of the plurality of configurations that satisfies the hardware memory constraint and has the shortest program runtime.

4. The method of claim 3, wherein the runtime compute resources are based in part on a number of digit decomposition operations, including number-theoretical transforms (NTTs) and multiplications.

5. The method of claim 1, further comprising:

initializing the boosting technique to perform a contiguous accumulation routine, when the ConAcc activation flag is set to true.

6. The method of claim 5, wherein performing the contiguous accumulation routine further comprises:

generating β ciphertext outputs one by one; and for each generated ciphertext output, accumulating the ciphertext output's contribution to each of γ accumulator ciphertexts corresponding to γ partial sums by computing the products of the ciphertext output by associated diagonals.

7. The method of claim 6, wherein the contiguous accumulation routine further comprises: reducing peak memory footprint in the process of multiplying diagonals by rotated ciphertext and summing products resulting from the multiplying during runtime.

8. The method of claim 1, wherein performing the at least one iteration further comprises:

computing one digit decomposition phase that generates temporary polynomials in a larger modulus QP from coefficients of an input polynomial;

computing a number of bf MultSum phases with bf KSKs, each MultSum phase computing two inner products between a decomposed array of polynomials and respective parts of a KSK; and

computing a number of bf permute phases of two ciphertext polynomials, wherein each MultSum phases outputs two ciphertext polynomials for the permute phases, and wherein each permute phase deterministically rearranges elements of a polynomial according to a parameter r to encode a rotation.

9. The method of claim 8, further comprising:

spanning a set of nonzero diagonal indices of a matrix representing the linear transformation using a set of baby step rotations (B) and a set of giant step rotations (G).

10. The method of claim 1, wherein the linear transformation process is executed as part of an fully homomorphic encryption (FHE) program, and wherein the hardware accelerator is an FHE fully homomorphic encryption (FHE) accelerator having an on-die memory as the internal memory.

11. A non-transitory computer-readable medium storing a set of instructions for optimizing compute runtime and memory footprint of a linear transformation process, the set of instructions comprising:

one or more instructions that, when executed by one or more processors of a device, cause the device to:

determine a set of optimal rotation parameters, wherein the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process; wherein the linear transformation process is a linear transformation of a ciphertext by a matrix with nonzero diagonals; wherein the rotation parameters include: a number of baby steps (β), a number of giant steps (γ), a boosting factor (bf), and a ConAcc activation flag; wherein the ConAcc activation flag indicates whether a contiguous accumulation routine is utilized as part of the linear transformation process; and wherein the optimal tradeoff comprises selecting, among configurations that satisfy a hardware memory constraint, one with the shortest program runtime;

initialize the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, wherein the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, wherein the at least one iteration is based on the determined of set optimal rotation parameters and at least one key switching key (KSK), and wherein the boosting factor (bf) defines a number of key switching keys (KSKs) used in the at least one iteration; and

load the initialized linear transformation process to an internal memory of a hardware accelerator.

12. A system for optimizing compute runtime and memory footprint of a linear transformation process comprising:

one or more processors configured to:

initialize the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, wherein the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, wherein the at least one iteration is based on the determined set optimal rotation parameters and at least one key switching key (KSK), and wherein the boosting factor (bf) defines a number of key switching keys (KSKs) used in the at least one iteration; and

load the initialized linear transformation process to an internal memory of a hardware accelerator.

13. The system of claim 12, wherein the one or more processors are further configured to:

determine the optimal rotation parameters based on a size of the internal memory, hardware constraints of the hardware accelerator including a total memory limit for the hardware processing capabilities, a number of accelerators, multipliers, and CPU cores, and global parameters of a program, including the linear transformation process.

14. The system of claim 13, wherein the one or more processors, when determining the optimal rotation parameters, are configured to:

generate a plurality of configurations based on possible combinations of the global program parameters, including rotation parameters;

evaluate runtime compute resources and memory footprint required for each configuration of the plurality of configurations; and

select a configuration out of the plurality of configurations that satisfies the hardware memory constraint and has the shortest program runtime.

15. The system of claim 14, wherein the runtime compute resources are based in part on a number of digit decomposition operations, including number-theoretical transforms (NTTs) and multiplications.

16. The system of claim 12, wherein the one or more processors are further configured to:

initialize the boosting technique to perform a contiguous accumulation routine, when the ConAcc activation flag is set to true.

17. The system of claim 16, wherein the one or more processors, when performing the contiguous accumulation routine, are configured to:

generate β ciphertext outputs one by one; and for each generated ciphertext output, accumulate the ciphertext output's contribution to each of γ accumulator ciphertexts corresponding to γ partial sums by computing the products of the ciphertext output by associated diagonals.

18. The system of claim 17, wherein the one or more processors, when performing the contiguous accumulation routine, are further configured to:

reduce peak memory footprint in the process of multiplying diagonals by rotated ciphertext and summing products resulting from the multiplying during runtime.

19. The system of claim 12, wherein the one or more processors, when performing the at least one iteration, are configured to:

compute one digit decomposition phase that generates temporary polynomials in a larger modulus QP from coefficients of an input polynomial;

compute a number of bf MultSum phases with bf KSKs, each MultSum phase computing two inner products between a decomposed array of polynomials and respective parts of a KSK; and

compute a number of bf permute phases of two ciphertext polynomials, wherein each MultSum phases two ciphertext polynomials for the permute phases, and wherein each permute phase deterministically rearranges elements of a polynomial according to a parameter r to encode a rotation.

20. The system of claim 19, wherein the one or more processors are further configured to:

span a set of nonzero diagonal indices of a matrix representing the linear transformation using a set of baby step rotations (B) and a set of giant step rotations (G).

21. The system of claim 12, wherein the linear transformation process is executed as part of an fully homomorphic encryption (FHE) program, and the hardware accelerator is an fully homomorphic encryption (FHE) accelerator having an on-die memory as the internal memory.

Patent Citations (65)

Patent	Date	Inventor	Cited By
US7280696(B2)	2007-10-01	Zakrzewski et al.	Applicant
US9281941(B2)	2016-03-01	Gentry et al.	Applicant
US9906360(B2)	2018-02-01	Johnson et al.	Applicant
US10075288(B1)	2018-09-01	Khedr et al.	Applicant
US12155746(B1)	2024-11-01	Crockett	Applicant
US2013/0170640(A1)	2013-07-01	Gentry	Applicant
US2013/0216044(A1)	2013-08-01	Gentry et al.	Applicant
US2016/0164670(A1)	2016-06-01	Gentry et al.	Applicant
US2016/0164676(A1)	2016-06-01	Gentry	Examiner
US2017/0149796(A1)	2017-05-01	Gvili	Applicant
US2018/0109376(A1)	2018-04-01	Gentry et al.	Applicant
US2019/0278600(A1)	2019-09-01	Frumkin et al.	Applicant
US2019/0334694(A1)	2019-10-01	Chen	Examiner
US2019/0394019(A1)	2019-12-01	Gao	Examiner
US2020/0076570(A1)	2020-03-01	Musuvathi et al.	Applicant
US2020/0084017(A1)	2020-03-01	Bent et al.	Applicant
US2020/0228307(A1)	2020-07-01	Cheon et al.	Applicant
US2020/0403781(A1)	2020-12-01	Gentry et al.	Applicant
US2021/0058229(A1)	2021-02-01	Jiang et al.	Applicant
US2021/0194666(A1)	2021-06-01	Georgieva et al.	Applicant
US2021/0211290(A1)	2021-07-01	Jindal et al.	Applicant
US2021/0211291(A1)	2021-07-01	Jindal et al.	Applicant
US2021/0328766(A1)	2021-10-01	No et al.	Applicant
US2022/0172050(A1)	2022-06-01	Dalli et al.	Applicant
US2022/0271922(A1)	2022-08-01	No	Examiner
US2022/0360428(A1)	2022-11-01	Creeger et al.	Applicant
US2022/0366059(A1)	2022-11-01	Sasidharan Rajalekshmi et al.	Applicant
US2023/0019214(A1)	2023-01-01	Prothero	Applicant
US2023/0112840(A1)	2023-04-01	Micciancio et al.	Applicant
US2023/0145760(A1)	2023-05-01	Cheon	Applicant
US2023/0216676(A1)	2023-07-01	Lee et al.	Applicant
US2023/0291541(A1)	2023-09-01	Gupta et al.	Applicant
US2023/0325529(A1)	2023-10-01	Sav	Examiner
US2023/0336567(A1)	2023-10-01	Gvili	Applicant
US2023/0361986(A1)	2023-11-01	Genise et al.	Applicant
US2023/0385061(A1)	2023-11-01	Ren et al.	Applicant
US2024/0048355(A1)	2024-02-01	Joye	Applicant
US2024/0106632(A1)	2024-03-01	No et al.	Applicant
US2024/0154786(A1)	2024-05-01	Hoshizuki et al.	Applicant
US2024/0171372(A1)	2024-05-01	Kim et al.	Applicant
US2024/0171374(A1)	2024-05-01	Tan	Examiner
US2024/0362343(A1)	2024-10-01	Na et al.	Applicant
US2024/0364496(A1)	2024-10-01	Chevallier-Mames et al.	Applicant
US2024/0396706(A1)	2024-11-01	Dimou et al.	Applicant
US2024/0421971(A1)	2024-12-01	Agrawal	Examiner
US2025/0005101(A1)	2025-01-01	Taneja	Examiner
US2025/0023715(A1)	2025-01-01	Bae	Applicant
US2025/0047484(A1)	2025-02-01	Joye	Applicant
US2025/0055672(A1)	2025-02-01	Bajpeyi et al.	Applicant
US2025/0112757(A1)	2025-04-01	Kumar et al.	Applicant
US2025/0150254(A1)	2025-05-01	Adir et al.	Applicant
US2025/0167976(A1)	2025-05-01	Van Beirendonck	Examiner
US2025/0211435(A1)	2025-06-01	Maji	Examiner
US2025/0266984(A1)	2025-08-01	Cheon et al.	Applicant
US2025/0279886(A1)	2025-09-01	Kao et al.	Applicant
US2025/0300806(A1)	2025-09-01	Vrubel	Examiner
US2025/0300807(A1)	2025-09-01	Vrubel	Examiner
US2025/0300832(A1)	2025-09-01	Kleinburd	Examiner
US2025/0337560(A1)	2025-10-01	Bae et al.	Applicant
US2025/0343671(A1)	2025-11-01	Bae et al.	Applicant
CN116192361(A)	2023-05-01		Applicant
CN116488788(A)	2023-07-01		Applicant
CN117394982(A)	2024-01-01		Applicant
EP4087177(A1)	2022-11-01		Applicant
KR102616119(B1)	2023-12-01		Applicant

Non-Patent Literature (27)

Wonkyung et al. “Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with GPUs.”, IACR Transactions on Cryptographic Hardware and Embedded Systems (2021): 114-148; Apr. 23, 2021, https://ia.cr/2021/508 (Year: 2021).Examiner
Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with GPUs (Year: 2021).Examiner
Bossuat, Jean-Philippe, Mouchet, Christian, Troncoso-Pastoriza, Juan, and Hubaux, Jean-Pierre, “Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys” accessed Jul. 9, 2024.Applicant
Cheon, Jung Hee, Han, Kyoohyung, Kim, Andrey, Kim, Miran, and Song , Yongsoo, “Bootstrapping for Approximate Homomorphic Encryption”, accessed Jul. 9, 2024.Applicant
Gentry, Craig, Halevi, Shai, Smart, Nigel P., “Better Bootstrapping in Fully Homomorphic Encryption”, published Dec. 15, 2011, accessed Jul. 9, 2024.Applicant
Halevi, Shai, Shoup, Victor, “Bootstrapping for HElib”, dated Apr. 20, 2020, pp. 1-38.Applicant
Jung, Wonkyung, Kim, Sangpyo, Ahn, Jung Ho, Cheon, Jung Hee, and Lee, Younho, “Over 100x Faster Bootstrapping in Fully Homomorphic Encryption through Memory-centric Optimization with GPUs”, Published Aug. 11, 2021, vol. 2021, No. 4, pp. 114-148, accessed Jul. 9, 2024.Applicant
Kim, Andrey, Lee, Yongwoo, Deryabin, Maxim, Eom, Jieun, and Choi, Rakyong, “LFHE:Fully Homomorphic Encryption with Bootstrapping Key Size Less than a Megabyte”, published May 26, 2023, accessed Jul. 9, 2024.Applicant
Kim, Jongmin, Lee, Gwangho, Kim, Sangpyo, Sohn, Glna, Kim, John, Rhu, Minsoo, Ahn, Jung Ho, “ARK:Fully Homomorphic Encryption Accelerator with Runtime Data Generation and Inter-Operation Key Rescue”, May 3, 2022, pp. 1-14, Seoul National University.Applicant
Zhou, Minxuan, et al. “FHEmem: A Processing In-Memory Accelerator for Fully Homomorphic Encryption”, arXiv:2311.16293v1 [cs.AR] Nov. 27, 2023.Applicant
Cheon, Jung Hee, Han, Kyoohyung, Han, Minki, “Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping”, accessed Dec. 23, 2024, pp. 1-18, Seoul National University, Seoul, Korea.Applicant
Kim, Jongmin, Kim, Sangpyo, Choi, Jaewan, Park, Jaiyoung, Kim, Donghwan, Ahn, Jung Ho, “Sharp: A Short-Word Hierarchical Accelerator for Robust and Practical Fully Homomorphic Encryption”, Jun. 17-21, 2023, pp. 1-15, ISCA'23, Orlando, Florida.Applicant
Lattigo, “Lattigo: lattice-based multiparty homomorphic encryption library in Go”, Aug. 2024, Github, https://github.com/tuneinsight/lattigo, date accessed Dec. 23, 2024.Applicant
Samardzic, Nikola, Feldmann, Axel, Manohar, Nathan, Genise, Nicholas, Eldefrawy, Karim Peikert, Chris, “Crater Lake: A Hardware Accelerator for Efficient Unbounded Computation on Encrypted Data”, Jun. 18-22, 2022, pp. 1-15, ISCA, New York, New York.Applicant
International Search Report for PCT/IB2025/050820, dated May 7, 2025. Searching Authority, Israel Patent Office, Jerusalem, Israel.Applicant
International Search Report for PCT/IB2025/050822, dated Apr. 30, 2025. Searching Authority, Israel Patent Office, Jerusalem.Applicant
International Search Report for PCT/IB2025/050824, dated May 7, 2025. Searching Authority, Israel Patent Office, Jerusalem, Israel.Applicant
Written Opinion of the Searching Authority for PCT/IB2025/050820, dated May 7, 2025. Searching Authority, Israel Patent Office, Jerusalem, Israel.Applicant
Written Opinion of the Searching Authority for PCT/IB2025/050822, dated Apr. 30, 2025. Searching Authority, Israel Patent Office, Jerusalem.Applicant
Written Opinion of the Searching Authority for PCT/IB2025/050824, dated May 7, 2025. Searching Authority, Israel Patent Office, Jerusalem, Israel.Applicant
Li, Ningbo et al. Efficient Multi-Key FHE With Short Extended Ciphertexts and Directed Decryption Protocol (Year: 2019).Applicant
Zhang, Kaiyuan et al. Hardware Acceleration for Fully Homomorphic Encryption Scheme Switching from CKKS to FHEW (Year: 2024).Applicant
Wu, et al. “Bootstrapping Optimization for Fully Homomorphic Encryption Schemes”, Apr. 19, 2024, PREPRINT (Version 1) available at Research Square [https://doi.org/10.21203/rs.3.rs-4194403/v1] (Year: 2024).Applicant
Bossuat, et al.; “Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys, 2021” (Year: 2021).Applicant
Cheon, et al.; “Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping, 2021” (Year: 2018).Applicant
Jung et al. “Over 100x Faster Bootstrapping in Fully Homomorphic Encryption through Memory-centric Optimization with GPUs” (Year: 2021).Applicant
Reagen, et al.; “Cheetah: Optimizing and Accelerating Homomorphic Encryption for Private Inference, 2021” (Year: 2021).Applicant