Method and Apparatus for Configuring a Reduced Instruction Set Computer Processor Architecture to Execute a Fully Homomorphic Encryption Algorithm

Abstract

Systems and methods for configuring a reduced instruction set computer processor architecture to execute fully homomorphic encryption (FHE) logic gates as a streaming topology. The method includes parsing sequential FHE logic gate code, transforming the FHE logic gate code into a set of code modules that each have in input and an output that is a function of the input and which do not pass control to other functions, creating a node wrapper around each code module, configuring at least one of the primary processing cores to implement the logic element equivalents of each element in a manner which operates in a streaming mode wherein data streams out of corresponding arithmetic logic units into the main memory and other ones of the plurality arithmetic logic units.

Claims

1. A method for compressing neural network weight data on a multiple processor core system, wherein the multiple processor core system comprises a chip including a plurality of processor cores, each processor core comprising one or more processing elements, an internal cache, and an external memory, wherein the processor cores or their processing elements are operable in a streaming mode, and wherein the compression is performed automatically upon output from a data reordering module and/or a convolution module, the method comprising: receiving a set of neural network weight values arranged in a multidimensional WHC structure; dividing the neural network weight values into a plurality of fixed sized groups; generating, for each group, a bitmask indicating whether each weight value in the group is zero or non-zero; identifying sparsity patterns including randomly interspersed zeros and short bursts of zero values within the data; and storing, for each group, only the non-zero values and the associated bitmask as compressed weight data, wherein the compressed weight data is stored in a main memory external to the chip and accessible by the plurality of processor cores thereby reducing external bandwidth and overall power consumption by avoiding transmission and computation of zero values, whereby decompression allows the data stream to avoid multiplications by zero to improve utilization of computation resources.

2. A method for decompressing compressed neural network weight data on a multiple processor core system, data on a multiple processor core system, wherein the multiple processor core system comprises a chip including a plurality of processor cores, each processor core comprising one or more processing elements an internal cache, and an external memory, wherein the processor cores or their processing elements are operable in a streaming mode, the method comprising: retrieving a plurality of groups of the compressed weight data and corresponding bitmasks from a main memory external to a processor chip; reconstructing each group of weight values by using the corresponding bitmask for that group to determine locations for zero values thereby eliminating multiplications and excess data movements; and supplying the reconstructed weight values to one or more neural network layers for processing in a convolution.

3. A method for compressing neural network weight data on a multiple processor core system, wherein the multiple processor core system comprises a chip including a plurality of processor cores, each processor core comprising one or more processing elements an internal cache, and an external memory, wherein the processor cores or their processing elements are operable in a streaming mode, and wherein the compression is performed automatically upon output from a data reordering module and or a convolution module to reduce bandwidth, power and computation load, the method comprising: receiving a set of neural network weight values arranged in a multidimensional WHC structure; dividing the neural network weight values into a plurality of fixed sized groups; generating, for each group, a bitmask indicating whether each weight value in the group is zero or non-zero; identifying sparsity patterns including randomly interspersed zeros and short bursts of zero values within the data; storing, for each group, only the non-zero values and the associated bitmask as compressed weight data, wherein the compressed weight data is stored in a main memory external to the chip and accessible by the plurality of processor cores, thereby reducing external bandwidth and overall power consumption by avoiding transmission and computation of zero values, whereby decompression allows the data stream to bypass unnecessary multiplications with zero, improving utilization of computation resources; retrieving the plurality of groups of the compressed weight data and corresponding bitmasks from a main memory external to a processor chip; reconstructing each group of weight values by using the corresponding bitmask for that group to determine locations for zero values thereby eliminating multiplications and excess data movements; and supplying the reconstructed weight values to one or more neural network layers for processing in a convolution.

4. A method for compressing neural network weight data on a multiple processor core system, wherein the multiple processor core system comprises a chip including a plurality of processor cores, each with one or more processing elements and internal cache, and wherein the system is operable to stream data, the method comprising: receiving a set of weight values; for each weight value, appending a bit indicating whether the value is zero or non-zero; for one or more sequences of consecutive zero values, appending a multi-bit field indicating a count of the consecutive zeros; and transmitting the resulting compressed stream over a data bus to an external memory; whereby the inclusion of per-value indicators and count fields increases the bit width of the data bus but provides a simpler compression implementation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0025] FIG. 1 is a schematic illustration of a processor architecture in accordance with one or more implementations.

[0026] FIG. 2a is a schematic illustration of a single RISC processor and related hardware showing the data streams of both control mode and streaming mode.

[0027] FIG. 2b is a schematic illustration of a processor architecture showing that the core modes can be dynamically and flexibly configured.

[0028] FIG. 3 is a flow chart of a pipeline of the computer processor architecture in a streaming mode, in accordance with one or more implementations.

[0029] FIG. 4 is a schematic diagram of a secondary core in a streaming mode, in accordance with one or more implementations.

[0030] FIG. 5 is a schematic diagram of specific topology of a secondary core, in accordance with one or more implementations.

[0031] FIG. 6 is a flow chart of a method for configuring an architecture in accordance with one or more implementations.

[0032] FIG. 7 is schematic diagram of a SegNet architecture.

[0033] FIG. 8 is a flow chart of a data stream of a portion of the SegNet implementation.

[0034] FIG. 9 is a schematic diagram of a compression data structure.

[0035] FIG. 10 is flowchart of an implementation of XEncoder.

[0036] FIG. 11 is a flowchart of an implementation of ZMac.

[0037] FIG. 12 illustrates the top-level topology derived from the bootsAND function in TFHE library for fully homomorphic encryption in accordance with one or more implementations.

[0038] FIG. 13 illustrates the bootsAND Top-Level topology with partial unrolling of the tfhe_MuxRotate_FFT Loop in accordance with one or more implementations.

[0039] FIG. 14 shows the top-level topology derived from the tGswFFTExternMulToTLwe function in accordance with one or more implementations.

[0040] FIG. 15 graphically illustrates how Decimation-in-Frequency can be used to decompose an N=8-point DFT into 2 N/2=4 point DFTs in accordance with one or more implementations.

[0041] FIG. 16 is a flow graph of decimation-in-frequency decomposition of an 8 point DFT into four two point DFTs in accordance with one or more implementations.

[0042] FIG. 17 is a basic flow graph of an FFT butterfly structure.

[0043] FIG. 18 is a logic element diagram of an FFT butterfly function in accordance with one or more implementations.

[0044] FIG. 19 illustrates the butterfly function of FIG. 19 mapped to physical cores of a streaming topology in accordance with one or more implementations.

[0045] FIG. 20 is a flow graph of DIT decomposition of an N=8-point DFT into two N/2=4 point computations in accordance with one or more implementations.

[0046] FIG. 21 is a flow chart of decimation-in-time decomposition of an 8-point DFT into four 2-point DFT computations in accordance with one or more implementations.

[0047] FIG. 22 illustrates a diagram on an input butterfly operation of single stage in accordance with one or more implementations.

[0048] FIG. 23 illustrates a logic element diagram of the butterfly of FIG. 23 in accordance with one or more implementations.

[0049] FIG. 24 illustrates the logic of FIG. 24 mapped out on cores of the streaming topology described herein in accordance with one or more implementations.

[0050] FIG. 25 illustrates polynomial multiplication, showing coefficients representation and point-value pair representation in accordance with one or more implementations.

[0051] FIG. 26 illustrates an equivalent simplified logic flow in accordance with one or more implementations.

[0052] FIG. 27 illustrates a first stage streaming topology in accordance with one or more implementations.

[0053] FIG. 28 illustrates the special last stage streaming topology in accordance with one or more implementations.

[0054] FIG. 29 illustrates the last stage of the optimized IFFT in a simplified form in accordance with one or more implementations.

[0055] FIG. 30 illustrates the last stage streaming topology mapped onto cores in accordance with one or more implementations.

[0056] FIGS. 31a-31d illustrate the entire FFT mapped to cores in accordance with one or more implementations.

[0057] FIGS. 32a-32d illustrate the entire IFFT mapped to cores in accordance with one or more implementations.

DETAILED DESCRIPTION

[0058] The inventors have developed an architecture and methodology that allows processor cores, such as known RISC processors to be leveraged for increased computing power. The processor cores, referred to as primary cores herein, are segregated into control logic and simple processing elements, such as arithmetic logic units. A node wrapper allows the architecture to be configurable into a streaming mode (fractured mode) in which pipelines are defined and data is streamed directly to the execution units/processing elements as secondary cores. Applicant refers to secondary cores using the tradename Fractal Cores. In a streaming mode, the processor control logic need not be used. The secondary cores are addressed individually and there is reduced need for data to be stored in temporary storage as the data is streamed from point to point in the pipelines. The architecture is extensible across chips, boards and racks.

[0059] FIG. 1 illustrates an example of a computing architecture. As illustrated in FIG. 1, architecture 102 includes multiple primary processing cores 108a, 108b . . . 108n. Each main processing core 108 can include a corresponding node wrapper 110a, 110b . . . 110n (only some of which are labeled 110 in FIG. 1. for clarity) as described in greater detail below. Each primary processing core 108 may be defined by a RISC processor, such as the Altera NIOS processor. By way of non-limiting example, each primary processing core 108 may include a corresponding main memory 112a, 112b . . . 112n (only some of which are labeled FIG. 1. for clarity) that includes multiple cache memories. The node wrappers 110 can include access memory associated with each secondary core, and a load/unload matrix associated with each secondary core. Each primary processing core 108 can also include a set of processing units 114a, 114b . . . 114n, such as arithmetic logic units (ALUs), which separately or collectively can define a secondary processing core as described in detail below.

[0060] A wrapper is generally known as hardware or software that contains (wraps around) other hardware, data or software, so that the contained elements can exist in a newer system. The wrapper provides a new interface to an existing element. In embodiments, the node wrappers provide a configurable interface that can be configured to allow execution in a conventional control-centric mode or in a streaming mode, or fractured mode, that is described below.

[0061] In a conventional control-centric mode (RISC mode), the architecture uses the core control logic to control data flow and operates in a manner wherein data is read from and written to the cache memory and processed by a primary core in accordance with control logic. However, secondary cores 114 may be selectively fractured to operate in a fractured mode, as part of a pipeline, wherein data streams out of the corresponding secondary core into the main memory and other ones of the plurality of secondary cores and data streams from the main memory and other secondary cores to stream into the corresponding core, as described in greater detail below. As an example, a rectangular partition can be created from a result matrix y using single precision floating point arithmetic.

[0062] The node wrappers 110 may be configured to partition logic and an input state machine for transferring data from memory to the processing element and wherein each arithmetic logic unit has an output that is associated with an output memory. The output memory may be updated throughout processing with the latest sum as it is computed. Arithmetic logic units 114 of the RISC processor can be used as streaming secondary cores in the streaming mode. Each node wrapper 110 can be configured to define multiple hardware streams, i.e. pipelines, to be allocated to specific ones of the cores.

[0063] FIG. 2a illustrates the two possible modes of operation, RISC mode and fractured mode, of the architecture. As illustrated in FIG. 2, RISC Processor 208 includes two processing elements, ALU1 and ALU2. Node Wrapper 210 includes two secondary node wrappers NW0 and NW1. Memory 212 includes secondary memories M0 and M1. In the RISC mode, the data streams indicated by the solid lines stream from a Network on a Chip (NOC), such as a PCIe bus, to memory 112 for processing by RISC processor 208. In the fractured mode, the streams are indicated by the dashed lines. In the fractured mode, node wrapper 210 is used as secondary node wrappers NW0 and NW1 and memory 212 is used as secondary memories M0 and M1 to define two data streams in this example. One data stream passed through ALU1 and one passed through ALU2 with ALU1 and ALU2 each defining a secondary core. Of course, the RISC processor can have any number of processing elements and data streams can be configured as needed. Note that, in this example, the RISC mode includes 4 data streams and a relatively large memory, while in the Fractured mode includes 2 data streams and a relatively small memory.

[0064] As illustrated schematically in FIG. 2b, some cores of the architecture can be configured to operate in the RISC mode while some are configured to operate in the fractured mode, as needed by any specific application at any specific time. Further, core modes can be configured dynamically, in real-time, during execution. On the left in FIG. 2b, all cores are configured as primary cores (RISC mode). On the right in FIG. 2b some cores are configured as primary cores and some cores are configured as secondary cores (fractured mode). The configuration can take any form as required by the specific application at the specific time. Some examples include: [0065] 112 RISC cores/1,480 Fractured Core (FC) cores: 896 RISC cores/12K FC cores per 1 U server, 36K RISC cores/474K FC cores per Rack [0066] 480 RISC cores/7,420 FC cores: 4K RISC cores/60K FC cores per 1 U server, 154K RISC cores/2.4M FC cores per Rack [0067] 8196 RISC cores/131,136 FC cores: 66K RISC cores/1M FC cores per 1 U server [0068] 2.6M RISC cores/42M FC cores per Rack

[0069] Referring to FIG. 1, the various interconnections are configured by the node wrappers using a Network On Chip (NOC). In this example, the NOC is a 2-layer NOC of L0 switches interconnected to a L1 switch via 64 bit lanes. The NOC also has an overlay network that interconnects all the secondary cores in a linear manner, as shown by the red arrows in FIG. 1. In this example, the switches are crosspoint switches, i.e. a collection of switches arranged in a matrix configuration. Each switch can have multiple input and output lines that form a crossed pattern of interconnecting lines between which a connection may be established by closing a switch located at each intersection, the elements of the matrix. In this example, a PCI Express (PCIe) buss interface is used. PCIe provides a switched architecture of channels that can be combined in 2, 4, 8, 16 and 32 configurations, creating a parallel interface of independently controlled lanes.

[0070] In some implementations, the architecture may be formed on a single chip. Each cache memory may be a nodal memory including multiple small memories. In some implementations, each core may have multiple arithmetic logic units. In some implementations, by way of non-limiting example, the arithmetic logic units may include at least one of integer multipliers, integer multiplier accumulators, integer dividers, floating point multipliers, floating point multiplier accumulators, floating point dividers. In some implementations, the arithmetic logic units may be single instruction multiple data units. As a simple example, an architecture can be made up of 500 primary processor cores 108 each having 16 processing elements. In the streaming mode, up to 8000 secondary cores 114 can be addressed individually. This allows for performance of massive mathematical operations, as is needed in Artificial Intelligence applications. The primary cores and secondary cores can be dynamically mixed to implement new algorithms.

[0071] The process and mechanism for configuring the architecture is described below. As noted above, the fractured mode is accomplished by defining one or more pipelines of streaming data between the secondary cores. FIG. 3 illustrates a simple data stream pipeline which connects 4 arithmetic logic units 302, 304, 306, and 308 in series so that an input from source 301 is processed into an output 309. The ALUs are examples of the processing elements described above that define the secondary cores. The pipeline is defined by setting the L0 and L1 switches in the NOC described above. Of course, the NOC can be configured in any manner to define any data stream pipeline(s). The appropriate node wrapper(s) 110 can execute code to configure the NOC. As an example, the pipeline of FIG. 2 can be configured by execution of the C++ code objects set forth below. Note that the keyword threadModule indicates to the tooling that the code to be executed will run on a RISC core, with the keyword streamModule indicating that the code to be executed will run on a Fractured Core.

TABLE-US-00001 class source: public threadModule { // code to run on a RISC core outputStream outStrm; void code( ); // pointer to the RISC code }; // sends data to output class pipeline: public streamModule { // code to run on a Fractured core inputStream inStrm; outputStream outStrm; void code( ); // pointer to the operation the Fractured core will perform }; // process data from input and send to output class sink: public threadModule { // code to run on a RISC core inputStream inStrm; void code( ); // pointer to the RISC code }; // receives data from input

[0072] In the objects above code( ) can point to the source code below:

TABLE-US-00002 // Example of code which can be run on a RISC core void source::code( ) { int x; for (x = 0; x < 1000; ++x) // Put 1000 ints into outStrm { printf(Generating Data %d\n, x); outStrm << x; // TruStream put } } //Example of code which can be run on a Fractured Core void pipeline::code( ) { int x; int sum = 0; inStrm >> x; // get data from input stream sum += x * 3;// perform some computation outStrm << sum; // TruStream put, send data to output stream } // Example of code which can be run on a RISC core void sink::code( ) { int x; for (x = 0; x < 1000; ++x) { inStrm >> x; // get data from input stream printf(Received Data %d\n, x); } }

[0073] The code below serves to connect the topology of pipeline of FIG. 3, where source and sink are running on a RISC core, and 4 Fractured Cores are performing a MAC (multiplication with accumulation):

TABLE-US-00003 class pipelineTest: public streamModule { source src; pipeline pipe; sink snk; public: pipelineTest( ) // Constructor { src >> pipe >> pipe >> pile >> pipe >> snk; // Connect modules end( ); // Housekeeping } };

[0074] FIG. 4 illustrates a top-level diagram of an example of a secondary core 400 defined by processing elements. The pipeline configuration requires a number of clock cycles for a value to be read out of Y memory, added to the new product, and returned to Y memory before that element can be accessed again. A product that arrives before the Y memory element is ready to be read is shunted to the T-FIFO for later accumulation. Memory hazard logic (not shown) can be used to determine if the Y memory location for a new product has been used recently that controls steering of the data in the design. The pre-loaded X mem holds the partition of the X (right) matrix applicable to the partition of the Y (result) matrix performed by this Small Core. The applicable partition of the A (left) matrix is streamed into the PE in compressed form (non-zero elements only, accompanied by row/column info). The Y mem accumulates the products as the matrix is computed. The implementation can also include a peer-to-peer connection between adjacent processing elements 114 in a ring intended to permit dividing the processing load for particular Y-elements between two or more processing elements, which is useful to make the design scalable to larger matrices without a significant loss of performance.

[0075] FIG. 5 illustrates a specific topology of secondary cores 500. The design includes a test scaffold built around the processing element ring that allows the test matrices to be initially stored in a central memory store, automatically partitioned and delivered to the processing elements, run through the processing elements with the option of continuously repeating the test matrices (for power measurement), and then have the result partitions collected and reassembled into the full output matrix and returned to the central memory where the result may be accessed easily using the memory initialization and dump tools.

[0076] Each processing element 114 in FIG. 5 is associated on the input side with a node input memory, partitioning logic and an input state machine for transferring data from the local memory to the processing element. On the output side, each processing element 114 is associated with an output memory that is updated throughout the process with the latest sum for each Y element as it is computed. At the completion of the matrix processing, the accumulated data in the output memory is transferred back to the central access memory via combiners that either pass data from the previous processing element 114, or replace input with data from the local processing element 114 to reconstruct the full matrix as the matrix is scanned by row and column.

[0077] The programming and data information in the central access memory includes a setup word for each processing element 114 that contains partition information for the processing element 114. That setup word configures the partition logic at each processing element 114 to only use data with rows and columns associated with the processing element's partition. Both the pre-load X matrix data and the streaming A matrix data arrive over the same path and use the same partition setup to select data out of the data stream from the central memory. Selected data at each processing element 114 gets written into the node input memory and held until the access manager completes transferring data and starts the processing. When processing starts, the processing uses only the data that has been transferred into the node memories and stops when the end of the data has been reached. If the repeat bit is set in the start word, the pointer into the node input memory is reset to 0 when the end of the buffered data is reached and allowed to repeat the data indefinitely. This allows power measurements to be made.

[0078] FIG. 6 illustrates a method 600 for reconfiguring a reduced instruction set computer processor architecture, in accordance with one or more implementations. The operations of method 600 presented below are intended to be illustrative. In some implementations, method 600 may be accomplished with one or more additional operations not described, and/or without one or more of the operations discussed. Additionally, the order in which the operations of method 600 are illustrated in FIG. 6 and described below is not intended to be limiting.

[0079] An operation 602 may include providing configuration code to one or more node wrappers. An operation 604 may include executing the configuration code to set the interconnections of the NOC in a manner which creates at least on pipeline. An operation 606 may include operating the architecture in a streaming mode wherein data streams out of the corresponding secondary core into the main memory and other ones of the plurality of secondary cores and data streams from the main memory and other secondary cores to stream into the corresponding core in a streaming mode or the control-centric mode.

[0080] FIGS. 7 and 8 illustrates a specific example of the architecture applied to a SegNet topology. As noted above, SegNet is a fully convolutional neural network (CNN) architecture for semantic pixel-wise segmentation. This core trainable segmentation engine consists of an encoder network, a corresponding decoder network followed by a pixel-wise classification layer. The architecture of the encoder network is topologically identical to the 13 convolutional layers in the VGG16 network. The role of the decoder network is to map the low-resolution encoder feature maps to full input resolution feature maps for pixel-wise classification. The SegNet decoder upsamples its lower resolution input feature map(s). Specifically, the decoder uses pooling indices computed in the max-pooling step of the corresponding encoder to perform non-linear upsampling. This eliminates the need for learning to upsample. The upsampled maps are sparse and are then convolved with trainable filters to produce dense feature maps.

[0081] As illustrated in FIG. 7, a SegNet Topology 700 includes encoder 710 and decoder 720. The three-dimensional CNN topology can be transformed into an equivalent one-dimensional topology using the techniques disclosed herein. SegNet Layer 1 712 can be transformed into the 77-stage fractured core pipeline 800 shown in FIG. 8. The stages illustrated in FIG. 8 perform the following operations: [0082] pad (Top), pad (Bottom), pad (Left) and pad (Right) add zero-padding around the image. Does not require memory. [0083] The reorder stages convert the row-based video stream into a window-based stream. Accesses on-die SRAM. [0084] The 64 convolve stages perform a convolution for each of the 64 filters (kernels). Accesses on-die SRAM. [0085] The batch-normalization stage performs batch normalization. Accesses on-die SRAM. [0086] The ReLU stage implements the Rectified Linear Unit (ReLU) activation function. Does not require memory. [0087] The three pooling stages perform max pooling. Accesses on-die SRAM.

[0088] The embodiments facilitate more efficient data compression. Neural Networks, by their very definition, contain a high degree of sparsity, for the SegNet CNN over 3 the computations involve a zero element. Clearly, having an architecture that can automatically eliminate the excess data movements for zero data, and the redundant multiply by zero for both random and non-random sparsity would result in higher performance and lower power dissipation. Data which is not moved results in a bandwidth reduction and a power savings. Multiplications that do not need to be performed also save power dissipation as well as allowing the multiplier to be utilized for data which is non-zero. The highest bandwidth and computation load in terms of multiply accumulates occurs in the DataStreams exiting the Reorder modules in 801 which feed the Convolve Modules 802. Automatically compressing the data leaving the reorder module, 801, reduces the bandwidth required to feed the convolve modules as well as reducing the maximum MAC (multiply accumulates) that each convolve performs. There are several possible zero compression schemes that may be performed, what is illustrated is a scheme which takes into account the nature of convolution neural networks. The input to a convolver, 802, consists of a 3-dimensional data structure (WidthHeightChannel). Convolution is defined as multiplying and summing (accumulating) each element of the WHC against a Kernel Weight data structure also consisting of (WidthHeightChannel). The data input into the convolver exhibits two types of sparsity-random zeros interspersed in the WHC data structure and short bursts of zeros across consecutive (W+1)(H+1)C data elements. The compressed data structure that is sent from the Reorder Modules to the Convolver modules is detailed in FIG. 9. For every possible 32 values one Bitmask value, 901, is sent followed by any non-zero data values, 902. Each bit position in the bitmask indicates where whether there is valid data or zero data in that position. In the case where there is no zero data, 901 will be all zeros, followed by 32 data values, 902. In the other extreme where there are 32 zero data values, 901 will be all 1's and no data values, 902, will follow. In the case there is a mixture of non-zero data values and data values the bitmask, 901, will indicate this and only the non-zero data values will follow in 902. FIG. 10 is the flow chart for the circuitry which resides in 801 the reorder module which performs the compression.

[0089] FIG. 11 is the flow chart for the circuitry which resides in 802, the convolver, to perform the de-compression. Note that the bit position which is non-zero is critical since the convolution operation must multiply the non-zero data with the correct kernel weight-hence a counter (FIG. 11, step 1 and step 5) must be maintained. The advantage is as follows: Given a SegNet Reorder/Convolution of width 7, height 7 and channels 64 an approach with no compression will send 3136 (7764) values from the reorder module, 801, to each convolver, 802 where 3136 Multiply Accumulations will be performed. With a 50% chance of zero values the described circuitry will send 98 BitMasks and only 1568 data values. This results in a savings in terms of bandwidth of almost 50% and a 50% reduction in multiply accumulates across 64 individual convolvers. Alternatively, a simpler compression scheme, such as the addition of an additional bit to each data values to indicate non-zero data plus the addition of several bits to indicate a count of zeros values can also be used to perform compression, at the penalty of increasing the bit width of the bus carrying the data values.

[0090] As noted above, the streaming topologies described herein can be applied to achieve FHE processing with far fewer computing resources than would be required with conventional processors. FHE has specialized logic gates that are very complicated and computing resource intensive. For example, the BootsAND logic gate of TFHE has two inputs (LweSample) that are each 501 32 bit integers. Transforming FHE logic, such as TFHE logic, to the streaming topologies desired herein yields processing that is much more efficient. Implementations described herein include topologies derived from three TFHE functions: (1) bootsAND, (2) tfhe_MuxRotate_FFT and (3) tGswFFTExternMulToTLwe.

[0091] Below are the constants used in the TFHE code. They are used to compute the sizes of the data members and for-loop limits in the streaming topology as described below.

TABLE-US-00004 static const int32_t N = 1024; static const int32_t k = 1; static const int32_t n = 500; static const int32_t bk_l = 2; static const int32_t bk_Bgbit = 10; static const int32_t ks_basebit = 2; static const int32_t ks_length = 8; static const double ks_stdev = 2.44e5; //standard deviation static const double bk_stdev = 7.18e9; //standard deviation static const double max_stdev = 0.012467; //max standard a 1/4 msg space deviation for

[0092] Torus32 is a key typedef used in the TFHE code and in the TruStream topologies below:

TABLE-US-00005 typedef int int32_t; typedef unsigned int uint32_t; typedef unsigned long long uint64_t; typedef int32_t Torus32; // avant uint32_t

[0093] The TFHE code is divided into references (structs) which are composite data type declarations defining a physically grouped list of variables under one name. Structs can be thought of as the data processed by the functions. For example, the TFHE bootsAND code includes 23 structs that can be classified as either 1) STATIC/NON-STREAMING (data values of these types are fixed/static for a particular Boolean AND gate and can therefore be stored in SRAM) or 2) DYNAMIC/STREAMING (data values which are periodically or constantly changing, and are streamed from one core to another).

[0094] The TFHE code is expressed in C/C++, both of which make extensive use of: [0095] new (a library function that requests memory allocation on a process's heap) [0096] malloc (a library function that allocates the requested memory and returns a pointer to it.) [0097] delete (a library function that requests removal of memory allocation on a process's heap) [0098] pointers.

[0099] The streaming topology described herein does not use these system functions. Instead, it uses streams. This has implications for the nine DYNAMIC/STREAMING structs of the TFHE code, when being adapted for a streaming processor arrangement. Implementations use a mechanism to replace the pointer data-members in these nine structs with the actual arrays being pointed to because instead of passing an array pointer from one function to another, a streaming program passes/streams the actual array from one module to another. On a conventional microprocessor, however, the benefits of a streaming programming model are best achieved by streaming pointers. However, this arrangement, conventional processors streaming pointers, is disadvantageous for the following reasons. [0100] The streaming compute fabric is arbitrarily scalable [0101] The streaming compute fabric can achieve much, much higher levels of performance [0102] the streaming compute fabric has none of the bottlenecks that plague conventional microprocessors, like caching, context switching, scheduling and dispatching [0103] The streaming compute fabric has no bloat code (such as control code), the only code running in the streaming compute fabric is application code [0104] the streaming compute fabric is far more efficient in terms of energy consumption and usage of silicon real-estate.

[0105] Accordingly, the dynamic structs of the TFHE bootsAND code can be converted into the following structs that can be streamed (the S designates a streaming struct.

TABLE-US-00006 1S. Struct TGswSample // DYNAMIC / STREAMING { int32_t all_sample[ (k + 1) * bk_l ]; // (k + 1) * l = 4 int32_t bloc_sample[ k + 1]; // k + 1 = 2 const int32_t k; // STATIC / NON-STREAMING const int32_t l; // STATIC / NON-STREAMING }; 2S. Struct Ts_LweSample // DYNAMIC / STREAMING { int32_t a[ n ]; // n = 500 int32_t b; double current_variance; }; 3S. Struct Ts_TGswSampleFFT // DYNAMIC / STREAMING { int32_t all_samples[ (k + 1) * l ]; // (k + 1) * l = 4 int32_t sample[ k + 1 ]; // k + 1 = 2 const int32_t k; // STATIC / NON-STREAMING const int32_t l; }; 4S. Struct Ts_IntPolynomial // DYNAMIC / STREAMING/** This structure represents an integer polynomial modulo X{circumflex over ()}N+1 */ { const int32_t N; // N = 1024 int32_t coefs[ N ]; }; 5S. Struct Ts_TlweSample // DYNAMIC / STREAMING { int32 a[ (k + 1) * N ]; // (k + 1) * N = 2048 int32 b; // Alias of a[k], DONT CARE double current_variance; const int32_t k; // STATIC / NON-STREAMING }; 6S Struct Ts_TLweSampleFFT // DYNAMIC / STREAMING { int32_t a[ (k + 1 ) * N ]; // (k + 1) * N = 2048 int32_t b; // Alias of a[k], DONT CARE double current_variance; const int32_t k; // STATIC / NON-STREAMING }; 7S. Struct Ts_TgswSample // DYNAMIC / STREAMING { int32_t all_sample[ (k + 1) * l ]; // (k + 1) * l = 4 int32_t bloc_sample[ k + 1 ]; // k + 1 = 2 const int32_t k; // STATIC / NON-STREAMING const int32_t l; // STATIC, NON-STREAMING }; 8S. Struct Ts_LagrangeHalfCPolynomial_IMPL // DYNAMIC / STREAMING /** structure that represents a real polynomial P mod X{circumflex over ()}N+1 as the N/2 complex numbers: P(w), P(w{circumflex over ()}3), ..., P(w{circumflex over ()}(N1)) where w is exp(i.pi/N) */ { double coefsC[ N ]; // N = 1024 N/2 complex numbers2 FFT_Processor_Spqlios* proc; }; 9S Struct Ts_TorusPolynomial // DYNAMIC / STREAMING/** This structure represents an torus polynomial modulo X{circumflex over ()}N+1 */ { const int32_t N; // N = 1024 int32_t coefsT[ N ]; };

[0106] The streaming structs above can be created from the original structs by, for example, the following process: [0107] locate a pointer in the code; [0108] backtrack through the code to find data that was created and the allocated block of data that is pointed to; [0109] determine the size of the allocated block; [0110] replace the pointer with a data array corresponding to the allocated block; and [0111] use the array as streaming data.

[0112] FIG. 12 illustrates the top-level topology derived from the bootsAND function in TFHE library for fully homomorphic encryption. Note that housekeeping functions, such as new and delete, are not relevant in the streaming programming model. Also, static function arguments, such as TfheGateBootstrappingCloudKeySet, LweBootstrappingKeyFFT and TgswParams, are omitted from FIG. 12 since they can be stored in the memories, such as 112a of FIG. 1, of appropriate cores of a streaming architecture. The topology can be derived by starting with call stack, creating blocks of functions with control, and converting the function calls to modules. An example is set forth below. Starting with the tfhe_bootstrap_woKS_FFT Function:

TABLE-US-00007 EXPORT void tfhe_bootstrap_woKS_FFT(LweSample *result, const LweBootstrappingKeyFFT *bk, Torus32 mu, const LweSample *x) { const TGswParams *bk_params = bk>bk_params; const TLweParams *accum_params = bk>accum_params; const LweParams *in_params = bk>in_out_params; const int32_t N = accum_params>N; const int32_t Nx2 = 2 * N; const int32_t n = in_params>n; TorusPolynomial *testvect = new_TorusPolynomial(N); int32_t *bara = new int32_t[N]; // Modulus switching int32_t barb = modSwitchFromTorus32(x>b, Nx2); for (int32_t i = 0; i < n; i++) { bara[i] = modSwitchFromTorus32(x>a[i], Nx2); } // the initial testvec = [mu,mu,mu,...,mu] for (int32_t i = 0; i < N; i++) testvect>coefsT[i] = mu; // Bootstrapping rotation and extraction tfhe_blindRotateAndExtract_FFT(result, testvect, bk>bkFFT, barb, bara, n, bk_params); delete[ ] bara; delete_TorusPolynomial(testvect); }

[0113] A corresponding module is created:

TABLE-US-00008 class tfhe_bootstrap_woKS_FFT_Module: public threadModule // A threadModule class { inputStream_NoAutoAckx_inStrm; // Input- stream data member outputStreamtestvect_outStrm; // Output- stream data member outputStream bara_outStrm; // Output-stream data member outputStream barb_outStrm; // Output-stream data member Torus32mu; // Data member LweSample*x; // Data member const TGswParams*bk_params; // Data member const TLweParams*accum_params; // Data member const LweParams*in_params; // Data member const int32_tN; // Data member const int32_tNx2; // Data member const int32_tn; // Data member TorusPolynomial* testvect[ FHE_FIFO_Size + 1 ]; // Data member int32_t* bara[ FHE_FIFO_Size + 1 ]; // Data member int32_t barb; // Data member void code( ); // Member function // (Contains the threadModule thread) public: tfhe_bootstrap_woKS_FFT_Module( const LweBootstrappingKeyFFT* bk ) : // Constructor (Called from bk_params( bk>bk_params ), // a streamModule when a accum_params( bk>accum_params ), // tfhe_bootstrap_woKS_FFT_Module in_params( bk>in_out_params ), // is constructed) N( accum_params>N ), Nx2( 2 * N ), n( in_params>n ) { setName( tfhe_bootstrap_woKS_FFT_Module ); // Set name (used in debugging) x_inStrm.setName( x_inStrm ); // Set name (used in debugging) bara_outStrm.setName( bara_outStrm ); // Set name (used in debugging) barb_outStrm.setName( barb_outStrm ); // Set name (used in debugging) testvect_outStrm.setName( testvect_outStrm ); // Set name (used in debugging) x_inStrm.setDirection( TS_NORTH ); // Set direction (used by the streamMpdule >> operator) bara_outStrm.setDirection( TS_SOUTH ); // Set direction (used by the streamMpdule >> operator) barb_outStrm.setDirection( TS_SOUTH ); // Set direction (used by the streamMpdule >> operator) testvect_outStrm.setDirection( TS_SOUTH ); // Set direction (used by the streamMpdule >> operator) } };

[0114] Code for the module is generated:

TABLE-US-00009 void tfhe_bootstrap_woKS_FFT_Module::code( ) // tfhe_bootstrap_woKS_FFT_Module thread { static const Torus32 mu = modSwitchToTorus32( 1, 8 ); for (int32_t h = 0; h < (FHE_FIFO_Size + 1); h++) // Create array of TorusPolynomials { testvect[h] = new_TorusPolynomial( N ); // N = 1024 bara[h] = new int32_t[ N ]; // N = 1024 for (int32_t i = 0; i < N; ++i) // Initialize bara[h] { bara[h][i] = 0; } } while (1) // An infinite loop { for (int32_t h = 0; h < (FHE_FIFO_Size + 1); h++) // Process a burst of input data { x_inStrm >> x; // Get next LweSample pointer from x_inStrm barb = modSwitchFromTorus32( x>b, Nx2 ); // Nx2 = 2048 for (int32_t i = 0; i < n; i++) { bara[h][i] = modSwitchFromTorus32( x>a[i], Nx2 ); // Nx2 = 2048 } x_inStrm.backwardAck( ); // Tell x_inStrm source that we're done with x for (int32_t i = 0; i < N; i++) // N = 1024 { testvect[h]>coefsT[i] = mu; } testvect_outStrm << testvect[h]; // Put testvect[h] into testvect_outStrm bara_outStrm << bara[h]; // Put bara[h] into bara_outStrm barb_outStrm << barb; // Put barb into barb_outStrm } } }

[0115] Finally, a streaming module is created:

TABLE-US-00010 class bootsAND_Topology: public streamModule// bootsAND_Topology streamModule { bootsAND_ModulebAND; tfhe_bootstrap_woKS_FFT_ModulewoKS;// tfhe_bootstrap_woKS_FFT_Module data member tfhe_blindRotateAndExtract_FFT_Module rotX; tfhe_blindRotate_FFT_TopologyrotTop; tLweExtractLweSample_ModulexSamp; IweKeySwitch_ModulekeySwitch; public: bootsAND_Topology( const TFheGateBootstrappingCloudKeySet* cks ) : bAND( cks ), woKS( cks>bkFFT ), rotX( cks>bkFFT>bk_params ), rotTop( cks>bkFFT ), xSamp( cks>bkFFT>accum_params ), keySwitch( cks, (char*)/Users/fredfurtek/Desktop/FCF MacBook Pro/QST/TruStreamCPP/TruStreamFHE/LweSAmple_result.txt ) { setName( bootsAND_Topology ); bAND >> woKS >> rotX >> rotTop >> xSamp >> keySwitch;// Create bootsAND_Topology pipeline end( ); } };

[0116] As a result, each box of FIG. 12 represents a streaming function module corresponding to a TFHE functionin which one more module input streams can provide the function and, one or more module output streams receive the output data from the TFHE function. The output data is eventually conveyed to another streaming function module. There is no passing of control or calling of other functions. Each streaming function module is a portion of the top level BootsAND topology. This topology allows the BootsAND operation to be reproduced on silicon with parallelizing and pipelining and thus allows for much greater efficiency and performance in processing the BootsAND function.

[0117] The biggest factor limiting the performance of TFHE is a 500-iteration for-loop in the TruStream module tfhe_blindRotate_FFT. In partial loop-unrolling, an n-iteration for-loop is replaced with a pipeline containing m for-loops, each with n/m iterations. In a partially unrolled pipeline, the loops are performed in parallel, while the steps within each loop are performed serially. In full loop-unrolling, an n-iteration for-loop is replaced with a loop-free pipeline containing n instances of each step in the for-loop. In a fully unrolled pipeline, all steps are performed in parallel.

[0118] FIG. 13 shows the bootsAND Top-Level topology with partial unrolling of the tfhe_tfhe_blindRotate_FFT Loop. In FIG. 13, there are 4 tfhe_blindRotate_FFT modules, each containing a for-loop with 125 iterations. In contrast, the bootsAND Top-Level topology of FIG. 12 has a single instance of the tfhe_blindRotate_FFT module, the instance containing a for-loop with 500 iterations. Of course, the bootsAND Top-Level topology can be further unrolled as is appropriate for any specific application.

[0119] FIG. 14 shows the top-level topology derived from the GswFFTExternMulToTLwe function.

[0120] It is necessary to determine and upper bound on the throughput of a streaming topology. Applicants have developed an algorithm for determining an upper bound on the throughput of a streaming topology that performs a sequence of operations: the upper bound on throughputin clock cycles per operationfor a Streaming topology is the maximum number of data values carried on a single topology stream during a single operation. This is so because a stream can transport data values at a maximum rate of one data value per clock cycle. For each stream, transport of data values for one operation must be completed before transport of data values for the next operation can begin. It follows that operations cannot be performed any faster than one operation per N clock cycles, where N is the maximum number of data values carried on a single stream during a single operation.

[0121] For example, the upper bound on throughput for the topology in FIG. 12 is: (The size of Ts_TlweSample in int32's)*(The number of loop iterations)

[0122] or 2,048*500=1,024,000 clock cycles per operation. While the upper bound on throughput for the topology in FIG. 13 is: (The size of Ts_TlweSample in int32's)*(The number of loop iterations) or 2,048*125=256,000 clock cycles per operation.

[0123] If the loop in FIG. 12 were to be fully unrolled, an upper bound on throughput of: (The size of Ts_TlweSample in int32's) or 2,048 clock cycles per operation would be achieved. The streaming topology described herein can achieve this upper bound because each core is able to: a) put a data value into its output stream(s) on every clock cycle, and b) get a data value from its input stream(s) on every clock cycle

[0124] Table 1 summarizes the bootsAND function throughput numbers for two clock frequencies: a). 125 MHz, the clock rate for some FPGA implementations of streaming topology, and b) 1 GHz, the expected clock rate for some custom-ASIC implementations of the topology.

TABLE-US-00011 TABLE 1 Throughput in Throughput in Throughput in Microseconds at Microseconds Clock Cycles 125 MHz at 1 GHz bootsAND (no 1,024,000 8,192 1,024 unrolling bootsAND (4x 256,000 2,048 256 unrolling bootsAND (full 2,048 16 2 unrolling

[0125] Using the numbers in Table 1, we are able to calculate the times needed to perform a thousand of most common arithmetic operations, including: addition, subtraction, min, max and average. Table 2 illustrates the times to perform a thousand of the most common arithmetic operations, including addition, subtraction, min, max, and average, using the streaming topology.

TABLE-US-00012 Milliseconds at Milliseconds Clock Cycles 125 MHz at 1 GHz bootsAND (no 1,024,000 8,192 1,024 unrolling bootsAND (4x 256,000 2,048 256 unrolling bootsAND (full 2,048 16 2 unrolling

[0126] It can be seen that the streaming topology described herein provides greatly enhanced efficiency in processing FHE functions on a computer. However, the core of FHE processing is Fast Fourier Transforms (FFT) and Inverse Fast Fourier Transforms (IFFT). Therefore, additional efficiencies can be gained if FFT and IFFT can be processed faster. Applicants have discovered that some known techniques for optimizing Fourier Transforms can be leveraged to create even more efficient processing in a streaming environment.

[0127] The Fourier transform (FT) decomposes a function of time into its constituent frequencies. The Fourier transform of a function of time is itself a complex-valued function of frequency, whose magnitude (modulus) represents the amount of that frequency present in the original function, and whose argument is the phase offset of the basic sinusoid in that frequency. The Fourier transform is not limited to functions of time, but the domain of the original function is commonly referred to as the time domain. The inverse Fourier transform mathematically synthesizes the original function from its frequency domain representation. Linear operations performed in one domain (time or frequency) have corresponding operations in the other domain, which are sometimes easier to perform. Therefore, Fourier Transforms have many applications in data processing and are critical to some FHE implementations.

[0128] Implementations described herein define new way to process FFTs and IFFTs. The FFT can then be mapped into a new computational implementation, such as the streaming topology described herein, with high parallelism. Further, implementations process an FFT of each polynomial and multiply term-wise in the frequency domain then convert back to the time domain. Conventional processing uses a coefficient representation (i.e. multiplies the coefficient of each term). Conventional computation costs are on the order of N.sup.2 squared (where N is order of polynomial). The method described herein yields a computation cost that is roughly NLog(N).

[0129] Implementations described herein create a pipeline architecture that calculates FFT algorithms with a special stage at the endpoints that calculate multiples of order N polynomials. This greatly reduces computational requirements.

[0130] The discrete Fourier Transform (DFT) of a finite length sequence of N is:

[00001]$\begin{array}{cc}X\left[k\right]={.Math.}_{n=0}^{N-1}x\left[n\right]W_N^{\mathrm{kn}},k=0,1,.Math.,N-1,& \left(1.1\right)\end{array}$$\mathrm{Where}{W}_N=e^{-j\left(\frac{2}{N}\right)}.\mathrm{The}\mathrm{inverse}\mathrm{discrete}\mathrm{Fourier}\mathrm{transform}\mathrm{is}\mathrm{given}\mathrm{by}$$\begin{array}{cc}x\left[n\right]=\frac{1}{N}{.Math.}_{k=0}^{N-1}X\left[k\right]W_N^{-\mathrm{kn}},n=0,1,.Math.,N-1.& \left(1.2\right)\end{array}$

[0131] Using Decimation in Frequency methodologies, we can divide the output sequence of the DFT into smaller subsequences with the following equations.

[00002]$\begin{array}{cc}X\left[2r\right]=\underset{n=0}{\overset{\left(N/2\right)-1}{.Math.}}\left(x\left[n\right]+x\left[n+\left(N/2\right)\right]\right)W_{N/2}^{\mathrm{rn}},r=0,1,.Math.,\left(N/2\right)-1.& \left(2.1\right)\end{array}$$\mathrm{Equation}\left(2.1\right)\mathrm{is}\mathrm{the}\left(N/2\right)\mathrm{points}\mathrm{DFT}\mathrm{of}\mathrm{the}\left(N/2\right)-\mathrm{point}\mathrm{sequence}g\left[n\right]=x\left[n\right]+x\left[n+\left(N/2\right)\right].$$\begin{array}{cc}X\left[2r+1\right]=\underset{n=0}{\overset{\left(N/2\right)-1}{.Math.}}\left(x\left[n\right]-x\left[n+\left(N/2\right)\right]\right)W_N^n{W}_{N/2}^{\mathrm{rn}},& \left(2.2\right)\end{array}$$r=0,1,.Math.,\left(N/2\right)-1.$

[0132] FIG. 15 graphically illustrates how Decimation-in-Frequency can be used to decompose an N=8-point DFT into two N/2=4 point DFTs by applying equation 2.1 for the even outputs and equation 2.2 for the odd outputs. FIG. 16 is a flow graph of decimation-in-frequency decomposition of an 8-point DFT into four two point DFTs. Note that, in FIG. 16, there are 3 columns/stages. The first column has 4 butterfly structures, each having an input and output. A butterfly structure of a DFT is a portion of the computation that breaks up the results of larger DFTs into sub-transforms. Each column FIG. 16 has 4 butterfly structures.

[0133] A basic flow graph of a butterfly structure is illustrated in FIG. 17. The input to the upper branch is p and the input to the lower branch is q Each butterfly structure can be mapped to a logic element and thus to a series of cores in a streaming topology. FIG. 18 is a logic element diagram of an FFT butterfly function. It can be seen that the logic is made up of standard logic elements (adders, multipliers . . . ). to create the flow graph, the complex inputs are divided into real and imagery parts for the computation. The upper input/output are for the real part, while the lower input/output are for the imagery part. The input/output is interleaved as p and q. The p and q input of the butterfly are selected from different addresses within the input buffer at different stages, as illustrated in FIG. 16. The fanout and FIFO accomplish this address selection. The add, subtraction and multiply logic elements are used to calculate real and imagery parts of the multiplication of complex inputs and the complex constant w. The p and q output of the butterfly are placed into the output buffer at different addresses at different stages, as illustrated in FIG. 16. The FanIn accomplishes this addressing.

[0134] FIG. 19 illustrates the butterfly function of FIG. 18 mapped to physical cores of a streaming topology. As described above, the cores include logic elements which can be configured to represent any processing algorithm. The result is that a single butterfly of one stage of an FFT has been mapped to silicon to define a streaming architecture for accomplishing the butterfly function. However, as discussed above, processing an FFT requires many butterfly functions.

[0135] The input sequence of an FFT (x[n]) can be also decomposed into smaller and smaller subsequences by applying Decimation-In-Time (DIT) transform algorithms. As discussed above, in the DIF algorithm, the decimation is done in the frequency domain. That's the reason, the frequency indices are in bit-reversed order. In DIT, we start, for example, with a single 8-point DFT, progress on to two 4-point DFTs and end with four 2-point DFTs by applying equation 3.1 below.

[00003]$\begin{array}{cc}\begin{array}{c}X\left[k\right]=\underset{r=0}{\overset{\left(N/2\right)-1}{.Math.}}x\left[2r\right]W_{N/2}^{\mathrm{rk}}+W_N^k\underset{r=0}{\overset{\left(N/2\right)}{.Math.}}x\left[2r+1\right]W_{N/2}^{\mathrm{rk}}X\left[k\right]\\ =G\left[k\right]+W_N^{k}H\left[k\right],k=0,1,.Math.,N-1.\end{array}& \left(3.1\right)\end{array}$

[0136] Each sum in equation (3.1) is the (N/2)-point DFT. The first sum is the (N/2)-point DFT of the even numbered points of the original input sequence and the second sum is the (N/2)-point DFT of the odd numbered points of the input sequence. FIG. 20 is a flow graph of DIT decomposition of an N=8 point DFT into two N/2=4 point computations. FIG. 21 is a flow chart of decimation-in-time decomposition of an 8-point DFT into four 2-point DFT computations. This is accomplished by applying equation 3.1 to continue to divide the N/2-point DFT into N/4-point DFTs until we obtain a 2-point FT. FIG. 22 is a diagram on an input butterfly operation of single stage. FIG. 23 is a logic element diagram of the butterfly of FIG. 22 obtained in a manner similar to that described above with respect to FIG. 18. FIG. 24 is the same logic mapped out on cores of the streaming topology described herein. Of course, the procedures described above can be used to map the logic diagrams to the cores.

[0137] FIG. 25 illustrates polynomial multiplication, showing coefficients representation and point-value pair representation. The top row of FIG. 25 is the conventional methodology. In the lower row of FIG. 25, in accordance with an implementation disclosed herein, FFT outputs A and B are pointwise multiplied to get C. subjecting the results of either method to an inverse (interpolation) algorithm achieves the same result. Given two polynomials

[00004]$A\left(x\right)={.Math.}_{j=0}^{n-1}{a}_j{x}^j\mathrm{and}B\left(x\right)={.Math.}_{j=0}^{n-1}{b}_j{x}^j,$

which are polynomials of degreebound n, their product, C(x)A(x)B(x) is a polynomial of degreebound 2n1.

[00005]$\begin{array}{cc}C\left(x\right)=\underset{j=0}{\overset{2n-2}{.Math.}}{c}_j{x}^j,& \left(4.1\right)\end{array}$$\mathrm{where}{C}_j={.Math.}_{k=0}^j{a}_k{b}_{j-k}$

[0138] Such a computation takes O(n.sup.2) time when we represent polynomial in the point-value format.

[00006]$\begin{array}{cc}c={\mathrm{IFFT}}_{2n}\left[{\mathrm{FFT}}_{2n}\left(a\right).Math.{\mathrm{FFT}}_{2n}\left(b\right)\right],& \left(4.3\right)\end{array}$

where, the vectors a and b are padded with zeros to length 2n, and .Math. denotes the component-wise of two 2n-length element vectors.

[0139] Given the fact that the elements in these vectors are real numbers (as opposed to complex numbers used as the standard input of an FFT) and the vectors have length of n and zero padded to length 2n, the FFT can be optimized by deploying a special first stage and an (N/2)-point FFT as shown in FIG. 25. As a result, the first stage of the optimized FFT has an equivalent logic flow that is very simple, as shown in FIG. 26. This yields a first stage streaming topology as shown in FIG. 27. A similar optimized (N/2) point IFFT (and corresponding relatively simple logic and streaming topology) can be used as the last stage for the same reasons. The special last stage is shown in FIG. 28. As a result, the last stage of the optimized IFFT has an equivalent logic flow that is very simple, as shown in FIG. 29. This yields a last stage streaming topology mapped onto cores as shown in FIG. 30.

[0140] In theory, to multiply two polynomials at order of N, an efficient way is to apply FFT to coefficients of each polynomial, pointwise multiply the FFT coefficients and perform the inverse FFT. The dimension of both the FFT and IFFT should be 2N. The coefficients of each polynomial are zero-padded to be a 2N dimension vector. The multiplication of two polynomials at order of N is in the order of 2N1. In TFHE, the modular arithmetic operation with a polynomial is required. After multiplication of two Torus polynomials, the final product (2N1 order polynomial) is reduced to modulo of X.sup.N+1 based on the following equations.

[00007]$c\left(i\right)=p\left(i\right)-p\left(N+i\right),i=0,1,.Math.,N-1$$c\left(N-1\right)=p\left(N-1\right)$

[0141] On the FFT implementation side, the FFT input is adjusted to achieve this modular operation before performing the 2N-point FFT by applying the following equations.

[00008]${\mathrm{fft}}_{\mathrm{in}\left(i\right)}=\frac{a\left(i\right)}{2},i=0,1,.Math.N-1$${\mathrm{fft}}_{\mathrm{in}\left(i\right)}=-\frac{a\left(i\right)}{2},i=N,N+1,.Math.2N-1$

[0142] Because of this unique input structure, the Decimation-in-Frequency Decomposition can be applies to optimize the FFT by deploying a special first stage and an (N)-point FFT. Similarly, the IFFT can optimized by deploying an (N)-point IFFT and a special last stage. Because of the modular arithmetic operation of polynomial in TFHE, there is no need to calculate the IFFT coefficients for i=N, N+1, . . . 2N1.

[0143] The stages of the streaming topologies for the FFT and the IFFT noted above can be connected to create a single streaming topology for each. The results are the FFT topology illustrated in FIGS. 31a-31d and the IFFT illustrated in FIGS. 32a-32d. Note that FIGS. 31a-31d include a special first stage 320 and FIGS. 32a-32d include a special last stage 330. It can be seen that the FFT and IFFT processed in the manner described above can be mapped to a relatively simple topology of cores in the streaming environment described herein. This allows FFTs and IFFTs to be processed in the streaming environment and thus allows FHE operations to be processed in the streaming environment. As noted above, the streaming topology causes a computing device to operate much more efficiently, and thus with reduced computing resources. It can be seen that all stages of the FFT and IFFT calculation are streamed. Conventional FFT calculation is accomplished in a recursive manner, one stage at a time. The implementations allow all stages of the FFT and IFFT to be laid out on hardware using multiple cores in the manner described above.

[0144] The embodiments disclosed herein can be used in connection with various computing platforms. The platforms may include electronic storage, one or more processors, and/or other components. Computing platforms may include communication lines, or ports to enable the exchange of information with a network and/or other computing platforms. The computing platforms may include a plurality of hardware, software, and/or firmware components operating together to provide the functionality attributed herein. Electronic storage may comprise non-transitory storage media that electronically stores information

[0145] Although the present technology has been described in detail for the purpose of illustration based on what is currently considered to be practical implementations, it is to be understood that such detail is solely for that purpose and that the technology is not limited to the disclosed implementations, but, on the contrary, is intended to cover modifications and equivalent arrangements that are within the spirit and scope of the appended claims. For example, it is to be understood that the present technology contemplates that, to the extent possible, one or more features of any implementation can be combined with one or more features of any other implementation.