Concrete
WebsiteLibrariesProducts & ServicesDevelopersSupport
2.10
2.10
  • Welcome
  • Get Started
    • What is Concrete?
    • Installation
    • Quick start
    • Quick overview
    • Terminology
  • Operations
    • Table Lookups basics
    • Non-linear operations
    • Other operations
      • Bit extraction
      • Common tips
      • Extensions
  • Compilation
    • Combining compiled functions
      • With composition
      • With modules
    • Key-related options for faster execution
      • Multi precision
      • Multi parameters
    • Compression
    • Reusing arguments
    • Parameter compatibility with restrictions
    • Common errors
  • Execution / Analysis
    • Simulation
    • Debugging and artifact
    • Performance
    • GPU acceleration
    • Other
      • Statistics
      • Progressbar
      • Formatting and drawing
  • Guides
    • Configure
    • Manage keys
    • Deploy
    • TFHE-rs Interoperability
      • Shared key
      • Serialization
    • Optimization
      • Improve parallelism
        • Dataflow parallelism
        • Tensorizing operations
      • Optimize table lookups
        • Reducing TLU
        • Implementation strategies
        • Round/truncating
        • Approximate mode
        • Bit extraction
      • Optimize cryptographic parameters
        • Error probability
        • Composition
  • Tutorials
    • See all tutorials
    • Part I: Concrete - FHE compiler
    • Part II: The Architecture of Concrete
  • References
    • API
    • Supported operations
  • Explanations
    • Compiler workflow
    • Advanced features
      • Table Lookups advanced
      • Rounding
      • Truncating
      • Floating points
      • Comparisons
      • Min/Max operations
      • Bitwise operations
      • Direct circuits
      • Tagging
    • Cryptography basics
    • Security
    • Frontend fusing
  • Developers
    • Contributing
      • Project layout
      • Compiler backend
        • Adding a new backend
      • Optimizer
      • MLIR FHE dialects
        • FHELinalg dialect
        • FHE dialect
        • TFHE dialect
        • Concrete dialect
        • Tracing dialect
        • Runtime dialect
        • SDFG dialect
      • Call FHE circuits from other languages
      • Benchmarking
      • Examples
      • Making a release
    • Release note
    • Feature request
    • Bug report
Powered by GitBook

Libraries

  • TFHE-rs
  • Concrete
  • Concrete ML
  • fhEVM

Developers

  • Blog
  • Documentation
  • Github
  • FHE resources

Company

  • About
  • Introduction to FHE
  • Media
  • Careers
On this page
  • Overview
  • Extracting a specific bit
  • Extracting multiple bits with slices
  • Bit extraction with signed integers
  • Use case example
  • Limitations
  • Performance considerations
  • A Chain of individual bit extractions
  • Reuse of Intermediate Extracted Bits
  • TLUs of 1b input precision

Was this helpful?

Export as PDF
  1. Operations
  2. Other operations

Bit extraction

This document provides an overview of the bit extraction feature in Concrete, 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.

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.

Extracting a specific bit

from concrete 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 concrete 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 concrete 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 concrete 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 concrete 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 Concrete 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.

PreviousOther operationsNextCommon tips

Last updated 1 month ago

Was this helpful?