APEX: Accurate Parallel Expressive Homomorphic Execution for Encrypted Databases

Fully homomorphic encryption (FHE) promises end-to-end secure cloud databases by enabling arbitrary queries directly over encrypted data, without ever exposing plaintext. However, existing FHE-based databases must trade off SIMD parallelism against exact query semantics, as they rely on approximate methods to exploit large-scale SIMD, limiting their practicality. This paper presents APEX, the first FHE database that jointly achieves efficient SIMD execution and precise SQL semantics within a single-scheme BGV/BFV framework. Our key insight is that the dominant bottleneck lies not in the schemes themselves but in data encoding: prior layouts misalign ciphertext slots with column and predicate semantics, squandering SIMD capacity. Therefore, Apex introduces a semantics-aware unified encoding UniCo that decomposes numeric and string values into bounded, position-weighted segments and aligns them with ciphertext slots across rows by data type and position. This alignment enables predicate comparisons to exploit bounded value ranges via Range-Aware Homomorphic Comparison (RAHC) and operate over an application-chosen small domain rather than the full plaintext modulus, making SIMD far more effective. Furthermore, to preserve efficiency and correctness for arbitrary-precision values, Apex employs Parallel Lazy Carry Propagation (PLCP), which defers crosssegment carry handling until needed and thus simplifies homomorphic query execution. Compared to state-of-the-art FHE databases, APEX achieves up to $8 \times$ speedup on TPC$\mathbf{H}$ benchmarks, and up to $\mathbf{2 0 9, 2 1 3} \times$ acceleration for string pattern matching with single- and multi-character wildcards.