Volley Revolver: A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference)

This paper introduces "Volley Revolver," a novel matrix-encoding method that enables efficient privacy-preserving neural network inference via homomorphic encryption, demonstrated by a convolutional neural network that classifies 32 encrypted MNIST images in approximately 287 seconds on a public cloud while requiring only a single ciphertext upload.

The Gist

Imagine you have a secret recipe for a delicious cake (your private data), and you want a famous chef (a cloud server) to tell you if it's good, but you don't want the chef to see the recipe or taste the raw ingredients. You also don't want the chef to steal your recipe.

This is the problem Volley Revolver solves. It's a new method for doing math on "locked" data (encrypted data) so that a cloud server can run a neural network (an AI brain) on your private images without ever seeing what those images actually are.

Here is the breakdown using simple analogies:

1. The Problem: The "Locked Box" Dilemma

Usually, to get an AI to recognize a handwritten number (like a "7"), you send the image to the cloud. But if you send it as a normal picture, the cloud can see it. If you encrypt it (lock it in a box), the cloud can't open it to do the math.

Homomorphic Encryption (HE) is like a magical glove box. You can put your ingredients inside, and the chef can mix, bake, and taste them through the gloves without ever opening the box. However, doing this math is incredibly slow and clunky. It's like trying to solve a complex puzzle while wearing thick winter gloves.

2. The Solution: "Volley Revolver"

The authors created a new way to pack data into these locked boxes to make the math faster. They call it Volley Revolver.

The Analogy: The Revolver Cylinder

Imagine a revolver with a cylinder that holds 6 bullets.

• Old Way: To check if a bullet is loaded, you have to spin the cylinder one click at a time, check, spin again, check again. This is slow.
• Volley Revolver: Imagine a special cylinder where you can load multiple bullets in a specific pattern. When you pull the trigger, instead of firing one bullet, the mechanism aligns all the bullets at once so you can check them all simultaneously.

In the paper, this means packing 32 different images into a single "locked box" (ciphertext). Instead of asking the cloud to do the math 32 times (once for each image), the cloud does the math 32 times at once in a single operation. This is called SIMD (Single Instruction, Multiple Data).

3. How It Handles the "Convolution" (The AI's Eyes)

Neural networks look at images using "kernels" (small filters that slide over the image to find edges or shapes).

• The Old Problem: Sliding a filter over an encrypted image is like trying to slide a piece of paper through a locked safe. You have to rotate the paper, check a spot, rotate again, check another spot. It takes forever.
• The Volley Revolver Trick: The authors figured out how to "spread out" the filter (the kernel) before locking it up. They create a set of "virtual" locked boxes inside the real one.
  • Think of it like a 3D hologram. Instead of a flat sheet of paper, the data is arranged in a 3D structure inside the box.
  • When the cloud needs to slide the filter, it doesn't have to physically move the paper. It just rotates the hologram. Because of the clever way the data was packed, this rotation instantly aligns the filter with the correct part of the image for all 32 images simultaneously.

4. The "Virtual Ciphertexts"

The paper introduces a cool concept: Virtual Ciphertexts.
Imagine you have one giant safe (the real ciphertext). Inside that safe, you have 32 smaller, invisible safes (virtual ciphertexts), each holding one image.

• The cloud server doesn't know the smaller safes exist; it just sees the big safe.
• But when the cloud performs an operation (like adding or multiplying), the magic of Volley Revolver ensures that the operation happens inside all 32 invisible safes at the exact same time.
• It's like a conductor waving a baton, and 32 different orchestras playing the same note perfectly in sync, even though they are all in the same room.

5. The Results: Fast and Private

The authors tested this on the MNIST dataset (handwritten numbers).

• The Setup: They took 32 images of handwritten numbers, locked them into one single box (about 20 MB in size), and sent it to a cloud server with 40 powerful processors.
• The Result: The cloud processed all 32 images and told them the answer (e.g., "This is a 7") in about 287 seconds.
• The Privacy: The cloud server never saw the numbers. It only saw the locked box. The data owner only had to send one box, not 32 separate ones.

Why This Matters

Before this, doing AI on encrypted data was so slow it was practically useless for real-time things.

• Efficiency: By packing 32 images into one box and using the "Revolver" rotation trick, they made the process much faster.
• Scalability: It shows that we can eventually run complex AI models on private data (like medical records or bank statements) without ever exposing the raw data to the cloud.

In summary: Volley Revolver is a clever packing technique that lets us do massive amounts of math on locked data all at once, turning a slow, clunky process into a fast, synchronized dance of encrypted numbers. It's the difference between checking one lock at a time and checking a whole bank vault with a single, magical key turn.

Technical Summary

Here is a detailed technical summary of the paper "Volley Revolver: A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference)" by John Chiang.

1. Problem Statement

The paper addresses the challenge of performing privacy-preserving inference on Convolutional Neural Networks (CNNs) using Homomorphic Encryption (HE).

• The Core Issue: While HE allows computation on encrypted data without decryption, standard HE schemes (like CKKS) suffer from high computational overhead and limited "multiplicative depth" (the number of sequential multiplications allowed before noise renders the ciphertext unusable).
• Specific Bottlenecks:
  • Matrix Multiplication: Existing methods for encrypting matrices often require complex shifting or multiple ciphertexts, leading to inefficiency.
  • Convolution: Performing convolution on encrypted images is computationally expensive because it requires summing products over sliding windows, often necessitating numerous rotation operations.
  • Batching: Efficiently processing multiple images simultaneously (SIMD batching) within a single ciphertext while maintaining the structural integrity of 2D/3D image data is difficult.
  • Activation Functions: Non-linear activation functions (like ReLU) must be approximated by polynomials, which increases circuit depth.

2. Methodology: The "Volley Revolver" Framework

The authors propose a novel matrix-encoding scheme called Volley Revolver, designed to optimize matrix multiplication and convolution operations within the HE domain.

A. Core Encoding Strategy

• Matrix Representation: Instead of treating data as a flat vector, Volley Revolver encodes data into a 2D matrix structure within a single ciphertext.
  • Matrix $A$ (Input): Encoded directly row-by-row.
  • Matrix $B$ (Weights/Kernel): Encoded as the transpose of the weight matrix, tiled vertically to match the dimensions of $A$.
• The "Revolver" Mechanism:
  • To compute $C = A \times B$, the system keeps $A$ fixed and "rotates" the encoded version of $B$ (like a revolver cylinder).
  • A specialized operation called RowShifter cyclically shifts the rows of the encrypted matrix $B$.
  • In each iteration, the system performs a homomorphic multiplication between $A$ and the shifted $B$, followed by a column summation (SumColVec) to aggregate the partial results.
  • This allows the calculation of arbitrary matrix products with a complexity of $O(p \log p)$ rotations, where $p$ is the number of columns in the result.

B. Convolution via "Virtual Ciphertexts"

• Kernel Spanning (Kernelspanner): Before inference, convolution kernels are expanded into $k^2$ distinct ciphertexts (where $k$ is the kernel size). Each ciphertext represents the kernel "slid" to a specific position within the image space.
• Virtual Ciphertexts (3D Simulation):
  • The authors introduce a simulation technique where a single real ciphertext is treated as containing multiple virtual ciphertexts.
  • If a ciphertext has enough slots to hold $m$ images, the system simulates $m$ independent virtual ciphertexts.
  • Operations (Add, Mul, Rot) are performed on the real ciphertext, which simultaneously affects all virtual ciphertexts.
  • Virtual Rotation (vRot): A complex operation requiring two real rotations and masking to simulate the rotation of data within a specific virtual image block without affecting others.
• SumForConv: An algorithm that accumulates the results of the element-wise multiplications between the image and the expanded kernels, effectively performing the convolution sum.

C. Handling Non-Linearity

• Since HE cannot compute ReLU directly, the authors use a degree-3 polynomial approximation (derived via least squares) to replace the ReLU activation function in all layers.

3. Key Contributions

1. Volley Revolver Encoding: A novel method for encoding matrices that enables efficient homomorphic multiplication of arbitrary shapes by rotating the transpose of the second matrix.
2. Efficient Convolution Algorithm: A strategy using "Kernelspanner" and "SumForConv" to perform convolution by pre-expanding kernels and accumulating intermediate results, reducing the need for repeated complex shifting during inference.
3. Virtual Ciphertext Simulation: A conceptual and algorithmic framework to treat a single ciphertext as a 3D structure containing multiple virtual images, enabling massive parallelism (SIMD) and preserving spatial relationships.
4. Optimized FC Layer Handling: A specific encoding for Fully Connected layers that aligns weight matrices to power-of-two dimensions to minimize the number of required rotations (degenerating complex RowShifter logic into simple rotations).

4. Experimental Results

The framework was evaluated on the MNIST dataset (handwritten digits) using a custom CNN architecture.

• Setup:
  • Hardware: Public cloud instance with 40 vCPUs.
  • Batch Size: 32 images (28x28 grayscale) packed into a single ciphertext (~19.8 MB).
  • Security: 80-bit security level (Ring dimension $N=2^{16}$, Modulus $Q \approx 2^{1200}$).
• Performance:
  • Inference Time: Approximately 287 seconds to compute likelihoods for 32 images in a single batch.
  • Accuracy: Achieved 98.61% classification accuracy, nearly matching the plaintext baseline (98.66%).
  • Communication: The data owner uploads only one ciphertext (~19.8 MB) for 32 images. The model provider uploads ~1 GB of encrypted weights (52 ciphertexts).
• Comparison with Baseline (CryptoNets-style):
  • Throughput: The proposed method achieves a 6.125x improvement in batching efficiency. While the baseline required 49 ciphertexts to process 64 images, Volley Revolver processes 392 images with the same number of ciphertexts (8 images per ciphertext).
  • Trade-off: The proposed method has higher inference latency due to the increased number of rotation operations and a deeper multiplicative circuit (due to degree-3 polynomials vs. degree-2 in baselines). However, it offers superior slot utilization and structural preservation.

5. Significance and Future Work

• Significance:
  • Scalability: Demonstrates that large-scale privacy-preserving inference is feasible by maximizing SIMD packing, reducing the number of ciphertexts required for batch processing.
  • Structural Integrity: The 3D tensor-native approach preserves the spatial structure of images better than flattening methods, making it more suitable for complex CNN architectures.
  • Hardware Agnosticism: The reliance on rotations (which are level-neutral) rather than deep multiplicative chains allows the system to scale better with hardware parallelism (e.g., GPUs/FPGAs) without exhausting the noise budget as quickly.
• Limitations & Future Directions:
  • Latency: Current latency is high (~5 minutes for 32 images), though this is expected to drop with parallel kernel execution.
  • Color Images: The current implementation focuses on grayscale. Future work aims to extend the "virtual ciphertext" concept to handle multi-channel (RGB) images by distributing channels across multiple ciphertexts.
  • Training: The authors note that the encoding scheme is also promising for FHE-based training (backpropagation), where the first matrix is rotated while the second remains static.

In conclusion, Volley Revolver represents a significant step forward in making Homomorphic Encryption practical for deep learning inference by optimizing how data is packed and manipulated, trading increased rotation operations for massive gains in batching efficiency and structural fidelity.