Fully Homomorphic Encryption (FHE) and lattice-based cryptography promise a world where cloud servers can compute on encrypted data without ever decrypting it. However, the practical adoption of these technologies has long been bottlenecked by massive computational and storage overheads.
Traditional lattice cryptography relies on the standard Learning With Errors (LWE) problem, which fundamentally operates on high-dimensional matrices and vectors. Performing vector operations—such as inner products, matrix multiplications, or distance metrics—under standard LWE requires either heavy matrix-vector multiplications or complex ciphertext "rotations" in Single Instruction, Multiple Data (SIMD) slot configurations.
To overcome this bottleneck, a powerful paradigm shift has emerged: polynomial vector packing (also known as coefficient encoding) within ring-based lattice structures like Ring-LWE (RLWE) and NTRU. By mapping vector data directly into the coefficients of polynomial rings, cryptographic operations can leverage native polynomial arithmetic to compute complex vector mathematics in a single homomorphic multiplication, bypassing costly rotations and drastically shrinking key sizes.
The Algebraic Shift from Matrices to Rings
Why does moving from standard LWE to a ring structure change the computational game? In standard LWE, cryptographic keys and ciphertexts are represented as large matrices and vectors. As shown by Dai et al. and Sun et al., transitioning to Ring-LWE replaces these high-dimensional matrix operations with polynomial arithmetic over a quotient ring (typically $\mathbb{Z}_q[X]/(X^N+1)$).
This representational shift yields two immediate benefits:
- Storage Reduction: Instead of storing an entire matrix, a key can be represented as a compact polynomial. Dai et al. demonstrated that this reduces key storage requirements by over three orders of magnitude. Similarly, Kim et al. leveraged this compactness to make post-quantum key encapsulation viable on resource-constrained IoT devices with limited SRAM.
- Computational Complexity: As explained by Yang et al., replacing matrix-vector multiplications with polynomial ring operations reduces the computational complexity of lattice protocols from quadratic ($O(n^2)$) or cubic to near-linear ($O(N \log N)$) via fast polynomial multiplication algorithms.
Bypassing Ciphertext Rotations via Coefficient Encoding
To perform vector math in homomorphic encryption, the traditional approach has been SIMD-style "slot encoding," where each vector element is placed into an independent plaintext slot. While SIMD works well for element-wise addition, computing an inner product (the backbone of machine learning and data analysis) requires summing across the slots. In FHE, shifting data across slots requires a "ciphertext rotation"—an operation that is computationally heavy, noise-inducing, and requires massive rotation keys.
Polynomial vector packing solves this by using coefficient encoding. Instead of putting vector elements into slots, elements are mapped directly to the coefficients of a single polynomial.
As highlighted by Wang et al. and Ren et al., this completely eliminates the need for ciphertext rotations during linear transformations. Instead of rotating slots, the system relies on standard linear algebra libraries and polynomial multiplication to aggregate data automatically.
The Magic of Algebraic Convolution
Why does multiplying two polynomials compute a vector inner product? The answer lies in the mechanics of polynomial multiplication, which inherently performs an algebraic convolution.
Consider two vectors, $\mathbf{u} = (u_0, u_1, \dots, u_{n-1})$ and $\mathbf{v} = (v_0, v_1, \dots, v_{n-1})$. If we encode $\mathbf{u}$ into a polynomial $U(X)$ and a reversed version of $\mathbf{v}$ into $V(X)$:
$$U(X) = \sum_{i=0}^{n-1} u_i X^i, \quad V(X) = \sum_{j=0}^{n-1} v_{n-1-j} X^j$$
When we multiply $U(X) \cdot V(X)$, the cross-terms accumulate. Specifically, the coefficient of the $X^{n-1}$ term in the resulting product polynomial will be exactly:
$$\sum_{i=0}^{n-1} u_i v_i = \mathbf{u} \cdot \mathbf{v}$$
By simply extracting a single coefficient from the resulting ciphertext, we obtain the exact scalar product.
Vector U: [ u0, u1, u2 ] --> Polynomial U(X): u0 + u1*X + u2*X^2
Vector V: [ v0, v1, v2 ] --> Polynomial V(X): v2 + v1*X + v0*X^2 (Reversed)
Multiplying U(X) * V(X) yields a product where the X^2 coefficient is:
(u0*v0) + (u1*v1) + (u2*v2) <-- Exactly the Dot Product!
Lu et al. utilized this forward and backward packing technique to compute scalar products for secure genome-wide association studies using just a single homomorphic multiplication. Similarly, Yasuda et al. demonstrated that high-dimensional binary vectors can be packed to calculate Hamming distances in a single multiplication, drastically reducing the memory footprint for biometric matching.
Chen et al. applied this to federated learning (AegisFL), showing that inner products, $L_2$ norms, and arithmetic means can all be evaluated with a single ciphertext multiplication, yielding a 24x to 30x speedup over rotation-heavy methods. For large-scale face recognition, Bai et al. packed multiple face vectors into a single polynomial to minimize ciphertext overhead and storage. Beyond simple inner products, Jung et al. showed that modular arithmetic properties can even transform additive operations into multiplicative ones to evaluate complex multivariate polynomials efficiently.
Optimizing the Underlying Polynomial Engine
To make polynomial arithmetic as fast as possible, the underlying cryptographic schemes must be tightly coupled with efficient number-theoretic representations.
- Residue Number Systems (RNS) and NTT: Rather than handling massive integers directly, Kim et al. adapted approximate homomorphic encryption to a full RNS and double-CRT representation. This decomposes polynomials into matrices of small integers, enabling component-wise arithmetic using standard 64-bit word operations and the Number Theoretic Transform (NTT).
- Composite Moduli: To accelerate bootstrapping (the noise-clearing operation in FHE), Li et al. introduced native polynomial arithmetic over composite spaces via a tree-based primitive root construction, eliminating expensive basis extensions.
- NTRU Structural Compactness: Beyond RLWE, Li et al. demonstrated that NTRU-based ciphertexts offer a distinct structural advantage: they use a single polynomial instead of a pair, enabling cleaner hardware dataflows and sub-4 millisecond bootstrapping runtimes.
By shifting from rigid matrix representations to the fluid, convolutional nature of polynomial rings, polynomial vector packing transforms the fundamental bottleneck of homomorphic encryption—multiplication—into its greatest algorithmic strength.
Key Foundational Work
Privacy-preserving genome-wide association studies on cloud environment using fully homomorphic encryption (2015) — contributed 2 concept elements to this direction.
Packed Homomorphic Encryption Based on Ideal Lattices and Its Application to Biometrics (2013) — contributed 2 concept elements to this direction.
Privacy-preserving data aggregation without secure channel: Multivariate polynomial evaluation (2013) — contributed 1 concept elements to this direction.