PaperlayerView exact revision on arXiv

Source-linked AI summary

HULK: An Efficient Algorithm for Enabling Fast Bulk Bitwise Operations on Homomorphically Encrypted Data

Mayank Kabra, Phillip Widdowson, Harshita Gupta, Rakesh Nadig, Nisa Bostancı, Eirini Tzermpou, Rakesh Kumar, Spiros Galanopoulos, Ataberk Olgun, Abdullah Giray Yağlıkçı, Mohammad Sadrosadati, Onur Mutlu

arXiv:2610.18391v1cs.CRcs.ARcs.DC

TL;DR

Existing HE approaches implement bulk bitwise operations with costly multiplications or lookup tables, despite the importance of protecting sensitive cloud data. HULK computes encrypted operand Hamming weights with slot-wise homomorphic additions and uses indicator evaluation to decode Boolean results. Across 13 end-to-end applications in healthcare, graph, and database analytics, HULK improves performance by up to 7.26× on the CPU and 6.65× on the GPU over the state-of-the-art arithmetic approach.

  • Problem

    Existing HE approaches implement bulk bitwise operations with costly multiplications or lookup tables, despite the importance of protecting sensitive cloud data.

    Source: §1 · pp. 1–2

  • Method

    HULK computes encrypted operand Hamming weights with slot-wise homomorphic additions and uses indicator evaluation to decode Boolean results.

    Source: §1 · p. 2, §6.2.2 · p. 7, §12 · p. 17

  • Results

    Across 13 end-to-end applications in healthcare, graph, and database analytics, HULK improves performance by up to 7.26× on the CPU and 6.65× on the GPU over the state-of-the-art arithmetic approach.

    Source: §12 · p. 17

  • Takeaways & Limitations

    HULK’s addition-dominant construction provides performance gains over the arithmetic approach across the evaluated application domains.

    Source: §1 · p. 2, §12 · p. 17

    The Fermat indicator requires p=65537 and thus K<65537; wider reductions require digit-wise Fermat tests, which are slower than HMul-based evaluation.

    Source: §8.3 · p. 13

Abstract

from arXiv · show

A wide range of important cloud applications, e.g., database analytics, graph analytics, and genome analysis, spend a considerable amount of time performing bulk bitwise operations (e.g., AND, OR, XOR). These applications often operate on highly sensitive data, making data privacy a critical concern. Homomorphic encryption (HE) enables secure computation on encrypted data without requiring decryption, ensuring privacy in untrusted and shared environments. We analyze 13 end-to-end applications across three domains (healthcare, graph, and database analytics) and observe that bulk bitwise operations take 62-100% of the execution time of the healthcare and graph workloads. The key problem is that existing HE approaches perform them with high-latency homomorphic operations (e.g., multiplication or lookup tables) and significantly increase the data size. Our goal is to enable fast bulk bitwise operations on homomorphically encrypted data by designing an efficient HE algorithm that reduces the use of these costly operations. To this end, we propose HULK, which performs two key steps: (1) it constructs bulk bitwise operations using low-cost homomorphic additions, which compute the Hamming weight of the encrypted operand bits in every slot of a packed ciphertext without any homomorphic multiplication, and (2) it decodes the result of an AND, OR, or XOR from the Hamming weight with a single indicator polynomial, keeping the result in the standard encoding. Across 13 end-to-end applications in healthcare, graph, and database analytics, HULK improves performance over the arithmetic approach used by prior works by up to 7.26x (CPU) and 6.65x (GPU), and on average by 2.32x/1.78x/1.45x (CPU) and 2.08x/1.70x/1.51x (GPU) for healthcare/graph/database analytics. When we increase the reduction depth in a representative application, HULK's speedup grows to 10.10x over the state-of-the-art GPU baseline.

1. Introduction

The introduction identifies bulk bitwise operations as a major cost in homomorphically encrypted workloads and proposes HULK to replace costly operations with additions and indicator-based decoding. It reports performance gains across 13 end-to-end applications.

Key Problem

  • Healthcare and graph workloads spend 62.0–100% of execution time on bulk bitwise operations, which existing HE approaches implement using costly multiplication or lookup-table evaluation.The introduction illustrates the workload with genome screening, where the arithmetic approach spends 991 HMuls for one evaluation.Source: §1 · pp. 1–2
  • Prior HE bitwise implementations rely on high-latency multiplications or lookup tables, while homomorphic addition is orders of magnitude cheaper.The introduction states that multiplication and lookup-table operations are 10^4–10^5× slower than unencrypted CPU execution.Source: §1 · p. 2

Key Insight

  • HULK exploits that sequential AND, OR, and XOR reductions are symmetric Boolean functions whose outputs depend on Hamming weight rather than bit arrangement.For AND, summing the bits reaches the input count only when every bit is 1.Source: §1 · p. 2

Key Mechanisms

  • HULK adds encrypted operand bits slot-wise to compute their Hamming weight without multiplication, then decodes AND, OR, or XOR using one indicator polynomial.The decoded result returns to the standard arithmetic encoding, supporting applications that mix bitwise and arithmetic operations.Source: §1 · p. 2

Key Results

  • Across 13 applications, HULK beats the arithmetic approach by up to 7.26× (CPU) and 6.65× (GPU), averaging 2.32×/1.78×/1.45× (CPU) and 2.08×/1.70×/1.51× (GPU) across healthcare/graph/database analytics.The reported averages correspond to healthcare, graph, and database analytics, respectively.Source: §1 · p. 2

2. Background

The background introduces homomorphic encryption and contrasts Boolean and arithmetic schemes. It explains how each represents data and supports bulk bitwise operations, including their main computational trade-offs.

2.1. Homomorphic Encryption

  • Homomorphic encryption enables computation on encrypted data without decryption; Boolean schemes such as TFHE and arithmetic schemes such as B/FV and CKKS support different operation types.B/FV supports exact integer arithmetic, while CKKS supports approximate floating-point arithmetic.Source: §2.1 · p. 2, §2.1.2 · p. 3

2.1.1. Boolean Approach (TFHE).

  • TFHE evaluates Boolean gates through lookup tables during bootstrapping, but its bit-by-bit ciphertext representation creates memory and computation overhead.Each bit requires a separate ciphertext and gate evaluation.Source: §2.1.1 · p. 3, §2.2 · p. 3

2.1.2. Arithmetic Approach (B/FV and CKKS).

  • B/FV and CKKS support packed SIMD slots, where homomorphic additions and multiplications act slot-wise; multiplication adds noise and may require relinearization.The schemes use RNS decomposition to represent large ciphertext moduli as smaller limbs.Source: §2.1.2 · p. 3
  • Arithmetic HE evaluates nonlinear functions as polynomials, and Paterson–Stockmeyer reduces the ciphertext multiplications needed for polynomial evaluation.It rewrites the polynomial in blocks using baby-step and giant-step powers.Source: §2.1.2 · p. 3

2.2. Bulk Bitwise Operations using HE

  • Boolean HE supports arbitrary-depth bitwise computation with LUT gates but lacks packing; arithmetic HE packs bits but uses multiplications to compose logic.The two approaches therefore trade gate-level flexibility against packed processing and multiplication costs.Source: §2.2 · p. 3
  • The arithmetic approach packs bits into slots and expresses AND, XOR, and OR with arithmetic formulas, but a K-input reduction still costs K−1 homomorphic multiplications.Packed ciphertexts provide SIMD parallelism because one homomorphic operation acts on all N slots.Source: §2.2 · p. 3

3. Key Related Works

The related-work section surveys HE-based bulk bitwise constructions across graph, healthcare, and database analytics. It describes how representative applications compose encrypted comparisons or matches using gates, multiplication trees, or lookup tables.

Encrypted Graph Analytics

  • Graph workloads include PSI and private nearest-neighbor search, where encrypted membership or bucket matches are commonly computed with HMul product trees.Bit-sliced PSI tests membership bit by bit, while nearest-neighbor bucket matches use wide ANDs over XNOR bits.Source: §3 · p. 4

Encrypted Healthcare Analytics

  • Healthcare applications include genome matching, variant lookup, and GWAS; prior constructions evaluate equality or threshold conditions over encrypted bits with HMul trees or lookup tables.The surveyed approaches include arithmetic HE, Boolean HE gates, and memory-efficient data packing.Source: §3 · p. 4

Encrypted Database Analytics

  • Encrypted database queries compose homomorphic comparison predicates with HMul-based AND/OR or TFHE gates, while top-k ranking uses threshold reductions over comparison bits.The section identifies filter-and-aggregate analytics and top-k queries as representative workloads.Source: §3 · p. 4

4. The Baseline FHE Scheme

The section compares Boolean and arithmetic HE approaches, then evaluates alternatives to packed B/FV. The product tree of packed arithmetic B/FV is the fastest existing approach for bulk bitwise operations.

4.2. Comparison with Other Approaches

  • The packed arithmetic B/FV product tree is 1.7–6,270× faster than four other approach families and is selected as the baseline.The comparison measures latency per record for one bulk AND-K.Source: §4 · p. 4, Table 1 · p. 5, §4.2 · p. 5

4.1. Analysis of Existing FHE Schemes Executing HE-based Bulk Bitwise Operations

  • At K=8, TFHE uses 2.5MB at PF=1 and 81.4GB at PF=32768, while packed B/FV uses at most 192MB in total.Packing more bits into B/FV lowers memory per bit; only at small packing factors does Boolean HE have significantly lower post-encryption memory.Source: §4.1 · p. 4, Figure 1 · p. 4
  • For HomAND, B/FV packing reduces latency by up to 405× at PF=32768, while Boolean HE is faster only at small packing factors.Across circuit depths, the Boolean approach averages a 77× latency reduction over arithmetic HE for AND at small packing factors; packing favors arithmetic HE for bulk operations over many bits.Source: §4.1 · p. 5, Figure 2 · p. 5

4.2. Comparison with Other Approaches

  • Batched Boolean schemes remain 2,529–6,270× slower per record than the product tree for K=2–128 because packing does not reduce per-gate latency.Each gate extracts operand bits into individual LWE ciphertexts and performs a bootstrapping-class operation.Source: §4.2 · p. 5, Table 1 · p. 5
  • Discrete CKKS evaluates AND-16 2.8× slower than arithmetic B/FV (3,877 ms vs. 1,388 ms) and is 1.7–3.8× slower per record than the product tree for K=2–128.Cleanup polynomials add two multiplications and two levels per gate; at depth 7, the required log2 Q=960 exceeds the 881-bit bound for 128-bit security at N=32768, forcing N=65536.Source: §4.2 · p. 5, Table 1 · p. 5
  • Scheme switching pays at least one bootstrapped gate per AND and does not provide a stronger baseline for bulk bitwise operations.It converts operands to LWE ciphertexts and evaluates a lookup table for every gate; Engorgio already outperforms it on relational predicates.Source: §4.2 · p. 5
  • Multi-input PBS is 1,496–4,002× slower per record than the product tree for K=8–64 because it cannot exploit SIMD packing and may require large parameter sets or PBS trees.For AND-64 with at most 5 bits per PBS, it requires 17 PBSs per record.Source: §4.2 · p. 5, Table 1 · p. 5

5. Motivation and Our Goal

Bulk bitwise operations account for a large share of healthcare and graph workload runtime, while database-query shares vary. The section motivates reducing costly homomorphic multiplications in these operations.

5. Motivation and Our Goal

  • Bulk bitwise operations take 97.6–100% of runtime for k-mer matching, variant lookup, and PSI, 87.3% for GWAS, and 62.0% for ANN search.The section attributes this share to arithmetic evaluation of wide AND, OR, and threshold reductions with costly homomorphic multiplications.Source: §5 · p. 6
  • In TPC queries, online filter generation takes 84.3–98.1% of runtime for Q6, Q12, and Q19, while bulk-bitwise shares range from 1.3% for Q6 to 56.5% for TPC-DS Q43.The bulk-bitwise share varies with how many predicates a query composes.Source: §5 · p. 6
  • TPC-H Q3's top-10 selection uses a threshold reduction over 73 bits, taking 51.3% of the arithmetic approach's execution time.The 73 bits comprise 63 encrypted revenue-comparison bits and 10 copies of a bit indicating whether an order fails the query filter.Source: §5 · p. 6

6. HULK: An Algorithm for Fast Homomorphic Bulk Bitwise Operations

HULK encodes bitvectors so each row occupies a ciphertext slot, then uses additions to compute operand Hamming weights and decodes Boolean results from those sums. It offers client-side and server-side decoding, with the latter retaining encrypted results for downstream computation.

6.1.1. Sum, then Indicator.

  • For a symmetric Boolean function, the result depends only on the Hamming weight S; HULK computes S with additions and decodes AND, OR, or XOR from it.The server evaluates one indicator per reduction; when revealing S is acceptable, the client can instead read the result from a fixed bit position.Source: §6 · p. 6, §6.1.1 · p. 7

6.1. Encoding

  • HULK stores each bitvector with row i in slot i, so one ciphertext holds N rows of one bitvector and K bitvectors occupy K ciphertexts.The slot-wise encoding lets one homomorphic addition operate across all N slots.Source: §6 · p. 6, §6.1 · p. 7

6.1.1. Sum, then Indicator.

  • For a K-input reduction, HULK replaces K−1 arithmetic multiplications with K−1 homomorphic additions and one indicator; an addition is ∼300× faster than a multiplication on the CPU system.For K=8, server-side decoding uses 3 multiplications rather than 7 in the arithmetic product tree.Source: §6.1.1 · p. 7, §6.2.2 · p. 8

6.2.1. Client-Side Decoding.

  • Client-side decoding decrypts S and reads AND, OR, or XOR from its bits, while a plaintext shift β places each result at a fixed bit position.This mode reveals S to the decryptor.Source: §6.2.1 · p. 7, Table 2 · p. 8

6.2.2. Server-Side Decoding.

  • When S must remain hidden or encrypted for downstream operations, server-side decoding evaluates an indicator polynomial that maps its possible values to the Boolean result.The polynomial interpolates the target indicator over D={0,…,K}.Source: §6.2.2 · p. 7
  • For AND and OR with K≥128, HULK uses a Fermat indicator when the application fits p=65537; none of the evaluated end-to-end applications meets those conditions.The Fermat indicator is 1.9× faster at K=256; otherwise HULK uses the Lagrange indicator.Source: §6.2.2 · p. 8

6.3. Cost Model

HULK’s cost depends chiefly on reduction size: additions form the Hamming weight, and indicator evaluation determines multiplicative depth and ciphertext modulus. Its decoding preserves B/FV security, with client-side decoding revealing more information than server-side decoding.

6.3 Cost Model

  • An AND-K, OR-K, or XOR-K reduction reserves ⌈log2 K⌉+1 bits per slot, while indicator degree K determines multiplicative depth and helps fix the ciphertext modulus and limb count.Paterson–Stockmeyer evaluation reduces indicator multiplication count; the cost model identifies K as the governing parameter.Source: §6.3 · p. 8

6.3.1. Client-Side Cost.

  • HULK adds no client homomorphic operations relative to standard B/FV; client-side decoding is plaintext work, while server-side decoding returns a 0/1 mask.The client’s cost equals that of the arithmetic baseline.Source: §6.3.1 · p. 8

6.4.1. Security Guarantees.

  • HULK inherits B/FV’s IND-CPA security under RLWE, but client-side decoding reveals each slot’s Hamming weight S whereas server-side decoding reveals only the Boolean result.The evaluated configurations use N=2^15 and a largest modulus of 741 bits, within the stated 128-bit security bound of 881 bits.Source: §6.4.1 · p. 8

6.4.2. Correctness Guarantees.

  • Correctness requires both the structural decoding conditions and B/FV noise below ∆/2 for exact decryption.The stated server-side condition uses an indicator polynomial that equals the target Boolean indicator for every S in D={0,…,K}.Source: §6.4.2 · p. 8

6.4.3. Noise Budget Analysis.

  • Summing K fresh ciphertexts increases noise by at most K·Bfresh without consuming a level; server-side indicator evaluation is HULK’s multiplicative-noise source.Its noise grows with multiplicative depth, and the authors validate selected parameters empirically for every workload.Source: §6.4.3 · p. 9
  • Downstream multiplication of a 0/1 mask by values and summation across blocks adds one level and log2(#blocks) bits in both approaches.The reported downstream cost is identical for HULK and the arithmetic approach.Source: §6.4.3 · p. 9

7. Methodology

The evaluation measures homomorphic-evaluation latency for HULK and comparison systems on real CPU and GPU platforms. It uses Microsoft SEAL for arithmetic approaches and HULK, HEonGPU for GPU HULK, and TFHE-rs for the Boolean approach.

7.1. Real System Evaluation Methodology

  • The CPU implementation uses Microsoft SEAL for HULK and prior arithmetic approaches, while GPU HULK uses HEonGPU and the Boolean approach uses TFHE-rs v1.7.0.The TFHE-rs bootstrapping used is reported as about 1.8× faster than OpenFHE’s.Source: §7.1 · p. 9
  • CPU experiments run on an AMD EPYC 7742; GPU experiments run on an NVIDIA A100 GPU-80 GB, and both systems use PCIe 4.0 NVMe SSDs.Table 3 is identified as the real-system configuration table.Source: §7.1 · p. 9, Table 3 · p. 9
  • End-to-end latency measurements include homomorphic evaluation only, excluding encoding, encryption, and decryption.The evaluation uses an AMD EPYC 7742 CPU and an NVIDIA A100 GPU with 80 GB.Source: §7.1 · p. 9

CPU: AMD EPYC 7742

The workloads cover healthcare, graph, and database analytics, with encrypted inputs processed end-to-end under B/FV. The comparison uses workload-specific minimum limb counts and validates outputs against a plaintext oracle.

7.2. Workloads

  • The evaluation includes 13 end-to-end applications across healthcare, graph, and database analytics, with encrypted inputs and encrypted application results.The workload set includes four genomic workloads, two graph workloads, and database filter-and-aggregate and ranking queries.Source: §7.2 · p. 9
  • Healthcare reductions include exact and fuzzy k-mer matching, variant lookup, and GWAS; graph workloads include PSI and approximate-nearest-neighbor search.The described query structures include AND, OR, and threshold reductions.Source: §7.2 · pp. 9–10
  • Database workloads evaluate TPC-H and TPC-DS filter-and-aggregate queries plus TPC-H Q3 top-10 ranking, with Q3 date predicates omitted because they exceed the depth budget without bootstrapping.The queries use comparison polynomials, compose predicates with AND reductions, then weight and aggregate masks.Source: §7.2 · p. 10
  • The arithmetic baseline follows prior application implementations, using product trees for AND/OR and equality and counting trees for thresholds.Baseline circuits and HULK share encoding, filters, aggregation, parameters, limb search, and measurement protocol, so bulk-bitwise composition differs.Source: §7.2 · pp. 10–11
  • All applications use server-side decoding and B/FV with N=32768; each approach uses its minimum limb count that decrypts correctly against a plaintext oracle.The server keeps results encrypted until the final answer; PSI additionally reduces its result to encrypted cardinality.Source: §7.2 · p. 11
  • HULK reduces HMul count in 12 of 13 applications and matches the baseline in TPC-H Q6; it needs one extra limb in four applications and the same limb count in nine.The one-extra-limb cases are exact and fuzzy k-mer matching, GWAS, and PSI.Source: Table 4 · p. 10, §7.2 · p. 11

8. Evaluation

The evaluation measures single reductions, 13 end-to-end applications, and PSI scalability as reduction depth increases. HULK’s advantage is strongest for wider reductions, while data movement becomes a cost as depth grows.

8.1. Effect of Different Reduction Depth

  • 2002.2×: HULK’s CPU speedup over the arithmetic approach for a single AND-tree reaches this value at K=1024 with client-side decoding and no indicator.The microbenchmark isolates one AND reduction; its speedups are not end-to-end results.Source: §8.1 · p. 11, Figure 5 · p. 11, §8.2 · p. 11

8.2. Evaluation of End-to-End Applications

  • HULK improves all 13 applications by up to 7.26× (CPU) and 6.65× (GPU), averaging 2.32×/1.78×/1.45× (CPU) and 2.08×/1.70×/1.51× (GPU) across healthcare/graph/database analytics.The comparison covers total execution time and breaks down filter generation, bulk bitwise operations, aggregation, and other operations.Source: §8.2 · p. 12, Figure 6 · p. 12

8.3. Case Study: Scalability Analysis

  • 2.31–10.10×: HULK’s GPU speedup over the arithmetic approach rises as PSI reduction depth K increases from 16 to 2048.HULK’s HMul count grows 74× versus 128× for the arithmetic approach, and its HMul advantage grows from 1.9× to 3.2×.Source: §8.3 · p. 13, Figure 7 · p. 13, Table 5 · p. 13
  • As K grows from 16 to 2048, bulk bitwise operations rise from 25% to 43% of HULK’s total runtime, with SSD-to-compute data movement the dominant cost.For K ≥128, the study uses a Fermat indicator with p=65537; wider reductions require slower digit-wise Fermat tests.Source: §8.3 · p. 13

9. Optimizing HULK for Specific Applications

HULK’s application-specific optimizations target addition-only workloads and database predicates: lane packing reduces ciphertext and addition counts, while encrypted bitmap indices remove online comparisons for precomputable predicates. Both optimizations have scope and storage trade-offs.

9.1. Memory-Efficient Data Packing

  • Packing divides each slot into W-bit lanes that independently accumulate operand bits and their Hamming weights, allowing one ciphertext to hold L bitvectors instead of one.A reduction of fan-in K needs W=⌈log2 K⌉+1 bits per lane; the plaintext modulus must satisfy p ≥2LW, and lane shifts require sufficient noise margin.Source: §9.1 · pp. 13–14
  • Packing is restricted to client-side decoding; server-side indicator evaluation would require 2LW interpolation points.Lane assignment at encryption fixes the supported fan-in, while assignment at query time keeps the database fan-in-agnostic but increases noise.Source: §9.1 · pp. 13–14

9.1.1. Evaluation of Memory-Efficient Data Packing.

  • 58.9–227.0×: Memory-efficient packing improves CPU performance over the arithmetic approach across four microbenchmarks, with speedup decreasing as K increases.Packing uses 23×, 15×, 8×, and 3× fewer ciphertexts for the four kernels; gains equal the lane count, which shrinks with log2 K.Source: §9.1.1 · p. 14, Figure 8 · p. 14

9.2. Encrypted Bitmap Indices for Databases

  • Bitmap indices precompute eligible predicates as encrypted bitvectors, reducing a query to bitmap composition and aggregation; a predicate is precomputable only when its constant is known before encryption.Across the query templates, 67.5% of TPC-H predicates and 71.6% of TPC-DS predicates are precomputable on average.Source: §9.2 · pp. 14–15

9.2.1. Evaluation of Encrypted Bitmap Indices.

  • Bitmaps accelerate the arithmetic approach by 6.39–52.55× on three TPC-H queries but only 1.01–1.33× on three TPC-DS queries.TPC-H bitmap indices remove 84.4–98.1% of execution time; high-cardinality comparisons remain online for TPC-DS Q3 and Q7.Source: §9.2.1 · p. 15, Table 6 · p. 15
  • Encrypted bitmap indices plus HULK improve performance by 14.10× on average over online-comparison arithmetic, with most of the gain coming from bitmaps.Bitmaps remove comparison for precomputable predicates, and HULK accelerates the remaining bitwise composition; together they cost 0.58× (Tier-1) to 1.83× (Tier-2) extra storage.Source: §9.2.1 · p. 15

10. Discussion and Future Work

HULK separates bulk addition-based bitwise reduction from the residual multiplication-based decoding work, enabling the reduction phase to run near the data. In the simulated storage-centric design, NAND flash parallelism and in-place reduction improve performance over GPU-only HULK.

1) Accelerating HULK with Near-Data Processing

  • HULK places the bulk HAdd phase inside NAND flash and offloads the residual HMul phase to a compute-optimized processor.The two phases have different hardware demands: HAdd is data-movement-bound, while HMul is compute-bound.Source: §10 · pp. 15–16
  • Bit-serial addition maps polynomial coefficients across NAND flash bitlines and exploits plane-, die-, chip-, and channel-level parallelism.In the workflow, flash-array latches hold carry bits while sum bits move to SSD-internal DRAM; controller cores perform modular reduction.Source: §10 · p. 16

Results

  • 1.30–1.75× speedup: HULK (SC-GPU) outperforms HULK (GPU), with the benefit increasing as reduction depth K grows.The comparison is shown for different reduction depths K.Source: Figure 10 · p. 16, §10 · p. 16
  • NAND flash parallelism increases HAdd throughput, while in-flash tree reductions cut data transferred out of the SSD by K×.These are the two stated causes of the storage-centric design's performance benefit.Source: §10 · p. 16

2) Improving indicator evaluation

  • Indicator evaluation is HULK’s only homomorphic multiplication use, and bit extraction remains the dominant overhead in most end-to-end workloads.The paper identifies advances in homomorphic digit or bit extraction as a direct benefit to HULK.Source: §10 · p. 16

11. Other Related Work

Prior work addresses encrypted search, Boolean logic, and HE acceleration, but the approaches differ in their support for bit-sliced data and packed SIMD throughput. HULK evaluates wide bulk bitwise operations on bit-sliced data in packed B/FV by slot-wise addition and a single indicator.

Other Related Work

  • HULK is presented as the first work to evaluate wide bulk bitwise operations on bit-sliced data in packed B/FV using slot-wise addition and a single indicator.Earlier approaches add before testing in other settings, including whole-word tests and match indicators across records.Source: §11 · p. 16

Encrypted search

  • Encrypted-search approaches generate equality predicates but do not reduce bit-sliced data; bit-sliced Fermat tests are 1.8–77× slower than the product tree for AND-K (K=2–128).The cited comparison is for p=65537 and requires one test per 16-bit digit.Source: §11 · pp. 16–17

Boolean and gate-level HE

  • Boolean HE supports bit-level logic but typically lacks the packed SIMD-style throughput of RLWE-based arithmetic HE for the targeted workloads.The passage characterizes Boolean HE as better suited to fine-grained logic.Source: §11 · p. 17

HE acceleration

  • HE accelerators primarily target arithmetic kernels, while conventional arithmetic HE is difficult to map efficiently onto near-data substrates that HULK better aligns with.The passage notes that processing-using-memory and in-flash processing use analog properties of memory and storage systems.Source: §11 · p. 17

12. Conclusion

HULK constructs bulk bitwise operations with addition-dominant logic to reduce costly homomorphic multiplication. Across 13 end-to-end applications, it improves performance over the state-of-the-art arithmetic approach.

Conclusion

  • 7.26× on CPU and 6.65× on GPU: HULK improves performance over the state-of-the-art arithmetic approach across 13 end-to-end applications.The applications span healthcare, graph, and database analytics; a simulated near-storage design further improves performance.Source: §12 · p. 17
Loading 2610.18391v1…