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
  • Operations on encrypted values
  • Noise and Bootstrap
  • Probability of Error
  • Function evaluation
  • PBS management

Was this helpful?

Export as PDF
  1. Explanations

Cryptography basics

PreviousTaggingNextSecurity

Last updated 1 month ago

Was this helpful?

This document provides an overview of Fully Homomorphic Encryption (FHE) to get you started with Concrete. For more comprehensive resources about FHE, visit or .

Operations on encrypted values

Homomorphic encryption allows computations on ciphertexts without revealing the underlying plaintexts. A scheme is considered if it supports an unlimited number of additions and multiplications.

Let xxx represent a plaintext and E[x]E[x]E[x] the corresponding ciphertext:

  • Homomorphic addition: E[x]+E[y]=E[x+y]E[x] + E[y] = E[x + y]E[x]+E[y]=E[x+y]

  • Homomorphic multiplication: E[x]∗E[y]=E[x∗y]E[x] * E[y] = E[x * y]E[x]∗E[y]=E[x∗y]

Noise and Bootstrap

FHE encrypts data as LWE ciphertexts, represented visually as a bit vector. The encrypted message is located in the higher-order (yellow) bits, while the lower-order (gray) bits contain random noise that ensures the security of the ciphertext.

Each operation on an encrypted value increases the noise, and if it becomes too large, it may overlap with the message and corrupt its value. To reduce the noise of a ciphertext, the Bootstrap operation generates a new ciphertext encrypting the same message, but with lower noise. This allows additional operations to be performed on the encrypted message.

In typical FHE programs, operations are followed by a bootstrap, and this sequence repeats multiple times.

Probability of Error

The amount of noise in a ciphertext is not as bounded as it may appear in the above illustration. As the errors are drawn randomly from a Gaussian distribution, they can be of varying size. This means that we need to be careful to ensure the noise terms do not affect the message bits. If the error terms do overflow into the message bits, this can cause an incorrect output (failure) when bootstrapping.

The noise in a ciphertext isn't strictly bounded, as errors are drawn from a Gaussian distribution and vary in size. If the noise grows too large, it may corrupt the message bits, causing incorrect outputs during bootstrapping.

In Concrete, the default failure probability is set to 1100000\frac{1}{100000}1000001​, meaning that 1 in every 100,000 executions may result in an error. Reducing this probability requires adjusting cryptographic parameters, potentially lowering performance. Conversely, allowing a higher probability of error may improve performance.

Function evaluation

Concrete uses PBS to evaluate functions homomorphically:

  • Homomorphic univariate function evaluation: f(E[x])=E[f(x)]f(E[x]) = E[f(x)]f(E[x])=E[f(x)]

For example, consider a function (or circuit) that takes a 4 bits input variable and output the maximum value between a clear constant and the encrypted input:

import numpy as np

def encrypted_max(x: uint4):
    return np.maximum(5, x)

This function could be turned into a table lookup:

def encrypted_max(x: uint4):
    lut = [5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    return lut[x]

The Lookup table lut being applied during the Programmable Bootstrap.

PBS management

You don't need to manage PBS operations manually, as they are handled automatically by Concrete during the compilation process. Each function evaluation is converted into a lookup table and evaluated via PBS.

For example, if you inspect the MLIR code generated by the frontend, you’ll see the lookup table in the 4th line of the following output:

module {
  func.func @main(%arg0: !FHE.eint<4>) -> !FHE.eint<4> {
    %cst = arith.constant dense<[5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]> : tensor<16xi64>
    %0 = "FHE.apply_lookup_table"(%arg0, %cst) : (!FHE.eint<4>, tensor<16xi64>) -> !FHE.eint<4>
    return %0 : !FHE.eint<4>
  }
}

There are 2 things to keep in mind about PBS:

  • Input type constraints: PBS operations adds constraints on input type and thus limits the maximum bit-width supported in Concrete.

While we’ve covered arithmetic operations, typical programs also involve functions (for example, maximum, minimum, square root). In , the Bootstrap operation can be enhanced with a , creating a Programmable Bootstrap (PBS).

PBS performance impact: PBS operations are costly, so minimizing the number of PBS can improve circuit performance. PBS cost also varies with input precision (for example, an 8-bit PBS is faster than a 16-bit PBS). To learn more about optimizing PBS, refer to the section.

Optimization
the awesome Zama repo
fhe.org
fully homomorphic
TFHE
Table Lookup