Skip to content

Roll and Rotation

Vector (CKKS)

         Original: [1, 2, 3, 4]
 Left Rotate by 1: [2, 3, 4, 1] (Roll)
Right Rotate by 1: [4, 1, 2, 3] (Rotate)

When rotating a vector, there are 2 choices. Rotate to the left or to the right.

Many of the existing FHE libraries, such as Microsoft SEAL and OpenFHE, has opted for using the left rotation.

However, FHE is now being utilized more and more for complex calculations, many of which involve matrix operations. In this space, many of the existing python data science libraries, such as NumPy, pytorch or TensorFlow support right rotation.

There is no set rule on the rotation direction, but any direction is quite confusing to the people who are used to one direction of rotation. This is why the DESILO FHE library offers both roll and rotate methods.

  • The roll method will shift the input vector to the right for positive shift values, as is in NumPy.
  • The rotate method will shift the input vector to the left for positive shift values, as is in SEAL.

Matrix (GL)

GL input matrices are 3-dimensional, and supports roll along each of the axis. Since an axis is always associated with a roll operation, the DESILO FHE library has opted for only supporting the roll method.

Examples

import numpy as np

a = np.arange(4 * 4 * 4).reshape((4, 4, 4))

array([[[ 0,  1,  2,  3],
        [ 4,  5,  6,  7],
        [ 8,  9, 10, 11],
        [12, 13, 14, 15]],

       [[16, 17, 18, 19],
        [20, 21, 22, 23],
        [24, 25, 26, 27],
        [28, 29, 30, 31]],

       [[32, 33, 34, 35],
        [36, 37, 38, 39],
        [40, 41, 42, 43],
        [44, 45, 46, 47]],

       [[48, 49, 50, 51],
        [52, 53, 54, 55],
        [56, 57, 58, 59],
        [60, 61, 62, 63]]])

Roll along the batch axis

np.roll(a, shift=1, axis=0)

array([[[48, 49, 50, 51],
        [52, 53, 54, 55],
        [56, 57, 58, 59],
        [60, 61, 62, 63]],

       [[ 0,  1,  2,  3],
        [ 4,  5,  6,  7],
        [ 8,  9, 10, 11],
        [12, 13, 14, 15]],

       [[16, 17, 18, 19],
        [20, 21, 22, 23],
        [24, 25, 26, 27],
        [28, 29, 30, 31]],

       [[32, 33, 34, 35],
        [36, 37, 38, 39],
        [40, 41, 42, 43],
        [44, 45, 46, 47]]])

Roll along the height axis

np.roll(a, shift=1, axis=1)

array([[[12, 13, 14, 15],
        [ 0,  1,  2,  3],
        [ 4,  5,  6,  7],
        [ 8,  9, 10, 11]],

       [[28, 29, 30, 31],
        [16, 17, 18, 19],
        [20, 21, 22, 23],
        [24, 25, 26, 27]],

       [[44, 45, 46, 47],
        [32, 33, 34, 35],
        [36, 37, 38, 39],
        [40, 41, 42, 43]],

       [[60, 61, 62, 63],
        [48, 49, 50, 51],
        [52, 53, 54, 55],
        [56, 57, 58, 59]]])

Roll along the width axis

np.roll(a, shift=1, axis=2)

array([[[ 3,  0,  1,  2],
        [ 7,  4,  5,  6],
        [11,  8,  9, 10],
        [15, 12, 13, 14]],

       [[19, 16, 17, 18],
        [23, 20, 21, 22],
        [27, 24, 25, 26],
        [31, 28, 29, 30]],

       [[35, 32, 33, 34],
        [39, 36, 37, 38],
        [43, 40, 41, 42],
        [47, 44, 45, 46]],

       [[51, 48, 49, 50],
        [55, 52, 53, 54],
        [59, 56, 57, 58],
        [63, 60, 61, 62]]])

Optimization Tips

Key Selection

To roll a ciphertext by 3 slots, there are roughly 3 options:

  1. roll 3 times with a fixed roll key of shift 1.
  2. roll 1 time with a fixed roll key of shift 3.
  3. roll with a roll key.

Internally, the roll key would roll twice, once with a fixed roll key of shift 1 and then again with a fixed roll key of shift 2. Because of this, the runtime of option 1 would be roughly 3 times slower than that of option 2, and the runtime of option 3 would be roughly 2 times slower than that of option 2.

In general, using the roll key is recommended unless there is a very specific set of shift values. For the roll key, the worst shift value is -1, which means every since fixed roll key is utilized, resulting in 12 to 15 internal rolls. In this case, have a fixed roll key with shift -1 (which is normalized to slot_count - 1) or using the Rotation Key would be much faster.

Roll with Several Different Shifts

Before the advent of GL, CKKS was used to simulate matrices. Vector indices would be rolled and multiplied, and the product would be rolled back to achieve the same effect of matrix multiplication. In this case, it is typical that a single ciphertext is rolled by several different shift values.

Thankfully, the homomorphic roll and rotation has several internal steps, and some of the early steps is the same regardless of the shift/delta value. Taking advantage of this characteristic makes it possible to efficiently roll a single ciphertext with multiple shift values. The DESILO FHE library offers roll_many and rotate_many methods to support this batch shift. It is possible to use a list of fixed roll/rotation key or a single roll/rotation key. A list of fixed roll/rotation key could use more memory but would be faster, so is the recommended method.

Examples

from desilofhe import Engine

engine = Engine()
secret_key = engine.create_secret_key()
fixed_roll_key_shift_1 = engine.create_fixed_roll_key(secret_key, shift=1)
fixed_roll_key_shift_2 = engine.create_fixed_roll_key(secret_key, shift=2)
fixed_roll_key_shift_3 = engine.create_fixed_roll_key(secret_key, shift=3)
fixed_roll_key_shift_4 = engine.create_fixed_roll_key(secret_key, shift=4)
roll_key = engine.create_roll_key(secret_key)

message = [1, 2, 3, 4]
ciphertext = engine.encrypt(message, secret_key)

rolled_ciphertexts_1 = engine.roll_many(
    ciphertext,
    [
        fixed_roll_key_shift_1,
        fixed_roll_key_shift_2,
        fixed_roll_key_shift_3,
        fixed_roll_key_shift_4,
    ],
)

rolled_ciphertexts_2 = engine.roll_many(
    ciphertext, roll_key, shifts=[1, 2, 3, 4]
)