2101.03403

## CryptoEmu: An Instruction Set Emulator for Computation Over Ciphers Xiaoyang Gong xgong35@wisc.edu Dan Negrut negrut@wisc.edu ## Abstract Fully homomorphic encryption (FHE) allows computations over encrypted data. This technique makes privacy-preserving cloud computing a reality. Users can send their encrypted sensitive data to a cloud server, get encrypted results returned and decrypt them, without worrying about data breaches. This project report presents a homomorphic instruction set emulator, CryptoEmu, that enables fully homomorphic computation over encrypted data. The software-based instruction set emulator is built upon an open-source, state-of-the-art homomorphic encryption library that supports gate-level homomorphic evaluation. The instruction set architecture supports multiple instructions that belong to the subset of ARMv8 instruction set architecture. The instruction set emulator utilizes parallel computing techniques to emulate every functional unit for minimum latency. This project report includes details on design considerations, instruction set emulator architecture, and datapath and control unit implementation. We evaluated and demonstrated the instruction set emulator's performance and scalability on a 48-core workstation. CryptoEmu has shown a significant speedup in homomorphic computation performance when compared with HELib, a state-of-the-art homomorphic encryption library. ## Index Terms Fully Homomorphic Encryption, Parallel Computing, Homomorphic Instruction Set, Homomorphic Processor, Computer Architecture. ## I. INTRODUCTION I N the conventional cloud service model, users share data with their service provide (cloud) to outsource computations. The cloud receives encrypted data and decrypts it with the cloud's private key or the private key shared between the user and the cloud. Thus, the service provider has access to user data, which might contain sensitive information like health records, bank statements, or trade secrets. Privacy concerns have been raised along with the wide adoption of cloud services. In 2019, over 164.68 million sensitive records were exposed in the United States [1]. In the worst-case scenario, the cloud service provider cannot be trusted. User data is inherently unsafe if it is in plain text. Even if the service provider is honest, cloud service is prone to fail victims of cybercrime. Security loopholes or sophisticated social engineering attacks expose user privacy on the cloud, and a successful attack usually results in a massive user data leak. One way to eliminate this type of risk is to allow the cloud to operate on the encrypted user data without decrypting it. Fully Homomorphic Encryption (FHE) is a special encryption scheme that allows arbitrary computation over encrypted data without knowing the private key. An FHE enabled cloud service model shown in Fig. 1. In this example, the user wants to compute the sum of 1, 3, 5 in the cloud. The user first encrypts data with FHE, then sends the cipher (shown in Fig. 1 as bubbles with blurry text) to the cloud. When the cloud receives encrypted data, it homomorphically adds all encrypted data together to form an encrypted sum and returns the encrypted sum to the user. The user decrypts the encrypted sum with a secret key, and the result in cleartext is 9 - the sum of 1, 3, and 5. In the entire process, the cloud has no knowledge of user data input and output. Therefore, user data is safe from the insecure cloud or any attack targeted at the cloud service provider. Fig. 1: Homomorphic Encryption <details> <summary>Image 1 Details</summary>  ### Visual Description ## Diagram: Secure Homomorphic Computation Workflow ### Overview The diagram illustrates a secure computation workflow involving two local systems and a cloud server. Data is encrypted, transmitted to the cloud for processing via a homomorphic sum operation, and then decrypted back locally. ### Components/Axes - **Left Local System**: - Contains three circles labeled `1`, `3`, and `5`. - An arrow labeled `Enc` points from the `3` to a blurred circle (encrypted value). - A `Send` arrow transmits the encrypted value to the cloud. - **Cloud**: - A blue rectangle labeled `Homomorphic SUM operation`. - Receives the encrypted value and performs computation. - **Right Local System**: - Contains a single circle labeled `9` (result of the sum). - A `Receive` arrow brings the encrypted result back. - A `Dec` arrow decrypts the result to `9`. ### Detailed Analysis - **Left Local System**: - Numbers `1`, `3`, and `5` are visible. Only `3` is explicitly encrypted (`Enc` arrow). - The `Send` arrow indicates transmission of the encrypted `3` to the cloud. - **Cloud**: - Performs a homomorphic sum operation. Homomorphic encryption allows computations (e.g., addition) on encrypted data without decryption. - **Right Local System**: - Receives the encrypted result (`9`) via `Receive`. - Decrypts the result (`Dec` arrow) to reveal `9`, matching the sum of `1 + 3 + 5`. ### Key Observations 1. **Encryption/Decryption**: Only the `3` is explicitly encrypted in the left system, suggesting partial data protection. 2. **Homomorphic Operation**: The cloud computes the sum of encrypted values (`3 + 5 + 1 = 9`) without accessing raw data. 3. **Flow Direction**: Data moves unidirectionally from left to right: encryption → transmission → cloud processing → decryption. ### Interpretation This diagram demonstrates **privacy-preserving computation** using homomorphic encryption. By encrypting data before transmission, sensitive information (e.g., `3`) remains confidential during cloud processing. The homomorphic sum operation enables secure aggregation of data (e.g., summing values across distributed systems) without exposing individual inputs. The final decrypted result (`9`) validates the correctness of the computation. **Notable Insight**: The workflow highlights a trade-off between security and computational overhead. While homomorphic encryption ensures data privacy, it introduces complexity in implementation and performance costs. The diagram assumes ideal conditions (e.g., no transmission errors, perfect encryption/decryption). </details> Blurry text in the figure denotes encrypted data. Over the years, the research community has developed various encryption schemes that enable computation over ciphers. TFHE [2] is an open-source FHE library that allows fully homomorphic evaluation on arbitrary Boolean circuits. TFHE library supports FHE operations on unlimited numbers of logic gates. Using FHE logic gates provided by TFHE, users can build an application-specific FHE circuit to perform arbitrary computations over encrypted data. While TFHE library has a good performance in gate-by-gate FHE evaluation speed and memory usage [3], a rigid logic circuit has reusability and scalability issues for general-purpose computing. Also, evaluating a logic circuit in software is slow. Because bitwise FHE operations on ciphers are about one billion times slower than the same operations on plain text, computation time ramps up as the circuit becomes complex. Herein, we propose a solution that embraces a different approach that draws on a homomorphic instruction set emulator called CryptoEmu. CryptoEmu supports multiple FHE instructions (ADD, SUB, DIV, etc.). When CryptoEmu decodes an instruction, it invokes a pre-built function, referred as functional unit, to perform an FHE operation on input ciphertext. All functional units are built upon FHE gates from TFHE library, and they are accelerated using parallel computing techniques. During execution, the functional units fully utilize a multi-core processor to achieve an optimal speedup. A user would simply reprogram the FHE assembly code for various applications, while relying on the optimized functional units. This report is organized as follows. Section 2 provides a primer on homomorphic encryption and summarizes related work. Section 3 introduces TFHE, an open-source library for fully homomorphic encryption. TFHE provides the building blocks for CryptoEmu. Section 4 describes CryptoEmu's general architecture. Section 5 and 6 provide detailed instruction set emulator implementations and gives benchmark results on Euler, a CPU/GPU supercomputer. Section 7 analyzes CryptoEmu's scalability and vulnerability, and compared CryptoEmu with a popular FHE software library, HELib [4]. Conclusions and future directions of investigation/development are provided in Section 8. ## II. BACKGROUND Homomorphic Encryption. Homomorphic encryption (HE) is an encryption scheme that supports computation on encrypted data and generates an encrypted output. When the encrypted output is decrypted, its value is equal to the result when applying equivalent computation on unencrypted data. HE is formally defined as follows: let Enc () be an HE encryption function, Dec () be an HE decryption function, f () be a function, g () be a homomorphic equivalent of f () , and a and b be input data in plaintext. The following equation holds: $$f ( a , b ) = D e c \left ( g ( E n c ( a ) , E n c ( b ) ) \right ) .$$ An HE scheme is a partially homomorphic encryption (PHE) scheme if g () supports only either addition or multiplication. An HE scheme is a somewhat homomorphic encryption (SWHE) scheme if a limited number of g () is allowed to be applied to encrypted data. An HE scheme is a fully homomorphic encryption (FHE) scheme if any g () can be applied for an unlimited number of times over encrypted data [5]. The first FHE scheme was proposed by Gentry [6]. In HE schemes, the plaintext is encrypted with Gaussian noise. The noise grows after every homomorphic evaluation until the noise becomes too large for the encryption scheme to work. This is the reason that SWHE only allows a limited number of homomorphic evaluations. Gentry introduced a novel technique called 'bootstrapping' such that a ciphertext can be homomorphically decrypted and homomorphically encrypted with the secret key to reduce Gaussian noise [6], [7]. Building off [6], [8] improved bootstrapping to speedup homomorphic evaluations. The TFHE library based on [3] and [9] is one of the FHE schemes with a fast bootstrapping procedure. Related work. This project proposed a software-based, multiple-instruction ISA emulator that supports fully homomorphic, general-purpose computation. Several general-purpose HE computer architecture implementations exist in both software and hardware. HELib [10] is an FHE software library the implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption scheme [11]. HELib supports HE arithmetic such as addition, subtraction, multiplication, and data movement operations. HELib can be treated as an assembly language for general-purpose HE computing. Cryptoleq [12] is a softwarebased one-instruction set computer (OISC) emulator for general-purpose HE computing. Cryptoleq uses Paillier partially homomorphic scheme [13] and supports Turing-complete SUBLEQ instruction. HEROIC [14] is another OISC architecture implemented on FPGA, based on Paillier partially homomorphic scheme. Cryptoblaze [15] is a multiple-instruction computer based on non-deterministic Paillier encryption that supports partially homomorphic computation. Cryptoblaze is implemented on the FPGA. ## III. TFHE LIBRARY TFHE [2] is an FHE C/C++ software library used to implement fast gate-by-gate bootstrapping. The idea of TFHE is straightforward: if one can homomorphically evaluate a universal logic gate and homomorphically evaluate the next universal logic gate that uses the previous logic gate's output as its input, one can homomorphically evaluate arbitrary Boolean functions, essentially allowing arbitrary FHE computations on encrypted binary data. Figure 2 demonstrates a minimum FHE gate-level library: NAND gate. Bootstrapped NAND gates are used to construct an FHE XOR gate. Similarly, any FHE logic circuit can be constructed with a combination of bootstrapped NAND gates. Fig. 2: Use of bootstrapped NAND gate to form arbitrary FHE logic circuit. Blurry text in the figure denotes encrypted data. <details> <summary>Image 2 Details</summary>  ### Visual Description ## Digital Logic Circuit Diagram: Combinational Logic Structure ### Overview The image depicts a digital logic circuit composed of multiple AND gates, input nodes (A and B), and an output node (Q). The diagram illustrates the flow of logical signals through interconnected gates, with no explicit numerical data or trends. ### Components/Axes - **Inputs**: - Node **A** (top-left) - Node **B** (bottom-left) - **Output**: - Node **Q** (rightmost) - **Logic Gates**: - All gates are **AND gates** (standard symbol: triangle with flat edge). - No explicit labels for individual gates (e.g., G1, G2), but their connections are visually distinct. ### Detailed Analysis 1. **Input Connections**: - **A** is connected to two AND gates: - One directly to the first gate (G1). - Another to a gate further downstream (G3). - **B** is connected to two AND gates: - One directly to G1. - Another to a gate further downstream (G2). 2. **Gate Connections**: - **G1**: Combines **A** and **B** (output feeds into G2 and G3). - **G2**: Combines output of G1 and **B** (output feeds into G4). - **G3**: Combines output of G1 and **A** (output feeds into G4). - **G4**: Combines outputs of G2 and G3 (output feeds into G5). - **G5**: Combines output of G4 and **A** (final output **Q**). 3. **Flow Direction**: - Signals flow from **A** and **B** through sequential AND gates, with intermediate outputs feeding into subsequent gates. - Final output **Q** is derived from the combination of all intermediate gate outputs and **A**. ### Key Observations - The circuit uses **only AND gates**, with no OR, NOT, or other gate types visible. - The structure suggests a **combinational logic** design, where the output **Q** depends solely on the current inputs **A** and **B**. - No feedback loops or sequential elements (e.g., flip-flops) are present. ### Interpretation This diagram represents a **combinational logic circuit** that processes inputs **A** and **B** through a series of AND gates to produce output **Q**. The specific Boolean function implemented depends on the arrangement of gates: - **G1** computes **A ∧ B**. - **G2** computes **(A ∧ B) ∧ B** (equivalent to **A ∧ B**). - **G3** computes **(A ∧ B) ∧ A** (equivalent to **A ∧ B**). - **G4** combines G2 and G3 outputs: **(A ∧ B) ∧ (A ∧ B)** (still **A ∧ B**). - **G5** combines G4 output with **A**: **(A ∧ B) ∧ A** (equivalent to **A ∧ B**). Thus, the final output **Q** simplifies to **A ∧ B**, indicating the circuit acts as a basic AND gate. However, the redundant gates suggest potential optimization opportunities or a placeholder for more complex logic. No numerical data, trends, or anomalies are present in the diagram. The focus is purely on the structural relationships between inputs, gates, and output. </details> TFHE API. TFHE library contains a comprehensive gate bootstrapping API for the FHE scheme [2], including secret-keyset and cloud-keyset generation; Encryption/decryption with secret-keyset; and FHE evaluation on a binary gate netlist with cloudkeyset. TFHE API's performance is evaluated on a single core of Intel Xeon CPU E5-2650 v3 @ 2.30GHz CPU, running CentOS Linux release 8.2.2004 with 128 GB memory. Table I shows the benchmark result of TFHE APIs that are critical to CryptoEmu's performance. TFHE gate bootstrapping parameter setup, Secret-keyset, and cloud-keyset generation are not included in the table. TABLE I: TFHE API Benchmark | API | Category | Bootstrapped? | Latency (ms) | |-----------------|------------------------|-----------------|----------------| | Encrypt | Encrypt decrypt | N/A | 0.0343745 | | Decrypt | Encrypt decrypt | N/A | 0.000319556 | | CONSTANT | Homomorphic operations | No | 0.00433995 | | NOT | Homomorphic operations | No | 0.000679717 | | COPY | Homomorphic operations | No | 0.000624117 | | NAND | Homomorphic operations | Yes | 25.5738 | | OR | Homomorphic operations | Yes | 25.618 | | AND | Homomorphic operations | Yes | 25.6176 | | XOR | Homomorphic operations | Yes | 25.6526 | | XNOR | Homomorphic operations | Yes | 25.795 | | NOR | Homomorphic operations | Yes | 25.6265 | | ANDNY | Homomorphic operations | Yes | 25.6982 | | ANDYN | Homomorphic operations | Yes | 25.684 | | ORNY | Homomorphic operations | Yes | 25.7787 | | ORYN | Homomorphic operations | Yes | 25.6957 | | MUX | Homomorphic operations | Yes | 49.2645 | | CreateBitCipher | Ciphertexts | N/A | 0.001725 | | DeleteBitCipher | Ciphertexts | N/A | 0.002228 | | ReadBitFromFile | Ciphertexts | N/A | 0.0175304 | | WriteBitToFile | Ciphertexts | N/A | 0.00960664 | In Table I, outside the 'Homomorphic operations' category, all other operations are relatively fast. In general, the latency is around 25ms, with exceptions of MUX that takes around 50ms, and CONSTANT, NOT, COPY that are relatively fast. The difference in speed is from gate bootstrapping. Unary gates like CONSTANT, NOT and COPY do not need to be bootstrapped. Binary gates need to be bootstrapped once. MUX needs to be bootstrapped twice. The bootstrapping procedure is manifestly the most computationally expensive operation in TFHE. This overhead is alleviated in CryptoEmu via parallel computing as detailed below. ## IV. CRYPTOEMU ARCHITECTURE OVERVIEW CryptoEmu is a C/C++ utility that emulates the behavior of Fully Homomorphic Encryption (FHE) instructions. The instruction set that CryptoEmu supports is a subset of ARMv8 A32 instructions for fully homomorphic computation over encrypted data. Figure 3 shows the abstract layer for an FHE application. For an FHE application that performs computation over encrypted data, the application will be compiled into FHE assembly that the instruction emulator supports. The instruction set emulator coordinates control units and functional units to decode and execute FHE assembly and returns final results. The design and implementation of CryptoEmu are anchored by two assumptions: Assumption 1. The instruction set emulator runs on a high-performance multi-core machine. Assumption 2. The cloud service provider is honest. However, the cloud is subject to cyber-attacks on the user's data. In §VII-C we will discuss modification on CryptoEmu's implementation when Assumption 2 does not hold. Cloud service model. Figure 4 shows the cloud service model. The instruction set emulator does what an actual hardware asset for encrypted execution would do: it reads from an unencrypted memory space an HE instruction ; i.e., it fetches Fig. 3: Abstract Layers <details> <summary>Image 3 Details</summary>  ### Visual Description ## Pyramid Diagram: Hierarchical Structure of FHE Components ### Overview The image depicts a four-tiered pyramid diagram illustrating the hierarchical relationship between components of a Fully Homomorphic Encryption (FHE) system. The pyramid structure suggests a foundational dependency model, with each level building upon the one below it. ### Components/Axes - **Top Tier (Smallest Box)**: - Label: "FHE Application" - Color: Light Blue (#ADD8E6) - **Second Tier**: - Label: "FHE Assembly" - Color: Light Orange (#FFA07A) - **Third Tier**: - Label: "FHE Functional Units" - Color: Light Blue (#ADD8E6) - **Base Tier (Largest Box)**: - Label: "Instruction Set Emulator" - Color: Light Orange (#FFA07A) **Spatial Grounding**: - All components are vertically stacked, centered, and proportionally sized to form a pyramid. - No legend, axes, or numerical data present. ### Detailed Analysis - **Color Pattern**: Alternating light blue and light orange tiers may indicate categorical grouping (e.g., application layer vs. infrastructure layer). - **Textual Content**: - "FHE Application" (top) - "FHE Assembly" (middle) - "FHE Functional Units" (lower) - "Instruction Set Emulator" (base) ### Key Observations 1. The pyramid’s base ("Instruction Set Emulator") is the largest, implying it is the foundational component. 2. "FHE Functional Units" directly support the "FHE Assembly," which in turn enables the "FHE Application." 3. No numerical values, trends, or quantitative data are present. ### Interpretation This diagram likely represents a layered architecture for FHE systems, where: - The **Instruction Set Emulator** provides the lowest-level computational framework. - **FHE Functional Units** (e.g., encryption/decryption modules) operate on top of the emulator. - **FHE Assembly** integrates these units into a cohesive system. - The **FHE Application** resides at the top, utilizing the assembled infrastructure. The alternating colors may serve to visually distinguish between "application-facing" (blue) and "infrastructure" (orange) components. The absence of numerical data suggests this is a conceptual model rather than a performance benchmark. </details> instruction that needs to be executed. The instruction set emulator also reads and writes HE data from an encrypted memory space, to process the user's data and return encrypted results to the encrypted memory space. The user, or any device that owns the user's secret key, will communicate with the cloud through an encrypted channel. The user provides all encrypted data to cloud. The user can send unencrypted HE instructions to the cloud through a secure channel. The user is also responsible for resolving branch directions for the cloud, based on the encrypted branch taken/non-taken result provided by the cloud. Fig. 4: Cloud service model <details> <summary>Image 4 Details</summary>  ### Visual Description ## Diagram: Cloud-User Interaction Architecture ### Overview The diagram illustrates a system architecture involving cloud-based components and a local user interface. It depicts bidirectional and unidirectional data flows between four key components: HE Instruction, Emulator, HE Data, and User. The system is divided into two sections: "Cloud" (containing three components) and "Local" (containing one component). ### Components/Axes 1. **Cloud Section** (Left side, orange/blue boxes): - **HE Instruction** (Orange box): Top-left position - **Emulator** (Blue box): Center position - **HE Data** (Orange box): Bottom-center position 2. **Local Section** (Right side, green box): - **User** (Green box): Right side 3. **Flow Arrows**: - **Bidirectional**: Between Emulator and HE Data (double-headed arrow) - **Unidirectional**: - Cloud → Local: Emulator → User (single-headed arrow) - Cloud Internal: HE Instruction → Emulator (single-headed arrow) ### Detailed Analysis - **HE Instruction** (Orange) → **Emulator** (Blue): - Represents input instructions from cloud-based high-expectation (HE) systems to the emulator. - **Emulator** (Blue) ↔ **HE Data** (Orange): - Indicates two-way communication between the emulator and cloud-based HE data storage/retrieval. - **Emulator** (Blue) → **User** (Green): - Shows output delivery from the emulator to the local user interface. ### Key Observations 1. **Bidirectional Data Flow**: The emulator maintains continuous interaction with HE Data, suggesting real-time processing or iterative feedback. 2. **Unidirectional User Output**: Final results only flow from the emulator to the user, implying a one-way presentation layer. 3. **Component Isolation**: The Cloud section operates independently of the Local section except through the emulator interface. ### Interpretation This architecture represents a hybrid cloud-local system where: - **HE Instruction** acts as a configuration/input module for cloud processing. - The **Emulator** serves as a central processing unit that: - Receives instructions from HE systems - Manages HE Data (possibly for simulation or validation purposes) - Delivers processed results to end-users - The **User** component represents the final interface layer, isolated from direct cloud interaction. The bidirectional flow between Emulator and HE Data suggests a dynamic system where cloud resources are continuously updated or validated during processing. The unidirectional user output emphasizes a controlled delivery mechanism, potentially for security or performance reasons. This design pattern is common in distributed systems requiring secure data handling while maintaining real-time user interaction. </details> ## A. Data Processing In actuality, the HE instruction and HE data can be text files or arrays of data bits stored in buffers, if sufficient memory is available. CryptoEmu employs a load-store architecture. All computations occur on virtual registers (vReg), where a vReg is an array of 32 encrypted data bits. Depending on the memory available on the machine, the number of total vReg is configurable. However, it is the compiler's responsibility to recycle vRegs and properly generate read/write addresses. A snippet of possible machine instructions is as follows: LOAD R1 ``` READ_ADDR1 READ_ADDR2 ``` LOAD R2 ``` ADD R0 R1, R2 STORE R0 WRITE_ADDR ``` Above, to perform a homomorphic addition, CryptoEmu fetches the LOAD instruction from the instruction memory. Because the instruction itself is in cleartext, CryptoEmu decodes the instruction, loads a piece of encrypted data from HE data memory indexed by READ ADDR1, and copies the encrypted data into vReg R1. Then, CryptoEmu increments its program counter by 4 bytes, reads the next LOAD instruction, and loads encrypted data from HE data memory into vReg R2. After the two operands are ready, CryptoEmu invokes a 32-bit adder and passes R1, R2 to it. The adder returns encrypted data in R0. Finally, CryptoEmu invokes the STORE operation and writes R0 data into the HE data memory pointed to by WRITE ADDR. Under Assumption 2, the honest cloud could infer some user information from program execution because HE instructions are in cleartext. However, all user data stays encrypted and protected from malicious attackers. Vulnerabilities are discussed in §VII-C. ## B. Branch and Control Flow CryptoEmu can perform a homomorphic comparison and generate N (negative), Z (zero), C (Unsigned overflow), and V (signed overflow) conditional flags. Based on conditional flags, the branch instruction changes the value of the program counter and therefore changes program flow. Because branches are homomorphically evaluated on the encrypted conditional flag, the branch direction is also encrypted. To solve this problem, CryptoEmu employs a client-server communication model from CryptoBlaze [15]. Through a secure communication channel, the cloud server will send an encrypted branch decision to a machine (client) that owns the user's private key. The client deciphers the encrypted branch decision and sends the branch decision encrypted with the server's public key to the server. The cloud server finally decrypts the branch decision, and CryptoEmu will move forward with a branch direction. Under assumption 2, the honest cloud will not use branch decision query and binary search to crack user's encrypted data, nor will the honest cloud infer user information from the user. In §VII-C, the scenario that assumption 2 does not hold will be discussed. ## V. DATA PROCESSING UNITS Data processing units are subroutines that perform manipulation on encrypted data, including homomorphic binary arithmetic, homomorphic bitwise operation, and data movement. Under Assumption 1, data processing units are implemented with OpenMP [16] and are designed for parallel computing. If the data processing units exhaust all cores available, the rest of the operations will be serialized. We benchmarked the performance of data processing units with 16-bit and 32-bit vReg size. Benchmarks are based an computing node on Euler. The computing node has 2 NUMA nodes. Each NUMA nodes has two sockets, and each socket has a 12-core Intel Xeon CPU E5-2650 v3 @ 2.30GHz CPU. The 48-core computing node runs CentOS Linux release 8.2.2004 with 128 GB memory. ## A. Load/Store Unit CryptoEmu employs a load/store architecture. A LOAD instruction reads data from data memory; a STORE instruction writes data to data memory. The TFHE library [2] provides the API for load and store operations on FHE data. If data memory is presented as a file, CryptoEmu invokes the specific LD/ST subroutine, moves the file pointer to the right LD/ST address, and calls the appropriate file IO API, i.e., ``` import_gate_bootstrapping_ciphertext_fromFile() or export_gate_bootstrapping_ciphertext_toFile() ``` Preferably, if the machine has available memory, the entire data file is loaded into a buffer as this approach significantly improves LD/ST instruction's performance. Table II shows LD/ST latency for 16-bit and 32-bit. LD/ST on a buffer is significantly faster than LD/ST on a file. The performance speedup is even more when the data file size is large because LD/ST on file needs to use fseek() function to access data at the address specified by HE instructions. TABLE II: LD/ST latencies. | | 16-bit (ms) | 32-bit (ms) | |----------------|---------------|---------------| | Load (file) | 0.027029 | 0.0554521 | | Store (file) | 0.0127804 | 0.0276899 | | Load (buffer) | 0.0043463 | 0.00778488 | | Store (buffer) | 0.0043381 | 0.0077692 | ``` #pragma omp parallel sections num_threads(2) { #pragma omp section { bootsAND(&g_o[0], &a_i[0], &b_i[0], bk); } #pragma omp section { bootsXOR(&p_o[0], &a_i[0], &b_i[0], bk); } } ``` Fig. 5: Parallel optimization for bitwise (g,p) calculation, get gp () ## B. Adder CryptoEmu supports a configurable adder unit of variable width. As for the ISA that CryptoEmu supports, adders are either 16-bit or 32-bit. Operating under an assumption that CryptoEmu runs on a host that supports multi-threading, the adder unit is implemented as a parallel prefix adder [17]. The parallel prefix adder has a three-stage structure: pre-calculation of generate and propagate bit; carry propagation; and sum computation. Each stage can be divided into sub-stages and can leverage a multi-core processor. Herein, we use the OpenMP [16] library to leverage parallel computing. Stage 1: Propagate and generate calculation. Let a and b be the operands to adder, and let a [ i ] and b [ i ] be the i th bit of a and b . In carry-lookahead logic, a [ i ] and b [ i ] generates a carry if a [ i ] AND b [ i ] is 1 and propagates a carry if a [ i ] XOR b [ i ] is 1. This calculation requires an FHE AND gate and an FHE XOR gate, see §III and Fig. 2 for gate bootstrapping. An OpenMP parallel region is created to handle two parallel sections. As shown in Fig. 5, CryptoEmu spawns two threads to execute two OpenMP sections in parallel. For a 16-bit adder, get gp() calculations are applied on every bit. This process is parallelizable: as shown in Fig. 6, CryptoEmu spawns 16 parallel sections [16], one per bit. Inside each parallel section, the code starts another parallel region that uses two threads. Because of nested parallelism, 32 threads in total are required to calculate every generation and propagate a bit concurrently. If there is an insufficient number of cores, parallel sections will be serialized, which will only affect the efficiency of the emulator. Stage 2: Carry propagation. Let G i be the carry signal at i th bit, P i be the accumulated propagation bit at i th bit, g i and p i be outputs from propagate and generate calculation. We define operator such that $$( g _ { x } , p _ { x } ) \odot ( g _ { y } , p _ { y } ) = ( g _ { x } + p _ { x } \cdot g _ { y } , p _ { x } \cdot p _ { y } ) \, .$$ Carry signal G i and accumulated propagation P i can be recursively defined as $$( G _ { i } , P _ { i } ) = ( g _ { i } , p _ { i } ) \odot ( G _ { i - 1 } , P _ { i - 1 } ) , w h e r e ( G _ { 0 } , P _ { 0 } ) = ( g _ { 0 } , p _ { 0 } ) \, .$$ The above recursive formula is equivalent to $$( G _ { i \colon j } , P _ { i \colon j } ) = ( G _ { i \colon n } , G _ { i \colon n } ) \odot ( G _ { m \colon j } , P _ { m \colon j } ) , w h e r e i \geq j a n d m \geq n \, .$$ Therefore, carry propagation can be reduced to a parallel scan problem. In CryptoEmu, we defined a routine, get carry() to perform operation . As shown in Fig. 7 , the requires two FHE AND gate and an FHE OR gate. CryptoEmu spawns two threads to perform the operation in parallel. For a 16-bit adder, we need 4 levels to compute the carry out from the most significant bit. As shown in fig 8, every two arrows that share an arrowhead represents one operation. The operations at the same level can be executed in parallel. In the case of a 16-bit adder, the maximum number of concurrent is 15 at level 1. Because of nested parallelism within the operation, the maximum number of threads required is 30. With a sufficient number of cores, parallel scan reduced carry propagation time from 16 times operation latency, to 4 times operation latency. Stage 3: Sum calculation. The last stage for parallel prefix adder is sum calculation. Let s i be the sum bit at i th bit, p i be the propagation bit at i th bit, G i be the carry signal at i th bit. Then $$s _ { i } = p _ { i } \, X O R \, G _ { i } \, .$$ One FHE XOR gate is needed to calculate 1-bit sum. For 16-bit adder, 16 FHE XOR gates are needed. All FHE XOR evaluation are independent, therefore can be executed in parallel. In total 16 threads are required for the best parallel optimization on sum calculation stage. ``` <loc_66><loc_61><loc_379><loc_273><_C++_>#pragma omp parallel sections num_threads(N) { #pragma omp section { get_gp(&g[0], &p[0], &a[0], &b[0], bk); } #pragma omp section { get_gp(&g[1], &p[1], &a[1], &b[1], bk); } ... #pragma omp section { get_gp(&g[14], &p[14], &a[14], &b[14], bk); } #pragma omp section { get_gp(&g[15], &p[15], &a[15], &b[15], bk); } } ``` Fig. 7: Parallel optimization for bitwise carry calculation, get carry () a) Benchmark: the 16-bit adder.: Table III shows benchmarking results for a 16-bit adder unit executed on the target machine describe earlier in the document. If parallelized, the 1-bit get gp() shown in Fig. 5 has one FHE gate latency around 25ms as shown in Table I. Ideally, if sufficient cores are available and there is no overhead from parallel optimization, (g,p) calculation should run 16 get gp() concurrently, and total latency should be 25ms. In reality, 16-bit (g,p) calculation uses 32 threads and takes 51.39ms to complete due to overhead in parallel computing. For carry propagation calculation, the 1-bit get carry() shown in Fig. 7 has two FHE gate latency of around 50ms when parallelized. In an ideal scenario, each level for carry propagation should run get carry() in parallel, and total latency should be around 50ms. In reality, the 16-bit carry propagation calculation uses 30 threads on level 1 and takes 93.42ms. A collection of 28 threads are used on carry propagation level 2; the operation takes 93.58ms. A collection of 24 threads are used on carry propagation level 3; the operation takes 80.34ms. Finally, 16 threads are used on carry propagation level 4; the operation takes 70.85ms. Fig. 8: Parallel scan for carry signals <details> <summary>Image 5 Details</summary>  ### Visual Description ## Flowchart: Multi-Stage Process with Labeled Components ### Overview The image depicts a multi-row flowchart with labeled boxes and directional arrows. Each row contains a sequence of boxes labeled with alphanumeric codes (e.g., G15-P15, G14-P14) and arrows connecting them. The arrows are labeled with additional codes (e.g., G15.14, P15.14), suggesting transitions or relationships between stages. The diagram appears to represent a structured process or system with hierarchical or sequential dependencies. ### Components/Axes - **Boxes**: Labeled with codes like `G15-P15`, `G14-P14`, `G13-P13`, etc. These likely represent distinct stages, components, or entities in the process. - **Arrows**: Labeled with codes like `G15.14`, `P15.14`, `G14.13`, etc. These indicate directional flow or interactions between boxes. - **Rows**: Organized into four distinct rows, each with a unique sequence of boxes and arrows. - **Legend**: No explicit legend is present, but the labels on boxes and arrows serve as identifiers. ### Detailed Analysis #### Row 1 (Top Row) - **Boxes**: `G15-P15`, `G14-P14`, `G13-P13`, `G12-P12`, `G11-P11`, `G10-P10`, `G9-P9`, `G8-P8`, `G7-P7`, `G6-P6`, `G5-P5`, `G4-P4`, `G3-P3`, `G2-P2`, `G1-P1`, `G0-P0`. - **Arrows**: Connect each box to the next in sequence (e.g., `G15-P15` → `G14-P14` → ... → `G0-P0`). - **Labels on Arrows**: `G15.14`, `P15.14`, `G14.13`, `P14.13`, ..., `G0.1`, `P0.1`. #### Row 2 - **Boxes**: `G15.14`, `G14.13`, `G13.12`, `G12.11`, `G11.10`, `G10.9`, `G9.8`, `G8.7`, `G7.6`, `G6.5`, `G5.4`, `G4.3`, `G3.2`, `G2.1`, `G1`, `P0`. - **Arrows**: Connect boxes in sequence (e.g., `G15.14` → `G14.13` → ... → `P0`). - **Labels on Arrows**: `G15.14`, `P15.14`, `G14.13`, `P14.13`, ..., `G0.1`, `P0.1`. #### Row 3 - **Boxes**: `G15.12`, `G14.11`, `G13.10`, `G12.9`, `G11.8`, `G10.7`, `G9.6`, `G8.5`, `G7.4`, `G6.3`, `G5.2`, `G4.1`, `G3.3`, `G2.2`, `G1.1`, `P0`. - **Arrows**: Connect boxes in sequence (e.g., `G15.12` → `G14.11` → ... → `P0`). - **Labels on Arrows**: `G15.12`, `P15.12`, `G14.11`, `P14.11`, ..., `G0.1`, `P0.1`. #### Row 4 - **Boxes**: `G15.8`, `G14.7`, `G13.6`, `G12.5`, `G11.4`, `G10.3`, `G9.2`, `G8.1`, `G7.7`, `G6.6`, `G5.5`, `G4.4`, `G3.3`, `G2.2`, `G1.1`, `P0`. - **Arrows**: Connect boxes in sequence (e.g., `G15.8` → `G14.7` → ... → `P0`). - **Labels on Arrows**: `G15.8`, `P15.8`, `G14.7`, `P14.7`, ..., `G0.1`, `P0.1`. #### Row 5 (Bottom Row) - **Boxes**: `G15`, `G14`, `G13`, `G12`, `G11`, `G10`, `G9`, `G8`, `G7`, `G6`, `G5`, `G4`, `G3`, `G2`, `G1`, `P0`. - **Arrows**: Connect boxes in sequence (e.g., `G15` → `G14` → ... → `P0`). - **Labels on Arrows**: `G15`, `P15`, `G14`, `P14`, ..., `G0.1`, `P0.1`. ### Key Observations 1. **Hierarchical Structure**: Each row represents a distinct level or phase of the process, with boxes labeled to reflect decreasing or increasing numerical values (e.g., `G15-P15` to `G0-P0`). 2. **Arrow Labels**: Arrows are labeled with codes that combine the source and target box codes (e.g., `G15.14` connects `G15-P15` to `G14-P14`). 3. **Repetition of Patterns**: The labels on boxes and arrows follow a consistent pattern, suggesting a systematic or algorithmic structure. 4. **Final Stage**: All rows converge on `P0`, indicating a terminal or output stage. ### Interpretation The diagram likely represents a multi-stage process or system with hierarchical dependencies. The labels on boxes (e.g., `G15-P15`, `G14-P14`) may denote specific components, stages, or entities, while the arrows (e.g., `G15.14`, `P15.14`) indicate transitions or interactions between them. The convergence on `P0` suggests a final output or resolution point. The structured repetition across rows implies a modular or iterative design, possibly for a computational, engineering, or organizational workflow. No numerical data or trends are present, as the diagram focuses on structural relationships rather than quantitative values. The absence of a legend or explicit axis titles limits direct interpretation of the labels, but their consistent formatting suggests a standardized coding system. </details> TABLE III: 16-bit adder latency <details> <summary>Image 6 Details</summary>  ### Visual Description ## Table: Latency Breakdown by Operation ### Overview The image presents a structured table detailing the latency (in milliseconds) associated with various computational operations. The table includes six rows, each representing a distinct operation, and two columns: "Operation" and "Latency (ms)". The values are precise, with varying decimal precision, and the final row aggregates the total latency, including overhead. ### Components/Axes - **Columns**: 1. **Operation**: Describes the computational task (e.g., "(g,p) calculation", "Carry propagation (Level 1)"). 2. **Latency (ms)**: Numerical values representing the time taken for each operation, measured in milliseconds. - **Rows**: 1. **(g,p) calculation**: 51.3939 ms 2. **Carry propagation (Level 1)**: 93.4178 ms 3. **Carry propagation (Level 2)**: 93.5273 ms 4. **Carry propagation (Level 3)**: 80.342 ms 5. **Carry propagation (Level 4)**: 70.8481 ms 6. **Sum calculation**: 34.2846 ms 7. **Total latency, including overhead**: 528.482 ms ### Detailed Analysis - **Latency Values**: - The **(g,p) calculation** has the second-highest latency at **51.3939 ms** (four decimal places). - **Carry propagation** latencies decrease progressively from **Level 1 (93.4178 ms)** to **Level 4 (70.8481 ms)**. - **Sum calculation** has the lowest latency at **34.2846 ms** (four decimal places). - **Total latency** aggregates all operations and overhead, totaling **528.482 ms**. - **Decimal Precision**: - **(g,p) calculation** and **sum calculation** use four decimal places, while others use two. This may reflect differing measurement granularity or reporting standards. ### Key Observations 1. **Carry Propagation Trends**: - Latency decreases by ~13 ms from Level 1 to Level 4, suggesting optimization or reduced complexity in higher levels. 2. **Overhead Contribution**: - The total latency (528.482 ms) exceeds the sum of individual operations (423.8137 ms) by **104.6683 ms**, indicating significant overhead not explicitly listed in the table. 3. **Precision Variability**: - Inconsistent decimal precision across operations may imply varying measurement tools or reporting conventions. ### Interpretation - **Operational Impact**: - **Carry propagation** dominates total latency, accounting for ~176 ms (33% of total). This suggests it is a critical bottleneck. - **Overhead** constitutes ~20% of total latency, highlighting inefficiencies in system design or process management. - **Design Implications**: - Optimizing **carry propagation** (e.g., reducing Level 1 latency) could yield the most significant performance gains. - The unexplained overhead warrants further investigation to identify hidden computational costs. - **Data Reliability**: - The mix of decimal precisions raises questions about measurement consistency. Standardizing reporting formats could improve data comparability. This table underscores the importance of granular latency analysis in identifying performance bottlenecks and optimizing computational workflows. </details> | Operation | Latency (ms) | |-----------------------------------|----------------| | (g,p) calculation | 51.3939 | | Carry propagation (Level 1) | 93.4178 | | Carry propagation (Level 2) | 93.5273 | | Carry propagation (Level 3) | 80.342 | | Carry propagation (Level 4) | 70.8481 | | Sum calculation | 34.2846 | | Total latency, including overhead | 528.482 | For sum calculation, 1-bit sum calculation uses one FHE XOR gate, with latency around 25ms. Ideally, if CryptoEmu runs all 16 XOR gates in parallel without parallel computing overhead, the latency for 16-bit sum calculation should be around 25ms. In reality, due to OpenMP overhead, the 16-bit sum calculation uses 16 threads and takes 34.28ms to complete. In total, a 16-bit adder's latency is 486.66ms. This result includes latency for all stages, plus overheads like variable declaration, memory allocation, and temporary variable manipulation. b) Benchmark: the 32-bit adder.: Table IV shows benchmarking results for a 32-bit adder unit executed on the target machine describe earlier in the document. Note that get gp() and get carry() have the same performance as the 16-bit adder. If sufficient cores are available, in the absence of OpenMP overhead, the (g,p) calculation should run 32 get gp() concurrently for 32-bit adder at a total latency of 25ms. In reality, the 32-bit (g,p) calculation uses 32 threads and takes 94.92ms to complete. TABLE IV: 32-bit adder latency | Operation | Latency (ms) | |-----------------------------------|----------------| | (g,p) calculation | 94.9246 | | Carry propagation (Level 1) | 147.451 | | Carry propagation (Level 2) | 133.389 | | Carry propagation (Level 3) | 127.331 | | Carry propagation (Level 4) | 112.268 | | Carry propagation (Level 5) | 91.5781 | | Sum calculation | 49.0098 | | Total latency, including overhead | 941.12 | For carry propagation calculation, if sufficient cores are available, each level for carry propagation should run get carry() in parallel. Without parallel computing overhead, total latency should be around 50ms. Level 0 of 32-bit carry propagation calculation uses 62 threads. Because the platform on which CryptoEmu is tested has only 48 cores, level 0 carry propagation calculation is serialized and takes 147.45ms to complete. Level 1 carry propagation calculation uses 60 threads, and similar to level 0, its calculation is serialized. Level 1 carry propagation calculation takes 133.39ms. Level 3 carry propagation calculation that uses 56 threads is serialized and takes 127.33ms to complete. Level 4 carry propagation calculation uses 48 threads, and it is possible to run every get carry() in parallel on our 48-core workstation. Level 4 carry propagation calculation takes 112.27ms. Level 5 carry propagation calculation uses 32 threads. It is able to execute all get carry() concurrently; level 5 takes 91.58ms to complete. For sum calculation, the 32-bit adder spawns 32 threads in parallel to perform FHE XOR operation if sufficient cores are available. The latency for the 32-bit sum calculation should be around 25ms. In reality, the 32-bit sum calculation uses 32 threads and takes 49ms to complete. In total, 32-bit adder's latency is 941.12ms. This result includes latency for all stages, plus overheads like variable declaration, memory allocation, and temporary variable manipulation. ## C. Subtractor The subtractor unit supports variable ALU size. CryptoEmu supports subtractors with 16-bit operands or 32-bit operands. Let a be the minuend, b be the subtrahend, and diff be the difference. Formula for 2's complement subtraction is: $$a + N O T ( b ) + 1 = d i f f \, .$$ As shown in Fig. 9, CryptoEmu reuses adder units in §V-B to perform homomorphic subtractions. On the critical path, extra homomorphic NOT gates are used to create subtrahend's complement. For a subtractor with N-bit operands, N homomorphic NOT operations need to be applied on the subtrahend. While all FHE NOT gates can be evaluated in parallel, in §III we showed that FHE NOT gates do not need bootstrapping, and is relatively fast (around 0.0007ms latency per gate) comparing to bootstrapped FHE gates. Therefore, parallel execution is not necessary. Instead, the homomorphic NOT operation is implemented in an iterative for-loop, as shown below: $$\begin{array} { r l } & { f o r ( i n t \, i = 0 ; \, i < N ; \, + + i ) } \\ & { b o o t s N O T ( \& b _ { - } n e g [ i ] , \, & b k [ i ] , \, b k ) ; } \end{array}$$ In addition to homomorphic NOT operation on subtrahend, the carry out bit from bit 0 needs to be evaluated with an OR gate because carry in is 1. Therefore, the adder in §V-B is extended to take a carry in bit. When sufficient cores are available on the machine, a subtractor units adds negation and carry bit calculation to the adder unit's critical path. Fig. 9: Subtractor architecture. Blurry text in the figure denotes encrypted data. <details> <summary>Image 7 Details</summary>  ### Visual Description ## Block Diagram: Binary Adder Circuit ### Overview The diagram illustrates a simplified digital adder circuit with two input bits (`a` and `b`), a carry-in input (`1`), and outputs for carry-out and result. The adder block processes the inputs to produce a binary sum and carry propagation. ### Components/Axes - **Inputs**: - `a` (top-left): Binary input bit. - `b` (top-right): Binary input bit. - `1` (bottom-left): Constant carry-in input (value = 1). - **Adder Block**: Central yellow rectangle labeled "Adder with carry." - **Outputs**: - `Carry out` (right): Propagated carry signal. - `Result` (bottom): Sum of `a`, `b`, and carry-in. ### Detailed Analysis - **Flow Direction**: - `a` and `b` flow into the adder block from the top. - The constant `1` (carry-in) enters from the left. - `Carry out` exits to the right. - `Result` exits downward. - **Key Connections**: - The `1` input is directly connected to the adder’s carry-in terminal, ensuring the circuit performs addition with a predefined carry. - The adder block’s output splits into two paths: `Carry out` (right) and `Result` (bottom). ### Key Observations - The diagram lacks numerical values or explicit logic gates (e.g., XOR, AND), focusing instead on high-level signal flow. - The constant `1` input suggests the adder is configured for a specific operation (e.g., incrementing a value by 1). - No feedback loops or additional components (e.g., registers, multiplexers) are shown. ### Interpretation This diagram represents a **1-bit full adder** with a fixed carry-in of `1`. The circuit adds two binary digits (`a` and `b`) along with the carry-in, producing a sum (`Result`) and a carry-out for chaining with higher-order bits. - **Functionality**: - If `a = 0` and `b = 0`, `Result = 1` (0 + 0 + 1 = 1, no carry-out). - If `a = 1` and `b = 1`, `Result = 1` with `Carry out = 1` (1 + 1 + 1 = 3 in binary: `11`). - **Design Implications**: - The absence of variable carry-in inputs limits flexibility but simplifies the circuit for specific use cases (e.g., fixed-increment operations). - The split output paths indicate modularity, allowing integration into larger multi-bit adder architectures. No numerical data or trends are present; the diagram focuses on structural relationships and signal propagation. </details> a) Benchmark.: Tables V and VI report benchmark results for the 16-bit and 32-bit subtractors on the target machine. Negation on the subtrahend takes a trivial amount of time to complete. The homomorphic addition is the most time-consuming operation in the subtractor unit. The homomorphic addition is a little slower than the homomorphic additions in §V-B because the adder needs to use extra bootstrapped FHE gates to process carry in and calculate carry out from sum bit 0. TABLE V: 16-bit subtractor latency <details> <summary>Image 8 Details</summary>  ### Visual Description ## Data Table: Latency Measurements for Operations ### Overview The image presents a data table comparing latency values (in milliseconds) for three computational operations: "Negation," "Add with carry," and "Total latency, including overhead." The table includes numerical values with high precision, suggesting a focus on performance metrics. ### Components/Axes - **Columns**: - **Operation**: Lists the computational tasks (Negation, Add with carry, Total latency). - **Latency (ms)**: Provides latency values for each operation. - **Rows**: - Three entries corresponding to the operations listed above. ### Detailed Analysis | Operation | Latency (ms) | |-------------------------|--------------------| | Negation | 0.0341106 | | Add with carry | 680.59 | | Total latency, including overhead | 715.015 | ### Key Observations 1. **Negation** has an extremely low latency of **0.0341106 ms**, indicating near-instantaneous execution. 2. **Add with carry** exhibits significantly higher latency (**680.59 ms**), suggesting computational complexity or resource contention. 3. **Total latency** (**715.015 ms**) is the sum of the two operations, confirming additive consistency in the data. ### Interpretation The data highlights a stark contrast in execution times between simple (Negation) and complex (Add with carry) operations. The total latency aligns with the sum of individual latencies, validating the table's internal consistency. The negligible overhead (715.015 ms - 680.59 ms = 34.425 ms) implies minimal additional system-level delays. This could reflect architectural optimizations or hardware acceleration for basic operations like negation. The disparity in latencies may inform performance bottlenecks in systems relying on these operations. </details> | Operation | Latency (ms) | |-----------------------------------|----------------| | Negation | 0.0341106 | | Add with carry | 680.59 | | Total latency, including overhead | 715.015 | ## D. Shifter CryptoEmu supports three types of shifters: logic left shift (LLS), logic right shift (LRS), and arithmetic right shift (ARS). Each shifter type has two modes: immediate and register mode. In immediate mode, the shift amount is in cleartext. For example, the following instruction shifts encrypted data in R0 to left by 1 bit and assigns the shifted value to R0. <details> <summary>Image 9 Details</summary>  ### Visual Description Icon/Small Image (238x17) </details> This instruction is usually issued by the cloud to process user data. Shift immediate implementation is trivial. The shifter calls bootCOPY() API to move all data to the input direction by the specified amount. The LSB or MSB will be assigned to an encrypted constant using the bootCONSTANT() API call. Because neither bootCOPY() nor bootCONSTANT() need to be bootstrapped, they are fast operations, see Table III. Therefore, an iterative loop is used for shifting. Parallel optimization is unnecessary. In register mode, the shift amount is an encrypted data stored in the input register. For example, the following instruction shifts encrypted data in R0 to left by the value stored in R1 and assign shifted value to R0. ``` LLS R0 R0 R1 ``` Because the shifting amount stored in R1 is encrypted, the shifter can't simply move all encrypted bits left/right by a certain amount. The shifter is implemented as a barrel shifter, with parallel computing enabled. a) Logic left shift.: Figure 10 shows the architecture for the 16-bit LLS. In the figure, numbers in the bubbles denote encrypted data in the shift register and the shift amount register. Numbers in the diamond denote an encrypted constant value generated by the bootsCONSTANT() API. The 16-bit LLS has four stages. In each stage, based on the encrypted shift amount, the FHE MUX homomorphically selects an encrypted bit from the shift register. In the end, the LLS outputs encrypted shifted data. FHE MUX is an elementary logic unit provided by TFHE library [2]. FHE MUX needs to be bootstrapped twice, and its latency is around 50ms. Therefore, it is reasonable to spawn multiple threads to execute all MUX select in parallel in each stage. For the 16-bit LLS, each stage needs 16 threads to perform a homomorphic MUX select, as shown in the following code: ``` its latency is around 50ms. Therefore, it is reasonable to spawn multiple threads to execute all MUX select stage. For the 16-bit LLS, each stage needs 16 threads to perform a homomorphic MUX select, as show code: { #pragma omp parallel sections num_threads(16) { #pragma omp section { bootsMUX(&out[0], &amt[0], &zero[0], &in[0], bk); } #pragma omp section { bootsMUX(&out[1], &amt[0], &in[0], &in[1], bk); } ... #pragma omp section { bootsMUX(&out[14], &amt[0], &in[13], &in[14], bk); } #pragma omp section { bootsMUX(&out[15], &amt[0], &in[14], &in[15], bk); } } ``` TABLE VI: 32-bit subtractor latency <details> <summary>Image 10 Details</summary>  ### Visual Description ## Table: Latency Analysis of Operations ### Overview The image presents a table comparing the latency (in milliseconds) of three operations: "Negation," "Add with carry," and "Total latency, including overhead." The data highlights significant differences in execution times between operations. ### Components/Axes - **Columns**: - **Operation**: Lists the computational operations analyzed. - **Latency (ms)**: Specifies the time taken for each operation in milliseconds. - **Rows**: 1. **Negation**: Latency = 0.0347466 ms. 2. **Add with carry**: Latency = 1058.65 ms. 3. **Total latency, including overhead**: Latency = 1115.25 ms. ### Detailed Analysis - **Negation**: The shortest latency at **0.0347466 ms**, indicating near-instantaneous execution. - **Add with carry**: Dominates with **1058.65 ms**, approximately **30,000x longer** than Negation. - **Total latency**: Sum of all operations and overhead, totaling **1115.25 ms**. This suggests overhead contributes **~56.6 ms** (1115.25 - 1058.65 - 0.0347466). ### Key Observations 1. **Add with carry** is the primary contributor to total latency, accounting for **~94.9%** of the total time. 2. **Overhead** (56.6 ms) is non-trivial, representing **~5.1%** of the total latency. 3. **Negation** has negligible impact on overall performance. ### Interpretation The data underscores that **Add with carry** is the critical bottleneck in this system. While Negation is nearly instantaneous, the Add operation’s high latency drives the total execution time. The overhead (56.6 ms) suggests additional system-level delays (e.g., context switching, memory access) that are not directly tied to the operations themselves. This highlights the need for optimization in Add with carry logic or hardware acceleration to reduce total latency. The stark contrast between operations also raises questions about the system’s design, as such a disparity may indicate inefficiencies in resource allocation or algorithmic complexity. </details> | Operation | Latency (ms) | |-----------------------------------|----------------| | Negation | 0.0347466 | | Add with carry | 1058.65 | | Total latency, including overhead | 1115.25 | Fig. 10: LLS architecture <details> <summary>Image 11 Details</summary>  ### Visual Description ## Digital Circuit Diagram: Configurable Shift Register/Multiplexer Array ### Overview The diagram depicts a complex digital circuit architecture featuring a grid of multiplexer (Mux) blocks arranged in a 16x4 matrix. The system includes labeled input registers ("Shift Reg"), configurable shift amounts, and output registers. The structure suggests a programmable data routing system with bit-level control. ### Components/Axes 1. **Vertical Axis (Left Side):** - Labeled "Shift Reg" at the top - 16 numbered registers (15-0) descending vertically - Each register feeds into a column of Mux blocks 2. **Horizontal Axis (Bottom):** - Labeled "Shift Amount" with values 0, 1, 2, 3 - Four columns of Mux blocks corresponding to shift values 3. **Output Section (Right Side):** - 16 output registers (15-0) mirroring input numbering - Each output register receives processed data from Mux blocks 4. **Mux Blocks:** - 64 total Mux elements (16 rows × 4 columns) - Each Mux has two inputs (A/B) and one output (Y) - Control signals not explicitly labeled but implied by shift amount ### Detailed Analysis 1. **Input Stage:** - 16-bit "Shift Reg" provides initial data - Each bit (15-0) feeds into the first column of Mux blocks 2. **Processing Stage:** - Four parallel Mux columns process data based on shift amount - Column 0 (shift=0): Direct passthrough - Column 1 (shift=1): Shifts data right by 1 bit - Column 2 (shift=2): Shifts data right by 2 bits - Column 3 (shift=3): Shifts data right by 3 bits - Mux selection logic determined by shift amount value 3. **Output Stage:** - Final outputs mirror input numbering (15-0) - Each output bit receives processed data from corresponding Mux column - Output configuration depends on selected shift amount ### Key Observations 1. **Bit Positioning:** - Higher-numbered bits (15-12) occupy top positions - Lower-numbered bits (3-0) occupy bottom positions - Consistent numbering across input/output stages 2. **Shift Behavior:** - Shift amount 0: No change in bit positions - Shift amount 1: Each bit moves to position n-1 - Shift amount 3: Bits 3-0 shift out of range (likely zero-padded) 3. **Control Mechanism:** - Shift amount selector likely uses binary encoding (00, 01, 10, 11) - No explicit control signals shown for Mux selection ### Interpretation This diagram represents a configurable bit-shifting system with programmable delay/routing capabilities. The architecture allows: - **Data Preservation:** Shift amount 0 maintains original bit positions - **Temporal Delay:** Higher shift amounts create progressive delays - **Bit Isolation:** Individual bit control through Mux configuration - **Parallel Processing:** Four simultaneous shift operations The system appears designed for applications requiring: - Configurable data pipelines - Bit-level signal manipulation - Parallel shift operations - Programmable delay elements Notable design considerations: 1. Missing explicit control logic for Mux selection 2. Potential overflow handling for shifts >3 3. No feedback paths shown for circular shifting 4. Assumed zero-padding for out-of-range shifts The diagram demonstrates a fundamental building block for advanced digital signal processing systems, combining shift register functionality with multiplexer-based reconfigurability. </details> In a parallel implementation with zero overhead, each stage should have one FHE MUX latency of around 50ms. Therefore, in an ideal scenario, four stages would have a latency of around 200ms. b) Benchmark: Logic left shift.: Table VII shows the benchmark results for the 16-bit LLS on the target platform. Each stage spawns 16 threads to run all FHE MUX in parallel with latency from 50-90ms, a latency that is in between 1 FHE MUX latency to 2 FHE MUX latency, due to parallel computing overhead. In total, it takes around 290ms to carry out a homomorphic LLS operation on 16-bit encrypted data. TABLE VII: 16-bit LLS latency | Operation | Latency (ms) | |-----------------------------------|----------------| | Mux select (Stage 1) | 87.3295 | | Mux select (Stage 2) | 82.2656 | | Mux select (Stage 3) | 76.6871 | | Mux select(Stage 4) | 55.5396 | | Total latency, including overhead | 287.92 | Table VIII shows the benchmark result for the 32-bit LLS. Each stage spawns 32 threads and takes around 90-100ms to complete. In total, it takes around 450-500ms for a homomorphic LLS operation on 32-bit encrypted data. TABLE VIII: 32-bit LLS latency | Operation | Latency (ms) | |-----------------------------------|----------------| | Mux select (Stage 1) | 101.92 | | Mux select (Stage 2) | 89.7695 | | Mux select (Stage 3) | 98.8634 | | Mux select(Stage 4) | 91.3939 | | Mux select (Stage 5) | 91.8491 | | Total latency, including overhead | 474.739 | c) Logic right shift/Arithmetic right shift.: LRS has an architecture that is similar to the architecture of LLS. Figure 11 shows the architecture for the 16-bit LRS. Compared to Fig. 10, the only difference between LLS and LRS is the bit order of the input register and output register. To reuse the LRS architecture for ARS, one should simply pass MSB of the shift register as the shift-in value, shown as the numbers in the diamond in Fig. 11. The LRS and ARS shifter implementation is similar to that of LLS. For 16-bit LRS/ARS, CryptoEmu spawns 16 parallel threads to perform a homomorphic MUX select at each stage. Table IX shows the benchmark result for the 16-bit LRS and ARS. LRS and ARS have similar performance. At each stage, LRS/ARS utilizes 16 threads, and each stage takes 50-90ms to complete. Single stage latency is between 1 FHE MUX latency to 2 FHE MUX latency, due to parallel computing overhead. In total, 16-bit LRS/ARS latency is around 290-300ms. TABLE IX: 16-bit LRS, ARS latency | Operation | LRS Latency (ms) | ARS Latency (ms) | |-----------------------------------|--------------------|--------------------| | Mux select (Stage 1) | 88.1408 | 87.7689 | | Mux select (Stage 2) | 85.5154 | 79.6416 | | Mux select (Stage 3) | 75.0295 | 75.2938 | | Mux select(Stage 4) | 55.9639 | 54.9246 | | Total latency, including overhead | 290.517 | 296.124 | Table X shows the benchmark result for the 32-bit LRS and ARS. The 32-bit LRS/ARS has five stages. Each stage creates 32 parallel threads to evaluate FHE MUX and takes 90-100ms to complete. Single stage latency is around 2 FHE MUX latency. In total, the 32-bit LRS/ARS takes around 470-500ms to complete a homomorphic LRS/ARS operation on 32-bit encrypted data. TABLE X: 32-bit LRS, ARS latency | Operation | LRS Latency (ms) | ARS Latency (ms) | |-----------------------------------|--------------------|--------------------| | Mux select (Level 1) | 104.33 | 106.132 | | Mux select (Level 2) | 104.75 | 95.3209 | | Mux select (Level 3) | 90.2377 | 90.1364 | | Mux select(Level 4) | 89.7183 | 90.5383 | | Mux select(Level 5) | 90.6315 | 94.4654 | | Total latency, including overhead | 472.896 | 491.787 | Fig. 11: LRS architecture <details> <summary>Image 12 Details</summary>  ### Visual Description ## Digital Circuit Diagram: Multiplexer-Based Shift Register Array ### Overview The diagram depicts a complex digital circuit composed of multiple multiplexers (Mux) arranged in a hierarchical structure. It includes a shift register (Shift Reg) on the left, a series of interconnected Mux blocks in the center, and an output section on the right. A "Shift Amount" control section is positioned at the bottom, suggesting variable data manipulation. The diagram uses standardized logic gate symbols and connectivity lines to represent signal flow. ### Components/Axes - **Left Section (Shift Reg)**: - Labeled "Shift Reg" with 16 input lines (0–15). - Each input connects to a Mux block via vertical lines. - **Central Section (Mux Array)**: - 16 columns of Mux blocks, each labeled "Mux". - Mux blocks are interconnected with horizontal and vertical lines, forming a grid-like structure. - Some Mux blocks have additional control lines (e.g., "0" and "1" inputs at the bottom). - **Right Section (Output)**: - Labeled "Output" with 16 output lines (0–15). - Each output line connects to a Mux block in the central section. - **Bottom Section (Shift Amount)**: - Labeled "Shift Amount" with 4 input lines (0–3). - Lines from this section connect to the Mux blocks, likely controlling shift operations. ### Detailed Analysis - **Shift Register (Shift Reg)**: - 16 input lines (0–15) suggest a 16-bit register. - Each input is routed to a corresponding Mux block, indicating parallel data processing. - **Mux Blocks**: - 16 columns of Mux blocks, each with multiple inputs and outputs. - Horizontal and vertical connections imply a tree-like structure for data routing. - Some Mux blocks have control inputs (e.g., "0" and "1" at the bottom), suggesting conditional selection. - **Output Section**: - 16 output lines (0–15) mirror the input structure, indicating a 16-bit output. - Output lines are connected to the final Mux blocks, which may perform final data selection or transformation. - **Shift Amount Control**: - 4 input lines (0–3) likely represent a 2-bit control signal (since 2² = 4). - These lines connect to the Mux blocks, enabling variable shift operations (e.g., shifting data by 0–3 positions). ### Key Observations - **Hierarchical Mux Structure**: The Mux blocks form a layered network, suggesting a multi-stage data processing pipeline. - **Symmetry in Input/Output**: The 16-input and 16-output lines indicate a balanced design for data flow. - **Control Signals**: The "Shift Amount" section introduces variability, allowing dynamic data manipulation. - **No Numerical Data**: The diagram lacks explicit numerical values beyond labels (e.g., 0–15, 0–3), focusing on structural relationships. ### Interpretation This diagram represents a **multiplexer-based shift register array**, likely used for advanced data manipulation in digital systems. The hierarchical Mux structure enables parallel processing, while the "Shift Amount" control allows variable bit shifting. The 16-bit input/output suggests applications in high-speed data routing, such as in microprocessors or signal processing units. The absence of numerical data implies the diagram focuses on architectural design rather than performance metrics. The interconnected Mux blocks may optimize data flow efficiency, reducing latency in complex operations. The "Shift Amount" control highlights the system's adaptability, making it suitable for tasks requiring dynamic bit manipulation. </details> ## E. Multiplier Design consideration. Binary multiplication can be treated as a summation of partial products [18], see Fig. 12. Therefore, adder units mentioned in §V-B can be reused for partial sum computation. Summing up all partial products is a sum reduction operation, and therefore can be parallelized. Fig. 12: Binary multiplication <details> <summary>Image 13 Details</summary>  ### Visual Description ## Matrix Diagram: Combinatorial Structure of A and B Elements ### Overview The image depicts a 4x5 matrix grid with labeled rows and columns. The rows are labeled A3, A2, A1, A0 (top to bottom), and the columns are labeled x, B3, B2, B1, B0 (left to right). Each cell contains a concatenated string of the row and column labels (e.g., A3B0, A2B1). Plus signs (+) are positioned in the leftmost cell of rows A2, A1, and A0, but not in the top row (A3). ### Components/Axes - **Row Labels (Vertical Axis):** A3, A2, A1, A0 (descending order). - **Column Labels (Horizontal Axis):** x, B3, B2, B1, B0 (left to right). - **Cell Content:** Each cell contains a string combining the row and column labels (e.g., A3B0, A2B1). - **Plus Signs (+):** Located in the leftmost cell of rows A2, A1, and A0 (columns x). ### Detailed Analysis - **Row A3:** Contains cells A3B0, A3B1, A3B2, A3B3 (no plus signs). - **Row A2:** Contains + (in x column), A2B1, A2B2, A2B3. - **Row A1:** Contains + (in x column), A1B1, A1B2, A1B3. - **Row A0:** Contains + (in x column), A0B1, A0B2, A0B3. - **Column x:** Contains no data in row A3; plus signs in rows A2, A1, A0. - **Column B0:** Contains A3B0, A2B0, A1B0, A0B0 (no plus signs). - **Column B3:** Contains A3B3, A2B3, A1B3, A0B3 (no plus signs). ### Key Observations 1. **Pattern of Plus Signs:** The plus signs are exclusively in the x column for rows A2, A1, and A0, suggesting a hierarchical or conditional relationship. 2. **Label Consistency:** All cell labels follow the format [Row Label][Column Label], with no deviations. 3. **Missing Data:** The top row (A3) lacks plus signs, while lower rows (A2, A1, A0) include them in the x column. 4. **Symmetry:** The grid is symmetric in structure but asymmetric in the placement of plus signs. ### Interpretation The matrix likely represents a combinatorial or hierarchical system where: - **A Elements (A3–A0):** Decreasing priority or hierarchy (e.g., A3 as highest, A0 as lowest). - **B Elements (B3–B0):** Decreasing priority or hierarchy (e.g., B3 as highest, B0 as lowest). - **Plus Signs:** Indicate a specific operation (e.g., addition, inclusion) or dependency between the x column and lower A rows. The absence of plus signs in the A3 row suggests A3 is a base or independent element. - **x Column:** Acts as a modifier or trigger for the plus signs in lower rows, possibly representing an external variable or condition. This structure could model a decision tree, a combinatorial matrix for operations, or a dependency graph where certain combinations (marked with +) require further action or validation. </details> However, the best parallel optimization cannot be achieved on our 48-core computing node. For a 16-bit wide multiplier, the product is a 32-bit encrypted value. Therefore, a 32-bit adder is required to carry out the homomorphic addition. Each 32-bit adder has peak thread usage of 64 threads: 31 threads with nested parallel (g,p) calculation that uses two threads. Thus, on the server used (with 48 cores), the 32-bit adder has to be partially serialized. For the 16-bit multiplier's parallel sum reduction, at most eight summation occur in parallel and each summation uses a 32-bit adder. The peak thread usage is 512 threads. For a 32-bit multiplier, maximum thread usage is 2048 threads. Thus, because homomorphic multiplication is a computationally demanding process, the server used does not have sufficient resources to do all operations in parallel. Homomorphic multiplication will thus show suboptimal performance on the server used in this project. Based on the design consideration above, CryptoEmu implements a carry-save multiplier [19] that supports variable ALU width. Carry-save multiplier uses an adder described in V-B to sum up partial products in series. - 1) Unsigned multiplication: Figure 13 shows the multiplier's architecture. For a 16-bit multiplier, A and B are 16-bit operands stored in vRegs. P is an intermediate 16-bit vReg to store partial products. Adder is a 16-bit adder with a carry in bit, see §V-B. On startup, vReg P is initialized to encrypted 0 using TFHE library's bootCONSTANT() API. Next, we enter an iterative loop and homomorphically AND all bits in vReg A with LSB of vReg B , and use the result as one of the operands to the 16-bit adder. Data stored in vReg P is then passed to the 16-bit adder as the second operand. The adder performs the homomorphic addition to output an encrypted carry out bit. Next, we right shift carry out, vReg P and vReg B , and reached the end of the iterative for-loop. We repeat the for-loop 16 times, and the final product is a 32-bit result stored in vReg P and vReg B . The pseudo-code below shows the 16-bit binary multiplication algorithm. ``` P = 0; for 16 times: (P, carry out) = P + (B[0] ? A : 0) [carry out, P, B] = [carry out, P, B] >> 1; return [P, B] ``` For implementation, an N-bit multiplier uses N threads to concurrently evaluate all the FHE AND gates. The adder is already parallel optimized. The rest of the multiplication subroutine is executed sequentially. Therefore, the multiplier is a computationally expensive unit in CryptoEmu. - a) Benchmark: Unsigned multiplication.: Table XI shows benchmark for 16-bit unsigned multiplication and 32-bit unsigned multiplication. A single pass for partial product summation takes around 715ms and 925ms, respectively. Total latency is roughly equal to N times single iteration's latency because summation operations are in sequence. - 2) Signed multiplication: Signed multiplication is implemented using the carry-save multiplier in Figure 13, with slight modifications. For N-bit signed multiplication, partial products need to be signed extended to 2N bit. Figure 14 shows the partial product summation for 4-bit signed multiplication. This algorithm requires a 2N-bit adder and a 2N-bit subtractor for TABLE XI: Unsigned multiplication latency | | 16-bit multiplier (ms) | 32-bit multiplier (ms) | |-----------------------------------|--------------------------|--------------------------| | Single iteration | 715.812 | 926.79 | | Total latency, including overhead | 11316.8 | 36929.2 | Fig. 13: Carry save multiplier <details> <summary>Image 14 Details</summary>  ### Visual Description ## Flowchart: Digital Circuit Process Flow ### Overview The image depicts a technical flowchart illustrating a digital circuit process involving multiple components connected via directional arrows. The system includes labeled blocks (P, B, LSB, A, Adder) and a NOT gate, with feedback loops and data flow paths. The diagram emphasizes binary logic operations and signal routing. ### Components/Axes - **Blocks**: - **P**: Input source (gray box). - **B**: Intermediate processing unit (orange box). - **LSB**: Sub-component of B (smaller orange box labeled "LSB"). - **A**: Secondary input/output unit (orange box). - **Adder**: Central processing unit (blue box). - **NOT Gate**: Binary logic inverter (standard logic symbol). - **Arrows**: Indicate data flow direction between components. - **Feedback Loops**: Two feedback paths from the Adder to B and A. ### Detailed Analysis 1. **Data Flow Paths**: - **P → B**: Primary input from P to B. - **B → LSB**: B routes data to its LSB sub-component. - **B → Adder**: B feeds into the Adder. - **A → Adder**: A feeds into the Adder. - **Adder → NOT Gate**: Adder output is inverted. - **NOT Gate → B**: Inverted signal feeds back into B. - **Adder → A**: Adder output also routes to A. 2. **Component Roles**: - **P**: Likely represents a power or primary input signal. - **B**: Processes data, with LSB handling lower-order bits. - **Adder**: Combines inputs from B and A, suggesting arithmetic operations. - **NOT Gate**: Introduces binary inversion, critical for feedback control. 3. **Feedback Mechanism**: - The Adder’s output is split into two paths: - One path inverts the signal (via NOT) and returns to B. - Another path routes directly to A, enabling iterative adjustments. ### Key Observations - **Binary Logic**: The presence of a NOT gate and LSB labeling confirms binary operations. - **Feedback Control**: The loop from Adder to B suggests error correction or stabilization. - **Modular Design**: Separation of B into B and LSB implies hierarchical processing. ### Interpretation This flowchart likely represents a **digital adder circuit with carry-lookahead logic** or a similar structure. The feedback loop from the Adder to B via the NOT gate indicates a control mechanism to adjust intermediate values (B) based on computation results, ensuring accuracy. The LSB sub-component suggests optimization for handling lower-order bits separately, common in high-speed arithmetic units. The dual feedback paths (to B and A) imply a system designed for iterative refinement, possibly in applications like digital signal processing or error-corrected memory systems. The modular design highlights efficiency in managing complex binary operations. </details> N-bit signed multiplication. The algorithm is further simplified with a 'magic number' [19]. Figure 15 shows the simplified signed multiplication. Based on this algorithm, the unsigned carry-save multiplier is modified to adopt signed multiplication. | | | | | A3 | A2 | A1 | AO | |------|------|-----------|------|----------------|-----------|------|----------| | A3B0 | A3B0 | | X | B3 | B2 | B1 | BO | | A3B1 | | A3B0 A3B1 | A3B0 | A3B0 | A2B0 A1B1 | | A1B0A0B0 | | | A3B1 | | A3B1 | A2B1 | | A0B1 | | | A3B2 | A3B2 | A3B2 | A2B2 | A1B2 | A0B2 | | | | A3B3 | A3B3 | | | A2B3 A1B3 A0B3 | | | | Fig. 15: Simplified signed binary multiplication <details> <summary>Image 15 Details</summary>  ### Visual Description ## Table: Signed Binary Multiplication ### Overview The image depicts a structured table illustrating the process of signed binary multiplication. It includes two primary sections: a detailed multiplication table and a summation table. The table uses algebraic notation (e.g., A3B0, A3B1) to represent terms, with signs (+, -) indicating positive or negative values. Red highlights emphasize specific terms in the multiplication table. ### Components/Axes - **Headers**: - Top row: `A3`, `A2`, `A1`, `A0` (multiplicand coefficients). - Leftmost column: `+`, `+`, `+`, `-` (signs of the multiplier terms). - **Multiplication Table**: - Rows correspond to multiplier terms (e.g., `A3B0`, `A3B1`, `A3B2`, `A3B3`). - Columns correspond to multiplicand terms (e.g., `A3`, `A2`, `A1`, `A0`). - Entries represent products of multiplier and multiplicand terms (e.g., `A3B0`, `A2B1`). - **Summation Table**: - Rows represent aggregated terms (e.g., `~A3B2`, `~A2B3`). - Final row: `1` (likely a carry or constant term). ### Detailed Analysis 1. **Multiplication Table**: - **Row 1 (+)**: - `A3B0` (A3 × B0), `A3B0` (A3 × B0), `A3B0` (A3 × B0), `A3B0` (A3 × B0). - Subsequent entries: `A3B1`, `A2B1`, `A1B1`, `A0B1`. - **Row 2 (+)**: - `A3B2`, `A3B2`, `A2B2`, `A1B2`, `A0B2`. - **Row 3 (+)**: - `A3B3`, `A3B3`, `A2B3`, `A1B3`, `A0B3`. - **Row 4 (-)**: - `A3B3` (negative sign applied). 2. **Summation Table**: - **Row 1**: `~A3B0`, `A2B0`, `A1B0`, `A0B0` (negative term `~A3B0` from the fourth row). - **Row 2**: `~A3B1`, `A2B1`, `A1B1`, `A0B1`. - **Row 3**: `~A3B2`, `A2B2`, `A1B2`, `A0B2`. - **Row 4**: `A3B3`, `~A2B3`, `~A1B3`, `~A0B3` (negative terms from the fourth row). - **Final Row**: `1` (likely a carry or normalization term). ### Key Observations - **Red Highlights**: Emphasize the terms `A3B0`, `A3B1`, `A3B2`, and `A3B3` in the multiplication table, suggesting these are critical for the final result. - **Sign Handling**: The `-` sign in the fourth row indicates a negative contribution from `A3B3`, which is later represented as `~A3B3` in the summation table. - **Aggregation**: The summation table combines terms with `~` to denote negative values, reflecting the signed nature of the multiplication. - **Final Term**: The `1` in the last row may represent a carry or a constant term added to the result. ### Interpretation This table demonstrates the step-by-step process of signed binary multiplication, where: 1. **Multiplier Terms**: Each row in the multiplication table corresponds to a term in the multiplier (e.g., `A3B0`, `A3B1`). 2. **Sign Propagation**: The `-` sign in the fourth row propagates to the summation table as `~A3B3`, ensuring correct handling of negative values. 3. **Term Aggregation**: The summation table combines all terms, with `~` indicating negative contributions. The final `1` suggests a carry or normalization step, common in binary arithmetic. 4. **Red Highlights**: Likely emphasize the most significant terms (e.g., `A3B0`, `A3B1`, `A3B2`, `A3B3`) in the multiplication process. The structure aligns with standard binary multiplication algorithms, where each term is computed, signed, and summed to produce the final result. The use of `~` for negative terms and the final `1` highlights the importance of sign management and carry propagation in signed binary operations. </details> a) Benchmark: Signed multiplication.: The unsigned multiplication was modified for signed multiplication based on the simplified algorithm outlined above. Table XII shows benchmark results for the 16-bit and 32-bit signed multiplications. A single pass for partial product summation takes roughly 745ms and 1155ms, respectively. The total latency for signed multiplication is around N times that of the single iteration. TABLE XII: Signed multiplication latency <details> <summary>Image 16 Details</summary>  ### Visual Description Icon/Small Image (574x53) </details> | | 16-bit multiplier (ms) | 32-bit multiplier (ms) | |-----------------------------------|--------------------------|--------------------------| | Single iteration | 742.8 | 1154.77 | | Total latency, including overhead | 13120.6 | 34826 | ## F. Divider CryptoEmu supports unsigned division over encrypted data. Figure 16 shows the flow chart for a non-restoring division algorithm for unsigned integer [20]. The division algorithm is based on sequential addition/subtraction. In every iteration, the MSB of vReg A decides whether the divider takes an addition or subtraction. This function is implemented building off the adder in §V-B. The MSB of vReg A is passed as the SUB bit into the adder. In the adder, the second operand b is homomorphically XORed with the SUB bit and then added with the first operand A and SUB bit. If FHE XOR gates are evaluated in parallel and parallel computing overhead is ignored, the adder with add/sub select is about 1 FHE XOR gate slower than regular adders. Note that, the integer divide instruct does not care about the value of remainder because the result will be rounded down (floor) to the closest integer, and therefore remainder calculation is skipped to save computation time. The unsigned division algorithm is a sequential algorithm. Within each iteration, a parallel optimized adder subroutine is invoked. Like multiplication, the unsigned division algorithm is computationally expensive. Pseudocode for the 16-bit unsigned division is shown below. ``` invoked. Like multiplication, the unsigned division is shown below. Non-restoring Division: A = 0; D = Divisor Q = Dividend for 16 times: [A, Q] = [A, Q] << 1 if A < 0: A = A + D else: A = A - D if A < 0: Q[0] = 0; else: Q[0] = 1; ``` a) Benchmark.: Table XIII provides benchmark results for the 16-bit and 32-bit unsigned integer divisions. Performance for a single iteration is slightly slower than homomorphic addition because one iteration uses an adder-subtractor unit. The division algorithm is sequential, and the total latency for N-bit division is around N times that of a single iteration's latency. TABLE XIII: Unsigned division latency <details> <summary>Image 17 Details</summary>  ### Visual Description Icon/Small Image (536x53) </details> | | 16-bit divider (ms) | 32-bit divider (ms) | |-----------------------------------|-----------------------|-----------------------| | Single iteration | 769.063 | 1308.67 | | Total latency, including overhead | 11659.5 | 38256.5 | ## G. Bitwise operations and data movement CryptoEmu supports several homomorphic bitwise operations and data movement of configurable data size. The instruction set supports 16-bit and 32-bit bitwise operation and data movement. The collection of bitwise operations includes homomorphic NOT, AND, OR, XOR, and ORN, in both immediate mode and register mode. All homomorphic bitwise operations except bitwise NOT are implemented with parallel computing optimizations. For the N-bit bitwise operation, CryptoEmu spawns N threads to carry out all FHE gate evaluation in parallel. Bitwise NOT operation is an exception because the FHE NOT gate does not need to be bootstrapped and is relatively fast. Parallel computing cannot be justified because of its overhead. The following code shows a generic way to implement N-bit parallel bitwise operations using the TFHE and OpenMP libraries. ``` #pragma omp parallel sections num_threads(16) { #pragma omp section { bootsAND(&out[0], &a[0], &b[0], bk); } ``` <details> <summary>Image 18 Details</summary>  ### Visual Description ## Flowchart: Division Algorithm with Bit Shifting and Conditional Adjustments ### Overview The flowchart depicts a computational algorithm for division or binary adjustment operations. It initializes variables, performs iterative adjustments to a value `A` based on comparisons with zero, and uses bit-shifting operations on a pair `[A, Q]`. The process terminates when a counter `Count` reaches a threshold `N`. ### Components/Axes - **Start**: Initialization block setting `A = 0`, `D = Divisor`, `Q = Dividend`, `Count = 0`. - **Decision Nodes**: - `A < 0?` (diamond-shaped decision box). - `Count < N?` (final decision box). - **Process Boxes**: - `[A, Q] = [A, Q] << 1` (bitwise left shift operation). - `A = A + D` or `A = A - D` (conditional adjustments). - `Q[0] = 0` or `Q[0] = 1` (binary assignment). - **End**: Termination block. ### Detailed Analysis 1. **Initialization**: - `A` starts at 0. - `D` is defined as the divisor. - `Q` is defined as the dividend. - `Count` starts at 0. 2. **First Decision (`A < 0?`)**: - **Yes**: - `[A, Q]` is left-shifted by 1 bit. - `A` is incremented by `D`. - **No**: - `[A, Q]` is left-shifted by 1 bit. - `A` is decremented by `D`. 3. **Second Decision (`A < 0?`)**: - **Yes**: Assign `Q[0] = 0`. - **No**: Assign `Q[0] = 1`. 4. **Loop Control (`Count < N?`)**: - If `Count` has not reached `N`, the process loops back to the first decision node. - If `Count >= N`, the algorithm terminates. ### Key Observations - The algorithm uses bit-shifting (`<< 1`) to manipulate `[A, Q]`, suggesting a focus on binary representation or efficiency. - Conditional adjustments (`A ± D`) imply a search for a remainder or alignment with a divisor. - The final assignment `Q[0] = 0/1` indicates binary output, possibly representing a quotient bit. - The loop condition `Count < N` suggests iterative refinement over `N` steps. ### Interpretation This flowchart likely implements a **division algorithm** or **binary approximation method**. The use of bit-shifting and conditional adjustments resembles techniques in: - **Restoring Division Algorithms**: Where `A` is adjusted to approach zero, and `Q` accumulates quotient bits. - **Newton-Raphson Division**: Iterative refinement of a quotient estimate. - **Fixed-Point Arithmetic**: Efficient computation on hardware with limited precision. The algorithm’s reliance on `Count < N` implies a trade-off between precision (more iterations) and computational cost. The final `Q[0]` value (`0` or `1`) could represent the least significant bit of the quotient, with higher bits determined in earlier iterations. The flowchart’s structure emphasizes deterministic, step-by-step refinement, typical of low-level arithmetic operations in embedded systems or hardware design. </details> Fig. 16: Binary division algorithm ``` Fig. 16: Binary division algorithm #pragma omp section { bootsAND(&out[1], &a[1], &b[1], bk); } ... #pragma omp section { bootsAND(&out[N-2], &a[N-2], &b[N-2], bk); } #pragma omp section { bootsAND(&out[N-1], &a[N-1], &b[N-1], bk); } } ``` Data movement instructions support homomorphic operations such as bit field clear, bit field insert, bit-order reverse, and byteorder reverse. Because data movement uses TFHE library's non-bootstrapped APIs like bootsCOPY() and bootsCONSTANT() , they are not implemented via OpenMP parallel sections. a) Benchmark.: Table XIV provides benchmark results for 16-bit and 32-bit bitwise operation and data movement instructions. When parallel optimized, an N-bit bitwise operation spawns N threads. For bitwise operation with bootstrapped FHE gate, latency is between 1-2 FHE gates when all threads are in parallel. The performance of the N-bit bitwise NOT and data movement instructions that are implemented sequentially is proportional to N times the corresponding TFHE API's latency. TABLE XIV: Bitwise operation and data movement latency | Operation | Category | Parallel? | 16-bit latency (ms) | 32-bit latency (ms) | |-------------|--------------------|-------------|-----------------------|-----------------------| | AND(imm) | Bitwise operations | Yes | 26.9195 | 27.1288 | | AND(reg) | Bitwise operations | Yes | 47.7228 | 55.4597 | | OR(imm) | Bitwise operations | Yes | 28.1923 | 27.8774 | | OR(reg) | Bitwise operations | Yes | 47.6171 | 50.089 | | XOR(imm) | Bitwise operations | Yes | 29.2375 | 27.9389 | | XOR(reg) | Bitwise operations | Yes | 47.1986 | 50.3683 | | ORN(imm) | Bitwise operations | Yes | 27.8467 | 27.776 | | ORN(reg) | Bitwise operations | Yes | 47.6422 | 57.0639 | | NOT(imm) | Bitwise operations | Yes | 0.0072794 | 0.0116968 | | NOT(reg) | Bitwise operations | No | 0.006089 | 0.01232 | | BFC | Bitwise operations | No | 0.0028094 | 0.0026892 | | BFI | Bitwise operations | No | 0.003278 | 0.0033974 | | RBIT | Bitwise operations | No | 0.0104582 | 0.0216222 | | REV | Bitwise operations | No | 0.0097926 | 0.0187618 | ## VI. CONTROL UNITS A control unit decides and/or changes the value of the program counter (PC), which in CryptoEmu is an integer in cleartext. CryptoEmu supports conditional execution that generates encrypted conditional flags defined in the ARM ISA. Based on conditional flags, the branch unit decides the branch direction to take. The PC is set to a cleartext that points to an HE instruction address when branch is taken, or increased by 4 if the branch is not taken. ## A. Conditional Flags The conditional unit handles NZCV flags defined in the ARM architecture. The N (negative) flag is set if an instruction's result is negative. The Z (zero) flag is set if an instruction's result is zero. The C (carry) flag is set if an instruction's results in an unsigned overflow. The V (overflow) flag is set if an instruction's results in an signed overflow. NZCV values are stored as encrypted data in a vReg. An instruction can be conditionally executed to update NZCV's value. The following code shows HE assembly for a while loop. Note that all data in this example is encrypted. ``` HE assembly for a while loop. Note that C++: int i = 42; while(i != 0) i--; HE assembly: MOV R0 R0 42 Loop_label: SUBS R0 R0 1 B_NE Loop_label ``` After the SUBS instruction is executed, the NZCV vReg is updated with results in R0. Based on the value of the Z flag, the program counter either updates its value to SUBS' instruction address (branch taken) or increases by 4 (branch non-taken). Because the homomorphic evaluation of a conditional flag is computationally expensive, an ordinary data processing unit does not have a mechanism to update a conditional flag. In reality, instructions like ADDS, SUBS, and MULS are treated as micro-ops and completed in two steps: homomorphic data processing and homomorphic conditional flag calculation. The N flag calculation is straight forward. CryptoEmu takes the MSB of result vReg and assigns it to the NZCV vReg. For the C flag, CryptoEmu takes the carry out result from previous unsigned computation and assigns it to the NZCV vReg. For the Z flag, the conditional unit performs an OR reduction on the input vReg, and assigns a negated result to the NZCV vReg. OR reduction can be parallelized. For a 16-bit conditional unit, OR reduction has four stages and maximum thread usage is eight. For a 32-bit conditional unit, OR reduction has five stages and maximum thread usage is 16. Finally, for the V flag, we take the sign bit (MSB) of two operands and the result for a signed computation, denoted as a , b , and s , respectively. Overflow is then evaluated as $$o v = \left ( \bar { a } \cdot \bar { b } \cdot s \right ) + \left ( a \cdot b \cdot \bar { s } \right ) .$$ Note that the conditional unit calculates overflow in parallel by executing (¯ a · ¯ b · s ) and ( a · b · ¯ s ) concurrently. a) Benchmark.: Table XV shows benchmark results for the 16-bit and 32-bit conditional units. The N flag and C flag calculations are fast because they do not have bootstrapped FHE gates. The Z flags and V flags are calculated at the same time. For conditional flag calculation on N-bit result, the maximum thread usage is N/ 2 + 2 threads. Z flag and V flag's latency dominates the total latency. TABLE XV: Conditional flag latency | | 16-bit (ms) | 32-bit (ms) | |-----------------------------------|---------------|---------------| | N flag | 0.0214161 | 0.0204952 | | C flag | 0.0007251 | 0.0002539 | | Z flag and V flag | 115.811 | 168.728 | | Total latency, including overhead | 115.901 | 169.843 | ## B. Branch CryptoEmu has a vReg virtual register reserved for the program counter (PC). The PC stores a cleartext value that points at an HE instruction address. CryptoEmu loads an HE instruction from PC, decodes the instruction, invokes the data processing unit to execute the instruction, and repeats. Normally when using the ARM A32 ISA, the next instruction address that CryptoEmu is at the current PC plus 4. However, branch instructions can modify the PC value based on conditional flags, and therefore decide the next instruction address CryptoEmu fetches from. For example, the following code branches to ADDRESS LABEL because SUBS instruction sets the Z flag. ``` MOV R0 R0 1 SUBS R0 R0 1 B_NE ADDRESS_LABEL ``` §VI-A discussed conditional flag calculation. The NZCV flag is stored in a vReg as encrypted data. The cloud needs to know the value of the NZCV flags to decide which branch direction to take. However, the cloud has no knowledge of NZCV value unless it is decrypted by the user. CryptoEmu adopts a server-client communication model from CryptoBlaze [15]. As demonstrated in Fig. 17, the cloud (server) first homomorphically evaluates an HE instruction and updates the NCZV vReg. Next, the cloud sends the encrypted NCZC value and branch condition to the client. User deciphers the encrypted NCZC value, and sends a branch taken/non-taken decision back to the cloud through a secure channel. Once the cloud learns the branch decision, the PC will either be updated to PC+4, or to the branch address. Fig. 17: Server-client model for branch resolution Blurry text in the figure denotes encrypted data. <details> <summary>Image 19 Details</summary>  ### Visual Description ## Component Diagram: Cloud-User Interaction Flow ### Overview The diagram illustrates a bidirectional interaction between a "Cloud" component and a "User" component, mediated by two labeled ovals: "NCZV Flags" and "Branch Direction." Arrows indicate directional flow between the components, suggesting a networked or process-driven relationship. ### Components/Axes - **Left Box**: Labeled "Cloud" (light blue background, black text). - **Right Box**: Labeled "User" (light orange background, black text). - **Oval 1**: Positioned above the arrow from "Cloud" to "User," labeled "NCZV Flags." - **Oval 2**: Positioned below the arrow from "User" to "Cloud," labeled "Branch Direction." - **Arrows**: - Top arrow: From "Cloud" to "User," passing through "NCZV Flags." - Bottom arrow: From "User" to "Cloud," passing through "Branch Direction." ### Detailed Analysis - **Cloud Component**: Positioned on the left, serving as the origin for the top arrow. No additional attributes or sub-components are visible. - **User Component**: Positioned on the right, acting as the destination for the top arrow and the origin for the bottom arrow. - **NCZV Flags**: An oval element acting as a mediator or checkpoint in the Cloud-to-User flow. The term "NCZV" may denote a specific protocol, validation mechanism, or flagging system (context-dependent). - **Branch Direction**: An oval element mediating the User-to-Cloud flow. The label implies a decision point or routing mechanism determining the path of data or processes. ### Key Observations 1. **Bidirectional Flow**: The diagram emphasizes two-way communication between Cloud and User, with distinct mediators for each direction. 2. **Mediator Roles**: - "NCZV Flags" likely governs permissions, authentication, or routing rules for Cloud-to-User interactions. - "Branch Direction" may represent conditional logic (e.g., A/B testing, failover paths) for User-to-Cloud responses. 3. **Simplified Representation**: No numerical data, scales, or legends are present, focusing purely on structural relationships. ### Interpretation This diagram likely represents a simplified architecture for a cloud-based system interacting with end-users. The "NCZV Flags" could enforce security policies or prioritize traffic, while "Branch Direction" might handle dynamic routing based on user behavior or system state. The bidirectional arrows suggest real-time synchronization or feedback loops, common in distributed systems. The absence of quantitative data implies the diagram is conceptual, emphasizing process flow over measurable metrics. The use of distinct colors (light blue for Cloud, light orange for User) visually reinforces the separation of roles, aiding in quick comprehension of the system's architecture. </details> ## VII. RESULTS This section reports on ( i ) the scalability with respect to bit count when the core count is a fixed number; ( ii ) the scalability with respect to core count when the data size is a fixed number; ( iii ) on CryptoEmu's potential vulnerabilities; and ( iv ) comparison against the state of the art. ## A. Scalability with respect to bit count Table I shows the latency of the TFHE library API. Non-bootstrapped gates such as CONSTANT, NOT, and COPY are three to four orders of magnitude faster than bootstrapped gates. Therefore, compared to bootstrapped gates, non-bootstrapped gates are considered as negligible in the CryptoEmu's performance equation. Functional units without bootstrapped gates are not included in our scalability analysis. The latency of a single bootstrapped gate is denoted as G . In the rest of the subsection, we analyzed the scalability of functional unit subroutines with respect to data size N. Two scenarios are considered: single core mode, and multi-core mode with a sufficient number of cores to do all intended parallel computation concurrently. CryptoEmu uses all available cores to concurrently perform homomorphic computation on encrypted data with multi-core mode latency. When CryptoEmu exhausted all core resources, the rest of the program will be serialized with single-core mode latency. a) Adder.: An adder has 3 stages: Generate and propagate calculation, carry calculation, and sum calculation. Let the available core number be 1 (single core mode); then, the time complexity for each stage is: Generate and propagate calculation : To compute generate and propagate for one bit, two bootstrapped FHE gates evaluations are required. With N-bit operands, total latency is 2 · G · N . Carry calculation : Three bootstrapped FHE gates evaluations are required to calculate the carry out bit. With N-bit operands, total latency is 3 · G · N . Sum calculation : One bootstrapped XOR gate is needed to calculate one sum bit. With N-bit operands, total latency is G · N Total latency : The latency for adder with single core is 6 · G · N . Time complexity is O ( N ) . Table XVI summarizes the discussion above for the N-bit adder with one core available. TABLE XVI: Adder scalability, single core | Operation | Latency | Time complexity | |-------------------|-----------|-------------------| | (g,p) calculation | 2 GN | O ( N ) | | Carry calculation | 3 GN | O ( N ) | | Sum calculation | GN | O ( N ) | | Total latency | 6 GN | O ( N ) | Assume a sufficient but fixed number of processors are available. Then, the latencies become: Generate and propagate : Calculation for generate and propagate for one bit can be executed in parallel, with a latency of one bootstrapped FHE gate. Given N-bit operands, N calculations can be carried out concurrently. Therefore, the latency for the (g,p) calculation is G . Carry calculation : Carry out computation for one bit can be executed in parallel, with a latency of two bootstrapped FHE gates. For N-bit operands, carry calculation is divided into log ( N ) stages. Operations in the same stage are executed in parallel. Therefore, latency for carry calculation is 2 · G · log ( N ) . Sum calculation : Each sum bit needs one bootstrapped XOR gate. For N-bit operands, N computations can be executed in parallel. Total latency for sum calculation is G . Total latency : The total latency for an adder with sufficient yet fixed number of cores is 2 · G · log ( N )+2 G . Time complexity is O ( log ( N )) . Table XVII summarizes the scalability analysis discussion for the N-bit adder with sufficient, yet fixed number of cores available. TABLE XVII: Adder scalability, multiple core | Operation | Latency | Time complexity | |-------------------|---------------------|-------------------| | (g,p) calculation | G | O (1) | | Carry calculation | 2 G · log ( N ) | O ( log ( N )) | | Sum calculation | G | O (1) | | Total latency | 2 G · log ( N )+2 G | O ( log ( N )) | b) Subtractor.: A subtractor performs homomorphic negation on subtrahend, and homomorphically adds subtrahend's complement to minuend using an adder with carry in of one. Negation uses TFHE library's non-bootstrapped NOT gate, and its latency is negligible. Adding a carry to the adder uses two extra bootstrapped gates. Therefore, the total latency for subtractor is Latency ( Adder ) + 2 · G . Table XVIII summarizes key scalability aspects for the N-bit subtractor with single core and with sufficient yet fixed number of cores available. TABLE XVIII: Subtractor scalability | # of cores | Latency | Time complexity | |--------------|------------------|-------------------| | Single core | 6 GN +2 G | O ( N ) | | Multi-core | 2 Glog ( N )+4 G | O ( log ( N )) | Shifter. For shifting with cleartext immediate, the operation is essentially a homomorphic data movement operation using the TFHE library's COPY and CONSTANT API. Shifting with immediate latency is therefore negligible compared to the rest of function units in CryptoEmu. . Shifting with encrypted vReg is implemented as a barrel shifter. For vReg N-bit shift, the operation has log ( N ) stages. In each stage, individual bits are selected by bits in the shifting amount vReg moves to the next stage through a MUX. The TFHE MUX has latency around 2 · G . When a single core is used, each stage has N MUXs. Latency in one stage is 2 · G · N . There are log ( N ) stages, therefore total shifter latency for a single core processor is 2 · G · N · log ( N ) . When sufficient cores are given, MUXs of the same stage can be evaluated in parallel, resulting in a latency of 2 · G . There are log ( N ) stages, therefore total shifter latency for processor with sufficient cores is 2 · G · log ( N ) . Table XIX summarizes key scalability aspects for the shifter with respect to bit count N, in single core and multi-core mode. TABLE XIX: Shifter scalability | # of cores | Latency | Time complexity | |--------------|---------------|-------------------| | Single core | 2 GNlog ( N ) | O ( Nlog ( N )) | | Multi-core | 2 Glog ( N ) | O ( log ( N )) | c) Multiplier.: The multiplier is implemented with iterative multiplication algorithms. A multiplier with N-bit operands requires N times iterations. N-bit unsigned multiplication contains an N-bit FHE AND evaluation and invokes an N-bit adder for every iteration. When running unsigned multiplication with a single core, sequential latency for N-bit FHE AND is N · G . Sequential latency for the N-bit adder is 6 · G · N . Latency for one iteration is 7 · G · N . Total latency for the N-bit unsigned multiplication 7 · G · N 2 . When sufficient number of cores are provided to run subroutines in parallel, parallel latency for the N-bit FHE AND is G . Parallel latency for N-bit adder is 2 · G · log ( N ) + 2 G . One iteration takes 2 · G · log ( N ) + 3 G to complete. Total latency for N-bit unsigned multiplication is 2 · G · N · log ( N ) + 3 · G · N . Signed multiplication has the same latency per iteration as in unsigned multiplication. N-bit signed multiplication involves an N-bit addition that adds an offset to the upper half of the 2N-bit product. This operation has sequential latency of 6 · G · N and parallel latency of 2 · G · log ( N ) + 3 G . Total latency for signed multiplication is therefore 7 · G · N 2 +6 · G · N for single core, and 2 · G · N · log ( N ) + 3 · G · N +2 · G · log ( N ) + 3 G if a sufficient number of cores is available. Table XX summarizes key scalability aspects (latency and time complexity) for the unsigned and signed multiplication with respect to bit count N, in single core and multi-core mode. TABLE XX: Multiplier scalability | unsigned? | # of cores | Latency | Time complexity | |-------------|--------------|--------------------------------------|-------------------| | Yes | Single core | 7 GN 2 | O ( N 2 )) | | Yes | Multi-core | 2 GNlog ( N )+3 GN | O ( Nlog ( N )) | | No | Single core | 7 GN 2 +6 GN | O ( N 2 )) | | No | Multi-core | 2 GNlog ( N )+3 GN +2 Glog ( N )+3 G | O ( Nlog ( N )) | d) Divider.: The divider is implemented with iterative non-restoring division algorithm. A divider with N-bit operands requires N iterations. Every iteration involves negligible non-bootstrapped gates and an adder-subtractor unit. The addersubtractor selectively inverts the second operand based on the value in the SUB bit. Then the subroutine invokes an adder to add the first operand, processes the second operand, and SUB bit together to form a result. For computation on single core, selective inversion for an N-bit operand uses N FHE XOR gates, and therefore has a latency of G · N . Adder with carry in has 6 · G · N +2 · G latency. Latency per iteration is 7 · G · N +2 · G , and total latency is 7 · G · N 2 +2 · G · N for single core. If enough cores are available, the N-bit selective inversion can be executed in parallel, resulting in G latency. Adder with carry in parallel computing mode has 2 · G · log ( N ) + 4 · G latency. Latency per iteration is 2 · G · log ( N ) + 5 · G , and total latency is 2 · G · N · log ( N ) + 5 · G · N . Table XXI shows latency and time complexity results for the unsigned division with respect to bit count N, in single core and multi-core modes. TABLE XXI: Divider scalability | # of cores | Latency | Time complexity | |--------------|--------------------|-------------------| | Single core | 7 GN 2 +2 GN | O ( N 2 )) | | Multi-core | 2 GNlog ( N )+5 GN | O ( Nlog ( N )) | e) Bitwise operations.: Bitwise operation evaluates all input bits with one FHE gate. Latency per bit is G . For N-bit bitwise operation in single core mode, total latency is G · N . In multi-core mode, because all FHE gate evaluations are in parallel, the total latency is G . Table XXI shows latency and time complexity data for bitwise operation with respect to bit count N, in single core and multi-core mode. TABLE XXII: Bitwise ops scalability | # of cores | Latency | Time complexity | |--------------|-----------|-------------------| | Single core | GN | O ( N ) | | Multi-core | G | O (1) | f) Conditional Flags.: Conditional flags calculation involves four sub-calculations: N flag, Z flag, C flag, and V flag. N flag and C flag calculations are trivial. Z flag calculation contains an OR reduction operation. In single core mode, the N-bit Z flag calculation has a latency of G · N . In multi-core mode, the OR reduction is executed in parallel. N-bit OR reduction is broken down into log ( N ) stages, and in each stage, the FHE OR gates are evaluated in parallel. The N-bit Z flag latency for parallel computing is Glog ( N ) . The V flag calculation uses five gates regardless of the size of the input vReg. In single core mode, V flag calculation has 5 · G latency. In multi-core mode because V flag calculation can be partially optimized with parallel computing, the latency is 3 · G . Therefore, total latency for single core mode is G · N +5 · G , and total latency for multi-core mode is G · log ( N ) +3 · G . Table XXIII shows latency and time complexity data for conditional flag calculation with respect to the bit count N, in single core and multi-core mode. TABLE XXIII: Conditional flags scalability | # of cores | Latency | Time complexity | |--------------|----------------|-------------------| | Single core | GN +5 G | O ( N ) | | Multi-core | Glog ( N )+3 G | O ( log ( N )) | ## B. Scalability with respect to core count CryptoEmu's performance is dictated by the extent to which it can rely on parallel computing. In ideal scenario, the processor has enough cores to enable any collection of tasks that can be performed in parallel to be processed as such. Sometimes, a part of the execution of an instruction takes place in parallel, but the rest is sequential because all CPU core resources are exhausted. In the worst case scenario, the processor has only one core and all computations are sequential/serialized. Assume that the size of the functional units is 16-bit. Peak thread usage is then 32 threads, where each thread performance an FHE gate evaluation. On the server used in this study, which has 48 cores distributed over four CPUs, we vary the number of cores available to carry our emulation from 1 core to 48 cores. This amounts to a strong scaling analysis. We created scenarios where ( i ) the instruction set can draw on one core only and therefore the computation is sequential; ( ii ) the instruction set has insufficient cores and parallel computation is mixed with sequential computation; and ( iii ) the instruction set can count on sufficient cores to do all emulation in parallel. a) Adder.: Figure 18 shows the 16-bit adder's compute time with respect to core count. From the chart, the adder's latency decreases when the core count increases from 1 to 32. The adder reached its optimal speed at around 32 core count and has a slight decrease in speed when the core count exceeds 32. Adder's maximum speedup from parallel computing is around 7.78x. Fig. 18: Time vs Core count <details> <summary>Image 20 Details</summary>  ### Visual Description ## Bar Chart: Adder: Time vs Core count ### Overview The chart visualizes the relationship between computational core count (x-axis) and execution time in milliseconds (y-axis) for an "Adder" operation. Time decreases as core count increases, with a notable plateau after a certain core threshold. ### Components/Axes - **Title**: "Adder: Time vs Core count" - **X-axis (Core count)**: - Labels: Odd integers from 1 to 47 (1, 3, 5, ..., 47) - Scale: Discrete increments of 2 cores (e.g., 1, 3, 5, ..., 47) - **Y-axis (Time (ms))**: - Labels: 0, 500, 1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500, 5000 - Scale: Linear increments of 500 ms - **Bars**: - Color: Blue (no legend present) - Height: Proportional to execution time ### Detailed Analysis - **Core 1 & 3**: Highest execution times (~4400 ms each), indicating sequential processing dominates at low core counts. - **Core 5**: Time drops to ~2300 ms, showing initial parallelization benefits. - **Core 7-9**: Further reduction to ~1300 ms, with minor fluctuations. - **Core 11**: Time stabilizes at ~900 ms, marking a plateau. - **Core 13-47**: Execution time remains relatively flat (~600-700 ms), with slight variations (e.g., ~650 ms at core 15, ~600 ms at core 31). ### Key Observations 1. **Diminishing Returns**: Time reduction slows significantly after core 11, suggesting parallelization overhead or algorithmic limitations. 2. **Odd-Numbered Cores**: All core counts are odd, possibly reflecting test case design constraints. 3. **Stability**: Post-core 11, time varies minimally (±50 ms), indicating saturation of performance gains. ### Interpretation The data demonstrates that increasing core count reduces computation time for the Adder operation up to ~11 cores, after which parallelization efficiency plateaus. This aligns with Amdahl's Law, where sequential bottlenecks limit scalability. The odd-numbered core counts may reflect hardware/software constraints (e.g., thread grouping). The plateau suggests that beyond 11 cores, adding more resources yields negligible time savings, highlighting the need for algorithmic optimization or hybrid parallel-sequential approaches for larger core counts. </details> b) Subtractor.: Figure 19 shows the 16-bit subtractor's compute time with respect to core count. The 16-bit subtractor uses at most 32 cores to compute in parallel. The subtractor's latency decreases as the core count increases from 1-32, and reaches its maximum performance at around 32 core count. At and beyond 32 core count, all parallel optimizations are enabled. When the core counts saturate the subtractor's parallel computing requirement, the latency of the subtractor is around 700ms. The subtractor's maximum speedup from parallel computing is about 8.49x. Fig. 19: Time vs Core count <details> <summary>Image 21 Details</summary>  ### Visual Description ## Bar Chart: Subtractor: Time vs Core count ### Overview The chart visualizes the relationship between computational core count and execution time (in milliseconds) for a "Subtractor" algorithm. Execution time decreases as core count increases, with a sharp decline at lower core counts followed by a plateau at higher counts. ### Components/Axes - **Title**: "Subtractor: Time vs Core count" - **X-axis (Core count)**: Discrete values from 1 to 47, labeled at intervals of 2 (1, 3, 5, ..., 47). - **Y-axis (Time, ms)**: Continuous scale from 0 to 6000 ms, with gridlines at 1000 ms intervals. - **Bars**: Blue vertical bars representing execution time for each core count. No explicit legend is present. ### Detailed Analysis - **Core 1**: Execution time peaks at ~5000 ms. - **Core 3**: Time drops to ~4500 ms. - **Cores 5–11**: Gradual decline, with times ranging from ~1800 ms (core 5) to ~1000 ms (core 11). - **Cores 13–47**: Time stabilizes between ~600 ms and ~700 ms, with minimal variation. - **Trend**: Execution time decreases non-linearly at lower core counts, then plateaus after ~11 cores. ### Key Observations 1. **Diminishing Returns**: The most significant time reduction occurs between 1 and 11 cores. Beyond this, additional cores yield negligible improvements (~600–700 ms). 2. **Outlier**: Core 1 exhibits the highest execution time (~5000 ms), suggesting single-core inefficiency. 3. **Stability**: Cores 31–47 show consistent performance (~600–700 ms), indicating saturation of parallel processing benefits. ### Interpretation The data demonstrates that increasing core count improves performance up to a critical threshold (~11 cores), after which further cores provide little benefit. This suggests: - **Parallelization Limits**: The algorithm may not scale efficiently beyond 11 cores due to overhead (e.g., synchronization, memory contention). - **Hardware Constraints**: Diminishing returns could reflect physical or architectural limits in core coordination. - **Optimization Opportunity**: Refactoring the algorithm to better utilize >11 cores might reduce the plateau. The chart underscores the importance of balancing core count with algorithmic efficiency in high-performance computing. </details> c) Shifter.: Figure 20 shows the 16-bit shifter's compute time with respect to core count. A 16-bit shifter has a maximum core usage of 16. The 16-bit shifter's latency decreases as the core count increases from 1-16. The shifter's performance reaches its peak at core count 16. For core counts higher than 16, its stays stable at around 300ms. The maximum speedup yielded by parallel computing is around 10.94x. Fig. 20: Time vs Core count <details> <summary>Image 22 Details</summary>  ### Visual Description ## Bar Chart: Shifter: Time vs Core count ### Overview The chart visualizes the relationship between core count (x-axis) and processing time in milliseconds (y-axis) for a system or application named "Shifter." Bars represent time values for core counts ranging from 1 to 47, with a logarithmic-like decline in time as core count increases, followed by a plateau. ### Components/Axes - **X-axis (Core count)**: Labeled "Core count," with integer values from 1 to 47 in increments of 2 (1, 3, 5, ..., 47). - **Y-axis (Time)**: Labeled "Time (ms)," with values from 0 to 3500 in increments of 500. - **Bars**: Blue vertical bars represent time values for each core count. No legend is present. - **Title**: "Shifter: Time vs Core count" is centered at the top. ### Detailed Analysis - **Core count 1**: Tallest bar at ~3200 ms. - **Core count 3**: Second-tallest bar at ~3200 ms. - **Core count 5**: Sharp drop to ~1200 ms. - **Core counts 7–13**: Gradual decline from ~900 ms (core 7) to ~600 ms (core 13). - **Core counts 15–47**: Time stabilizes between ~300–400 ms, with minor fluctuations (e.g., core 15: ~400 ms, core 17: ~350 ms, core 21: ~380 ms, core 25: ~360 ms, core 31: ~340 ms, core 35: ~320 ms, core 39: ~310 ms, core 41: ~300 ms, core 43: ~300 ms, core 45: ~300 ms, core 47: ~300 ms). ### Key Observations 1. **Initial High Time**: Core counts 1 and 3 exhibit the highest time (~3200 ms), suggesting inefficiency or overhead at low core counts. 2. **Rapid Decline**: Time drops sharply from core count 1–5 (~3200 ms → ~1200 ms), then gradually declines to ~600 ms by core count 13. 3. **Plateau Effect**: Beyond core count 13, time remains relatively flat (~300–400 ms), indicating diminishing returns for additional cores. 4. **Consistency at High Core Counts**: Cores 35–47 show minimal variation (~300–320 ms), suggesting saturation or optimization limits. ### Interpretation - **Scalability Insights**: The sharp decline in time up to core count 13 implies that the workload benefits significantly from parallelization up to this point. Beyond 13 cores, the lack of improvement suggests the application may not be optimized for further parallelization or is constrained by other bottlenecks (e.g., memory, I/O, or sequential dependencies). - **Efficiency at Low Core Counts**: The high time at core counts 1 and 3 highlights potential inefficiencies in single-threaded or lightly parallelized execution, possibly due to overhead from task scheduling or underutilized resources. - **Practical Implications**: For systems using "Shifter," allocating more than 13 cores may not yield proportional performance gains, making core count 13 a potential sweet spot for balancing cost and performance. ### Spatial Grounding - Bars are centered under their respective core count labels on the x-axis. - Y-axis ticks and labels are aligned to the left of the chart. - No legend is present, so color coding is uniform (blue bars). ### Content Details - **Core count 1**: 3200 ms - **Core count 3**: 3200 ms - **Core count 5**: 1200 ms - **Core count 7**: 900 ms - **Core count 9**: 800 ms - **Core count 11**: 700 ms - **Core count 13**: 600 ms - **Core count 15**: 400 ms - **Core count 17**: 350 ms - **Core count 19**: 380 ms - **Core count 21**: 360 ms - **Core count 23**: 350 ms - **Core count 25**: 340 ms - **Core count 27**: 330 ms - **Core count 29**: 320 ms - **Core count 31**: 310 ms - **Core count 33**: 300 ms - **Core count 35**: 300 ms - **Core count 37**: 300 ms - **Core count 39**: 300 ms - **Core count 41**: 300 ms - **Core count 43**: 300 ms - **Core count 45**: 300 ms - **Core count 47**: 300 ms ### Notable Anomalies - **Core count 19**: Slight spike to ~380 ms compared to neighboring cores (~350–360 ms), suggesting a temporary inefficiency or outlier. - **Core count 33**: Drops to ~300 ms, aligning with the plateau trend. This analysis confirms that "Shifter" exhibits optimal performance scaling up to 13 cores, after which additional cores provide negligible time reductions. The data underscores the importance of workload design for parallel processing efficiency. </details> d) Multiplier.: Figure 21 shows the 16-bit multiplier's compute time with respect to core count. A 16-bit multiplier requires 32 cores to enable all parallel computing optimization. From the chart, both unsigned and signed multiplication's latency decrease as the number of cores increases from 1 to 32. The multiplier reached its top speed at around 32 cores. Beyond that, the multiplier's latency stays around 11000-12000ms. Unsigned multiplication has a maximum parallel computing speedup of 8.3x; signed multiplication has a maximum parallel computing speedup of 8.4x. Fig. 21: Time vs Core count <details> <summary>Image 23 Details</summary>  ### Visual Description ## Bar Chart: Multiplier: Time vs Core count ### Overview The chart compares computation time (in milliseconds) for unsigned and signed multiplication operations across varying core counts (1 to 47). Two data series are visualized: orange bars represent unsigned multiplication, while gray bars represent signed multiplication. The y-axis scales logarithmically from 0 to 100,000 ms, with the x-axis showing core counts in odd increments (1, 3, 5, ..., 47). ### Components/Axes - **Title**: "Multiplier: Time vs Core count" - **X-axis**: - Label: "Core count" - Scale: Discrete values from 1 to 47 (odd numbers only) - **Y-axis**: - Label: "Time (ms)" - Scale: 0 to 100,000 ms in 10,000 ms increments - **Legend**: - Position: Bottom center - Entries: - Orange: "Unsigned Multiplication" - Gray: "Signed Multiplication" - **Bars**: - Grouped by core count (each group contains two bars: orange and gray) - Heights correspond to time values ### Detailed Analysis 1. **Core Count 1**: - Unsigned: ~85,000 ms - Signed: ~90,000 ms 2. **Core Count 3**: - Unsigned: ~45,000 ms - Signed: ~47,000 ms 3. **Core Count 5**: - Unsigned: ~32,000 ms - Signed: ~34,000 ms 4. **Core Count 7**: - Unsigned: ~25,000 ms - Signed: ~26,000 ms 5. **Core Count 9**: - Unsigned: ~20,000 ms - Signed: ~21,000 ms 6. **Core Counts 11–47**: - Both series plateau between ~10,000–15,000 ms, with minor fluctuations (e.g., ~12,000 ms at core count 13, ~11,000 ms at core count 25). ### Key Observations - **Steep Initial Decline**: Time drops dramatically from core count 1 (90,000 ms) to core count 5 (32,000 ms), then gradually stabilizes. - **Minimal Difference Between Signed/Unsigned**: Signed operations consistently take ~2–5% longer than unsigned, but the gap narrows as core count increases. - **Plateau Effect**: Beyond core count 9, performance gains diminish, suggesting diminishing returns at higher core utilization. ### Interpretation The data demonstrates that increasing core count significantly reduces computation time for multiplication operations, with the most substantial gains occurring at low core counts (1–5). The near-identical performance of signed and unsigned operations implies that sign handling introduces negligible overhead in this implementation. The plateau at higher core counts suggests potential bottlenecks (e.g., memory bandwidth, instruction scheduling) limiting further optimization. This chart highlights the importance of core parallelism in computational efficiency but also underscores the need for architectural improvements to sustain performance gains at scale. </details> e) Divider.: Figure 22 shows the 16-bit divider's compute time with respect to core count. A 16-bit divider requires 32 cores to achieve the best parallel computing performance. From the chart, divider's latency decreases as the core count increases from 1 to 32. From 32 cores on, the divider's latency stays at around 12000ms. The 16-bit divider has a maximum parallel computing speedup of 8.43x, reached when it can draw on 32 cores. Fig. 22: Time vs Core count <details> <summary>Image 24 Details</summary>  ### Visual Description ## Bar Chart: Divider: Time vs Core count ### Overview The chart visualizes the relationship between core count (x-axis) and processing time in milliseconds (y-axis). It shows a bar graph with 24 vertical blue bars representing time measurements across core counts from 1 to 47. The y-axis scales logarithmically from 0 to 100,000 ms, while the x-axis increments by 2 cores. The title emphasizes a "Divider" relationship between time and core count. ### Components/Axes - **X-axis (Core count)**: Labeled "Core count" with values 1, 3, 5, ..., 47 (odd numbers up to 47). - **Y-axis (Time)**: Labeled "Time (ms)" with logarithmic scale from 0 to 100,000 ms in 10,000 ms increments. - **Legend**: Single blue bar color with no explicit label, implying a single data series. - **Title**: "Divider: Time vs Core count" centered at the top. ### Detailed Analysis - **Core 1**: Tallest bar at ~88,000 ms (highest time). - **Core 3**: ~45,000 ms (50% reduction from Core 1). - **Core 5**: ~32,000 ms (28% reduction from Core 3). - **Core 7**: ~24,000 ms (25% reduction from Core 5). - **Core 9**: ~20,000 ms (20% reduction from Core 7). - **Core 11**: ~18,000 ms (10% reduction from Core 9). - **Cores 13–47**: Bars plateau between ~10,000–12,000 ms, showing minimal variation. ### Key Observations 1. **Steep Initial Decline**: Time drops rapidly from Core 1 to Core 11 (~88,000 ms → ~18,000 ms). 2. **Plateau Effect**: Beyond Core 11, time remains stable (~10,000–12,000 ms) despite doubling core counts. 3. **Diminishing Returns**: Adding cores beyond 11 yields negligible time improvements. 4. **Anomaly**: Core 1’s time (~88,000 ms) is 5.5× higher than Core 3 (~45,000 ms), suggesting non-linear scaling. ### Interpretation The data demonstrates **Amdahl’s Law** in action: parallel processing gains are limited by sequential tasks. The sharp decline up to Core 11 indicates effective parallelization, while the plateau suggests: - **Bottlenecks**: A single-threaded component limiting further optimization. - **Overhead**: Synchronization or communication costs negating benefits of additional cores. - **Hardware Limits**: Physical constraints (e.g., memory bandwidth) capping scalability. The "Divider" title metaphorically represents the threshold (Core 11) where time "divides" into a stable range. This pattern is critical for optimizing parallel workloads, as adding cores beyond 11 offers no practical benefit in this scenario. </details> f) Bitwise operations.: Figure 23 shows 16-bit bitwise operation's compute time with respect to the core count. 16-bit bitwise ops requires 16 cores to have the best parallel computing performance. From the graph, at core count 16 the bitwise operation reached its top speed. At 16 cores and beyond, the latency stays around 50ms. 16-bit bitwise op has a maximum parallel computing speedup of 8.63x. Fig. 23: Time vs Core count <details> <summary>Image 25 Details</summary>  ### Visual Description ## Bar Chart: BitOps: Time vs Core count ### Overview The chart visualizes the relationship between computational core count and processing time (in milliseconds) for a task labeled "BitOps." Bars represent time measurements across core counts from 1 to 47. Time decreases significantly with increasing core count initially, then stabilizes at lower values. ### Components/Axes - **X-axis (Core count)**: Discrete categories labeled 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47. - **Y-axis (Time (ms))**: Linear scale from 0 to 450 ms, with increments of 50 ms. - **Legend**: Positioned at the top, labeled "BitOps" with a blue color matching the bars. ### Detailed Analysis - **Core count 1**: Tallest bar (~400 ms). - **Core count 3**: Second tallest (~380 ms). - **Core count 5**: ~200 ms. - **Core count 7**: ~150 ms. - **Core counts 9–13**: Gradual decline to ~100 ms. - **Core counts 15–47**: Bars stabilize at ~50 ms, with minor fluctuations. ### Key Observations 1. **Inverse relationship**: Time decreases as core count increases, but the rate of improvement slows dramatically after core count 7. 2. **Plateau effect**: From core count 15 onward, time remains nearly constant (~50 ms), suggesting diminishing returns. 3. **Outlier**: Core count 1 has the highest time (~400 ms), indicating single-core inefficiency. ### Interpretation The data demonstrates that parallelizing "BitOps" across multiple cores reduces processing time, but only up to a point. Beyond 15 cores, additional cores provide negligible time savings, likely due to: - **Parallel processing limits**: The task may not scale linearly beyond a certain core count. - **Overhead**: Synchronization or communication costs between cores may offset gains. - **Hardware constraints**: The system might lack resources (e.g., memory bandwidth) to utilize more cores effectively. This pattern highlights the importance of optimizing parallel algorithms and understanding hardware-specific bottlenecks in distributed computing. </details> - g) Conditional Flags.: Figure 24 shows the 16-bit conditional flag unit's compute time with respect to core count. A 16-bit conditional flag unit runs a maximum of 18 threads in parallel. On the chart from core count 15 onward, the latency of the conditional flag unit hovers at around 120-130ms. The maximum parallel computing speedup is 4.7x. Fig. 24: Time vs Core count <details> <summary>Image 26 Details</summary>  ### Visual Description ## Bar Chart: Time vs Core Count ### Overview The chart visualizes the relationship between computational core count and processing time (in milliseconds) under a specific condition. It uses vertical bars to represent time values for core counts ranging from 1 to 47. The y-axis shows time in milliseconds (0–600 ms), while the x-axis lists core counts in increments of 2. ### Components/Axes - **Title**: "Condition: Time vs Core count" (centered at the top). - **X-axis**: - Label: "Core count" (bottom). - Values: 1, 3, 5, ..., 47 (odd numbers from 1 to 47). - **Y-axis**: - Label: "Time (ms)" (left). - Scale: 0–600 ms in increments of 100. - **Bars**: - Color: Blue (no legend present; assumed uniform). - Heights vary inversely with core count (taller bars for lower core counts). ### Detailed Analysis - **Core Count 1**: Tallest bar (~520 ms). - **Core Count 3**: Second tallest (~470 ms). - **Core Count 5**: ~270 ms. - **Core Counts 7–13**: Gradual decline (~180–210 ms). - **Core Counts 15–47**: Plateau (~100–150 ms), with minor fluctuations (e.g., ~120 ms at 21, ~140 ms at 25, ~110 ms at 33, ~105 ms at 47). ### Key Observations 1. **Inverse Relationship**: Time decreases as core count increases, but the rate of improvement diminishes after ~13 cores. 2. **Diminishing Returns**: The steepest time reduction occurs between 1–13 cores; beyond this, gains are marginal. 3. **Plateau Effect**: Core counts ≥15 show minimal time variation (~100–150 ms), suggesting saturation or parallelization limits. ### Interpretation The data suggests that increasing core count improves performance up to ~13 cores, after which additional cores yield negligible time savings. This could indicate: - **Parallelization Limits**: The workload may not scale efficiently beyond 13 cores. - **Overhead Saturation**: System-level overhead (e.g., inter-core communication) becomes dominant. - **Hardware Constraints**: The test environment might cap effective core utilization. The absence of a legend implies uniform data representation, but the lack of error bars or confidence intervals limits statistical certainty. The plateau at higher core counts warrants further investigation into parallelization efficiency or hardware bottlenecks. </details> ## C. Vulnerability There are two source of vulnerability associated with the current CryptoEmu implementation: ( i ) the unencrypted HE instruction memory; and ( ii ) the branch resolution process. Because HE instruction memory is in cleartext, the cloud knows exactly what assembly code is being executed. Assumption 2 assumes that the cloud is honest, so cloud visible instructions to the cloud do not pose a security issue. However, it is possible that the cloud's execution pipeline is compromised by attackers. If an attacker obtains control over the instruction set emulator, or performs a side-channel attack, user data can be breached. If Assumption 2 is lifted, then the unencrypted HE instruction memory becomes a security loophole.Note that, we still assume the cloud will not start a denial of service attack on user. For example, if user send an encrypted number such as age, credit score or salaries, the cloud can also use binary search to actively query the value of an encrypted data using conditional unit implemented in CryptoEmu, and eventually find out the cleartext. User can counter the attack by sending HE instructions with anti-disassembly techniques, making it difficult for side-channel attack. However, this approach does not eliminate an active attack from cloud. The cloud is able to actively find encrypted data's value because the cloud can abuse the branch resolution process. The problem can be solved by having the user assume control over the branch resolution process [15]. The user can ask for encrypted data from cloud, decrypt and process the data, send data back to cloud and inform the cloud which is the next instruction to fetch. With some extra overhead in data transmission, the user can make branch resolution unknown to the cloud and has full control over branch resolution. ## D. Comparison against the state of the art HELib [4] is one of the most widely adopted FHE software libraries. HELib implements the Brakerski-Gentry-Vaikuntanathan (BGV) scheme and supports basic homomorphic operations [21]. HELib has native support for binary negation, addition/subtraction, multiplication, binary condition, shift immediate, bitwise operation and binary comparison. CryptoEmu supports all these operation and a few more: left shift/right shift with encrypted amount, unsigned binary division, and NZCV condition flag computation. This section compares the performance of the operations supported by both HELib and CryptoEmu. TABLE XXIV: HELib vs CryptoEmu | Operation | HELib | CryptoEmu (single core) | CryptoEmu (multi-core) | Speedup | |---------------------------|------------|---------------------------|--------------------------|-----------| | Addition | 10484.1ms | 4400.67ms | 566.149ms | 18.518x | | Subtraction | 10962.2ms | 5088.57ms | 599.396ms | 18.289x | | Multiplication (unsigned) | 69988.9ms | 86389.8ms | 10396.1ms | 6.732x | | Multiplication (signed) | 81707.2ms | 92408.4ms | 10985.4ms | 7.438x | | LLS (immediate) | 0.534724ms | 0.0040335ms | 0.0040335ms | 132.571x | | Bitwise XOR | 1.52444ms | 416.013 ms | 47.1986ms | -30.9613x | | Bitwise OR | 771.12ms | 416.146 ms | 47.6171ms | 16.194x | | Bitwise AND | 756.641ms | 411.014ms | 47.6001ms | 15.90x | | Bitwise NOT | 1.8975ms | 0.012508 ms | 0.012508 ms | 151.703x | | Comparison | 4706.07ms | 519.757ms | 110.416ms | 42.62x | As reported in Table XXIV, for addition and subtraction, CryptoEmu's single core performance is about two times faster than HELib's. With sufficient cores, CryptoEmu yields maximum 18x speed up compare to HELib. For both signed and unsigned multiplication, CryptoEmu in single core mode is slightly slower than HELib. CryptoEmu yields a maximum 7x speed up in multiple core mode compare to HELib. HELib supports logic left shift (LLS) with immediate. This operation is not computationally intensive compared to addition/subtraction. LLS with immediate is not implemented without parallel computing optimizations on CryptoEmu, and therefore single core latency is the same as multi-core latency. Because of the excellent support provided by TFHE library, LLS with immediate on CryptoEmu is about 132x faster than on HELib. For bitwise operation, HELib's bitwise XOR is in fact 31x faster than CryptoEmu. This is expected because the implementation for HELib's bitwise XOR is not computationally expensive. For bitwise OR and bitwise AND, CryptoEmu's single core speed is faster than HELib's. When maximum cores are enabled, CryptoEmu yields 16x speed up on bitwise OR and bitwise AND compared to HELib. Bitwise NOT is not a computationally expensive operation on both CryptoEmu and HELib. Because bitwise NOT is implemented without parallel computing techniques, single core and multi-core performance are the same on CryptoEmu. By comparison, CryptoEmu is 151x faster than HELib on bitwise NOT operation. For comparison/conditional operations, we benchmarked HELib's CompareTwo() function and CryptoEmu's conditional unit. HELib's compare routine compares two encrypted values and returns the greater/lesser number and comparison result. Our CryptoEmu compares two encrypted data and returns N, Z, C, and V flags. Because the Z-flag computation is on conditional unit's critical path, it is justified to compare latencies of two functionally equivalent operations that are on both unit's critical paths. CryptoEmu's comparison is much faster than HELib's in single core mode. When multiple cores are enabled, CryptoEmu yields maximum speedup of 42x. ## VIII. CONCLUSION AND FUTURE WORK CryptoEmu successfully supports multiple homomorphic instructions on a multi-core host. With function units built upon the TFHE bootstrapped gate library, CryptoEmu is reconfigurable and reusable for general purpose computing. Through parallel computing algorithms that significantly reduces time complexity, CryptoEmu has a scalable implementation and achieves parallel computing speedup from 4.7x to 10.94x on functional units. Compare to HELib, CryptoEmu has maximum 18x speedup on addition/subtraction, 7x speedup on multiplication, 16x speed up on bitwise AND/OR, 42x speedup on comparison, 130x speedup on left shift with immediate, and 151x speedup on bitwise NOT. Scalability of CryptoEmu can be further improved. The current design only supports single instruction set emulator process that runs on multiple cores. Therefore maximum core count is bounded by number of cores on one CPU. With more cores available, CryptoEmu can draw on more parallelism through pipelining, multiple instruction issue and dynamic instruction scheduling. Another aspect that could provide further speed improvements is the use of AVX instructions. ## REFERENCES - [1] J. Clement, 'Cyber crime: number of breaches and records exposed 2005-2020.' https://www.statista.com/statistics/273550, 2020. Accessed on 2020Dec-01. - [2] I. Chillotti, N. Gama, M. Georgieva, and M. Izabach` ene, 'TFHE: Fast fully homomorphic encryption library,' August 2016, Accessed on 2020-Dec-01. https://tfhe.github.io/tfhe. - [3] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachene, 'Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds,' in international conference on the theory and application of cryptology and information security , pp. 3-33, Springer, 2016. - [4] S. Halevi and V. Shoup, 'An implementation of homomorphic encryption,' 2013, Accessed on 2020-Dec-17. https://github.com/shaih/HElib. - [5] A. Acar, H. Aksu, A. S. Uluagac, and M. Conti, 'A survey on homomorphic encryption schemes: Theory and implementation,' ACM Computing Surveys (CSUR) , vol. 51, no. 4, pp. 1-35, 2018. - [6] C. Gentry, 'Fully homomorphic encryption using ideal lattices,' in Proceedings of the forty-first annual ACM symposium on Theory of computing , pp. 169-178, 2009. - [7] I. Chillotti, N. Gama, M. Georgieva, and M. Izabach` ene, 'Tfhe: fast fully homomorphic encryption over the torus,' Journal of Cryptology , vol. 33, no. 1, pp. 34-91, 2020. - [8] L. Ducas and D. Micciancio, 'Fhew: bootstrapping homomorphic encryption in less than a second,' in Annual International Conference on the Theory and Applications of Cryptographic Techniques , pp. 617-640, Springer, 2015. - [9] I. Chillotti, N. Gama, M. Georgieva, and M. Izabach` ene, 'Faster packed homomorphic operations and efficient circuit bootstrapping for tfhe,' in International Conference on the Theory and Application of Cryptology and Information Security , pp. 377-408, Springer, 2017. - [10] S. Halevi and V. Shoup, 'Design and implementation of a homomorphic-encryption library,' IBM Research (Manuscript) , vol. 6, pp. 12-15, 2013. - [11] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, '(leveled) fully homomorphic encryption without bootstrapping,' ACM Transactions on Computation Theory (TOCT) , vol. 6, no. 3, pp. 1-36, 2014. - [12] O. Mazonka, N. G. Tsoutsos, and M. Maniatakos, 'Cryptoleq: A heterogeneous abstract machine for encrypted and unencrypted computation,' IEEE Transactions on Information Forensics and Security , vol. 11, no. 9, pp. 2123-2138, 2016. - [13] P. Paillier, 'Public-key cryptosystems based on composite degree residuosity classes,' in International conference on the theory and applications of cryptographic techniques , pp. 223-238, Springer, 1999. - [14] N. G. Tsoutsos and M. Maniatakos, 'Heroic: homomorphically encrypted one instruction computer,' in 2014 Design, Automation & Test in Europe Conference & Exhibition (DATE) , pp. 1-6, IEEE, 2014. - [15] F. Irena, D. Murphy, and S. Parameswaran, 'Cryptoblaze: A partially homomorphic processor with multiple instructions and non-deterministic encryption support,' in 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC) , pp. 702-708, IEEE, 2018. - [16] OpenMP, 'Specification Standard 5.1.' Available online at http://openmp.org/wp/, 2020. - [17] K. Vitoroulis, 'Parallel prefix adders,' Concordia university , 2006. - [18] A. D. Booth, 'A signed binary multiplication technique,' The Quarterly Journal of Mechanics and Applied Mathematics , vol. 4, no. 2, pp. 236-240, 1951. - [19] C. Terman, '6.004 computation structures.' MIT OpenCourseWare, https://ocw.mit.edu, Spring 2017. - [20] geeksforgeeks.org, 'Non-restoring division for unsigned integer.' https://www.geeksforgeeks.org/non-restoring-division-unsigned-integer, 2018, Accessed on 2020-Dec-09. - [21] S. Halevi and V. Shoup, 'Algorithms in helib,' in Annual Cryptology Conference , pp. 554-571, Springer, 2014. <details> <summary>Image 27 Details</summary>  ### Visual Description ## Portrait Image: Unlabeled Individual ### Overview The image is a black-and-white portrait of an individual with no visible textual, numerical, or graphical data elements. The subject is centered against a plain, neutral background. No charts, diagrams, tables, or embedded text are present. ### Components/Axes - **No axes, legends, or labeled components** are visible. - **No textual annotations** (e.g., names, dates, measurements) are discernible. - **No data series, categories, or sub-categories** are present. ### Detailed Analysis - **Clothing**: The individual wears a collared shirt under a dark sweater. No logos, text, or patterns are visible on the attire. - **Background**: Uniformly plain with no distinguishing features. - **Lighting/Contrast**: High contrast between the subject and background, but no gradients or color variations to analyze. ### Key Observations - No numerical values, trends, or distributions can be extracted. - No relationships between components (e.g., flow, causality) are depicted. - No outliers, anomalies, or patterns are identifiable. ### Interpretation This image contains no factual or data-driven content. It appears to be a standard portrait photograph, likely intended for identification or professional use. The absence of textual or graphical elements suggests it is not designed to convey analytical or technical information. **Note**: If this image is part of a larger dataset or context (e.g., a document page), additional metadata or surrounding text may be required for full analysis. </details> <details> <summary>Image 28 Details</summary>  ### Visual Description ## Photograph: Portrait of a Man ### Overview The image is a black-and-white portrait of a middle-aged man with short, dark hair. He is wearing a collared, button-up shirt and is positioned centrally against a neutral, nondescript background. No textual elements, charts, diagrams, or data visualizations are present. ### Components/Axes No axes, labels, legends, or numerical data are visible in the image. ### Detailed Analysis - **Subject**: The man’s face is the focal point, with a neutral expression. - **Clothing**: A light-colored collared shirt with visible buttons and a slight crease at the collar. - **Background**: A plain, dark-toned wall with no discernible features or text. - **Lighting**: Even illumination with no shadows or highlights suggesting depth. ### Key Observations - No textual or graphical elements are present. - The image focuses solely on the subject’s upper body and face. ### Interpretation This image appears to be a standard portrait with no embedded data, annotations, or contextual clues beyond the subject’s appearance. It lacks any technical or analytical components that would require extraction of labels, trends, or relationships. The absence of textual information suggests the image is intended for identification or illustrative purposes rather than data representation. </details> Xiaoyang Gong is a graduate student in the Department of Electrical and Computer Engineering at the University of WisconsinMadison. Xiaoyang received his MS in Electrical Engineering in 2020 and BS in Computer Engineering in 2019 from the University of Wisconsin-Madison. He worked as an intern at Arm Ltd.'s CPU team in 2019. His interests are in computer architecture and processor design. Dan Negrut is a Mead Witter Foundation Professor in the Department of Mechanical Engineering at the University of WisconsinMadison. He has courtesy appointments in the Department of Computer Sciences and the Department of Electrical and Computer Engineering. Dan received his Ph.D. in Mechanical Engineering in 1998 from the University of Iowa under the supervision of Professor Edward J. Haug. He spent six years working for Mechanical Dynamics, Inc., a software company in Ann Arbor, Michigan. In 2004 he served as an Adjunct Assistant Professor in the Department of Mathematics at the University of Michigan, Ann Arbor. He spent 2005 as a Visiting Scientist at Argonne National Laboratory in the Mathematics and Computer Science Division. He joined University of Wisconsin-Madison in 2005. His interests are in Computational Science and he leads the Simulation-Based Engineering Lab. The lab's projects focus on high performance computing, computational dynamics, artificial intelligence, terramechanics, autonomous vehicles, robotics, and fluid-solid interaction problems. Dan received the National Science Foundation Career Award in 2009. Since 2010 he is an NVIDIA CUDA Fellow.