torus/docs/core-features/bit_extraction.md

Bit Extraction

This document provides an overview of the bit extraction feature in Torus, including usage examples, limitations, and performance considerations.

Overview

Bit extraction could be useful in some applications that require directly manipulating bits of integers. Bit extraction allows you to extract a specific slice of bits from an integer, where index 0 corresponds to the least significant bit (LSB). The cost of this operation increases with the index of the highest significant bit you wish to extract.

{% hint style="warning" %} Bit extraction only works in the Native encoding, which is usually selected when all table lookups in the circuit are less than or equal to 8 bits. {% endhint %}

Extracting a specific bit

from torus import fhe

@fhe.compiler({"x": "encrypted"})
def f(x):
    return fhe.bits(x)[0], fhe.bits(x)[3]

inputset = range(32)
circuit = f.compile(inputset)

assert circuit.encrypt_run_decrypt(0b_00000) == (0, 0)
assert circuit.encrypt_run_decrypt(0b_00001) == (1, 0)

assert circuit.encrypt_run_decrypt(0b_01100) == (0, 1)
assert circuit.encrypt_run_decrypt(0b_01101) == (1, 1)

Extracting multiple bits with slices

You can use slices for indexing fhe.bits(value) :

from torus import fhe

@fhe.compiler({"x": "encrypted"})
def f(x):
    return fhe.bits(x)[1:4]

inputset = range(32)
circuit = f.compile(inputset)

assert circuit.encrypt_run_decrypt(0b_01101) == 0b_110
assert circuit.encrypt_run_decrypt(0b_01011) == 0b_101

Bit extraction supports slices with negative steps:

from torus import fhe

@fhe.compiler({"x": "encrypted"})
def f(x):
    return fhe.bits(x)[3:0:-1]

inputset = range(32)
circuit = f.compile(inputset)

assert circuit.encrypt_run_decrypt(0b_01101) == 0b_011
assert circuit.encrypt_run_decrypt(0b_01011) == 0b_101

Bit extraction with signed integers

Bit extraction supports signed integers:

from torus import fhe

@fhe.compiler({"x": "encrypted"})
def f(x):
    return fhe.bits(x)[1:3]

inputset = range(-16, 16)
circuit = f.compile(inputset)

assert circuit.encrypt_run_decrypt(-14) == 0b_01  # -14 == 0b_10010 (in two's complement)
assert circuit.encrypt_run_decrypt(-12) == 0b_10  # -12 == 0b_10100 (in two's complement)

Use case example

Here's a practical example that uses bit extraction to determine if a number is even:

import numpy as np
from torus import fhe

@fhe.compiler({"x": "encrypted"})
def is_even(x):
    return 1 - fhe.bits(x)[0]

inputset = [
    np.random.randint(-16, 16, size=(5,))
    for _ in range(100)
]
circuit = is_even.compile(inputset)

sample = np.random.randint(-16, 16, size=(5,))
for value, value_is_even in zip(sample, circuit.encrypt_run_decrypt(sample)):
    print(f"{value} is {'even' if value_is_even else 'odd'}")

It prints:

13 is odd
0 is even
-15 is odd
2 is even
-6 is even

Limitations

• Negative indexing is not supported: Bits extraction using negative indices is not supported, such as fhe.bits(x)[-1].
  • This is because the bit-width of x is unknown before inputset evaluation, making it impossible to determine the correct bit to extract.
• Reverse slicing requires explicit starting bit: When extracting bits in reverse order (using a negative step), the start bit must be specified, for example, fhe.bits(x)[::-1] is not supported.
• Signed integer slicing requires explicit stopping bit: For signed integers, when using slices, the stop bit must be explicitly provided, for example, fhe.bits(x)[1:] is not supported.
• Float bit extraction is not supported: While Torus supports floats to some extent, bit extraction is not possible on float types.

Performance considerations

A Chain of individual bit extractions

Extracting a specific bit requires clearing all the preceding lower bits. This involves extracting these previous bits as intermediate values and then subtracting them from the input.

Implications:

• Bits are extracted sequentially, starting from the least significant bit to the more significant ones. The cost is proportional to the index of the highest extracted bit plus one.
• No parallelization is possible. The computation time is proportional to the cost, independent of the number of CPUs.

Examples:

• Extracting fhe.bits(x)[4] is approximately five times costlier than extracting fhe.bits(x)[0].
• Extracting fhe.bits(x)[4] takes around five times more wall clock time than fhe.bits(x)[0].
• The cost of extracting fhe.bits(x)[0:5] is almost the same as that of fhe.bits(x)[5].

Reuse of Intermediate Extracted Bits

Common sub-expression elimination is applied to intermediate extracted bits.

Implications:

• The overall cost for a series of fhe.bits(x)[m:n] calls on the same input x is almost equivalent to the cost of the single most computationally expensive extraction in the series, i.e. fhe.bits(x)[n].
• The order of extraction in that series does not affect the overall cost.

Example:

The combined operation fhe.bit(x)[3] + fhe.bit(x)[2] + fhe.bit(x)[1] has almost the same cost as fhe.bits(x)[3].

TLUs of 1b input precision

Each extracted bit incurs a cost of approximately one TLU of 1-bit input precision. Therefore, fhe.bits(x)[0] is generally faster than any other TLU operation.