Diagonal Primitives (FHEON-D)

The diagonal primitives evaluate the layers of a network over channel diagonals instead of folding every input channel into every output channel. They are provided for single inputs by FHEONANNDiagonalController, which runs sequentially. The controller declares its primitives with the names and arguments they have in FHEONANNStandardController (see Shared interface), so a model switches between the standard and the diagonal implementation by changing only the controller type.

Layouts

Compact channel blocks (ResNet, VGG). A tensor of C channels of width w is held in one ciphertext as C consecutive blocks of w^2 slots: channel c is in slots c w^2 ... (c+1) w^2 - 1. The ciphertext has exactly C w^2 slots, so every stage of a network (one per width) has its own slot count, bootstrapping keys and key file.

Strided layout (LeNet-5). Rows rowStride slots apart, columns colStride apart, input channels and output groups channelStride apart. A “valid” convolution keeps the strides of its input and a pooling leaves its sums in place (twice the strides), so no layer compacts its output. The channels of an output group are interleaved in the gaps a pooling leaves (subShifts, the offset of each channel inside its group): the multiplexed packing. The layout is described by the optional FHEONLayout argument of the primitives:

FHEONLayout field

Meaning

rowStride, colStride

slots between two rows / columns; rowStride = 0 selects the compact layout

channelStride, numGroups, subShifts

slots between two channels / output groups, number of output groups, offset of each channel inside its group

inputSlots, outputSlots

slot count of an input that cannot be derived (rotation keys), slot count of a pooling output

channelGroup

channels compacted together in the first channel stage of a stride-2 downsampling (0: default)

weightScale

factor multiplied into the encoded weights (the 1/4 of a preceding sum pooling, a ReLU scale)

inputPositions

linear layer: the slot(s) of every input (several slots are summed, which fuses a pooling into the layer)

Primitives

Primitive

Implementation

Cost

he_convolution (3x3, padding 1, stride 1)

he_convolution_diagonal

8 hoisted rotations for the taps (±1, ±w, ±(w±1)), one rotation per diagonal (Horner form, a single rotation key), 9 plaintext products per diagonal, one level. The padding masks are folded into the kernel plaintexts. With fewer input than output channels the input is replicated first.

he_convolution (k x k, padding 0)

he_convolution_layout

k^2 - 1 hoisted taps; per sub shift inputChannels + numGroups - 1 diagonals (one rotation and k^2 products each) and one final rotation; one level. Output in the strided layout.

he_convolution_and_shortcut_optimized (3x3 stride 2 + 1x1 shortcut)

he_convolution_and_shortcut_diagonal, downsample_channels

the 4 stride phases of the input are compacted once (masked doublings: log2(w/2) levels for the columns, 1 for the rows, 1 or 2 for the channels), the convolution and the shortcut share their taps, and both outputs land in the layout of the next stage

he_avgpool (2x2, stride 2)

he_sumpool_layout (strided layout) or he_avgpool_diagonal

window sums: 3 hoisted rotations and no level left in place, or the same downsampling onto outputSlots. The 1/4 goes into the next weights (avgpool_weight_scale).

he_globalavgpool

rotation tree, then masked_rotation_sum

the average of channel c in slot c: log2(w^2) rotations for the sums, one rotation key for the gathering, two levels. The ResNet and VGG models fuse the global pooling into the first linear layer instead (inputPositions)

he_linear

he_linear_diagonal

numDiagonals (the outputs rounded up to a power of two) plaintext products, baby-step giant-step rotations (linear_baby_steps), log2(slots / numDiagonals) folding rotations, one level. Inputs anywhere (inputPositions); the output has numDiagonals slots, so the following ReLU and bootstrapping are small.

he_relu

he_relu_scalar, he_relu_normalized

Chebyshev approximation: 6, 5 or 4 levels at degree 59, 27 or 13, plus one when the input is scaled. normalizedOutput returns ReLU(x / s) within [0, 1].

he_sum_two_ciphertexts

residual additions at matching levels

The rotations of every primitive come from generate_convolution_rotation_positions, generate_avgpool_rotation_positions and generate_linear_rotation_positions, which return exactly the rotations the primitive uses. The weights are encoded with the controller’s encode_convolution_kernel, encode_convolution_bias, encode_shortcut_kernel, encode_linear_weights and encode_linear_bias (on FHEONHEController::encode_kernel_diagonal, encode_kernel_layout, encode_bias_diagonal, encode_bias_layout, encode_shortcut_diagonal and encode_linear_diagonal), at the level returned by convolution_kernel_level, so no plaintext is adjusted during a layer. Internally, a ciphertext reused by many products is rescaled once (rescale_pending) and the products of a diagonal are accumulated directly on its polynomials (plain_inner_product).

Shared interface

The diagonal controller declares the primitives above with the names and arguments of FHEONANNStandardController, together with the encoders, the rotation-key generators and convolution_kernel_level. The layout options that only the diagonal primitives use are passed in the optional FHEONLayout argument, which the standard controller ignores. The models use the alias ANNDiagonalController.

Security levels

At a standard security level (-DSECURITY_LEVEL=128, 192, 256) the ring dimension follows from the modulus chain (Security Levels, Ring Dimension and Packing). The LeNet-5 diagonal programs fill every slot of that ring (HEConfig.fillSlots): with 16384 slots or more, conv2 runs its 16 channels as 16 parallel groups instead of 4 groups of 4 interleaved channels. They also run a leveled chain there (no bootstrapping), whose small scale fits a 2^15 ring at 128 bits.

Background

The primitives combine known techniques: the diagonal method and hoisted rotations of Halevi and Shoup (Algorithms in HElib, CRYPTO 2014; Faster Homomorphic Linear Transformations in HElib, CRYPTO 2018), channel mixing by rotating channel blocks and the hybrid method for rectangular linear layers (Gazelle, USENIX Security 2018), and the strided, multiplexed packing of Lee et al. (Low-Complexity Deep Convolutional Neural Networks on FHE using Multiplexed Parallel Convolutions, ICML 2022).

Performance

The following timings were measured on one machine (Intel Core Ultra 7 265K, 20 threads, 31 GB RAM, OpenFHE 1.5.1), with the performance-efficient parameters and the same predictions in every pair. Seconds per image:

Model

Standard

Diagonal

Note

LeNet-5

14.1 (LeNet5)

2.17 (LeNet5Diagonal)

sequential controllers

ResNet-20

454 (ResNet20Optimized)

84 (ResNet20Diagonal)

sequential controllers

The diagonal models are described in Diagonal Examples, and the measurements of all the models in Evaluation.