LWE

LWE attributes

BitFieldEncodingAttr

An attribute describing encoded LWE plaintexts using bit fields.

Syntax:

#lwe.bit_field_encoding<
  unsigned,   # cleartext_start
  unsigned   # cleartext_bitwidth
>

A bit field encoding of an integer describes which contiguous region of bits a small integer occupies within a larger integer.

The data describing the encoding consists of the starting bit positions of the cleartext bit field and its width, where the LSB is bit 0 and the MSB is bit bit_width-1. So the above example would have starting bit 30 and width 3. The bits not specified for the message have semantics defined by the scheme or lowering.

Note that this encoding does not specify the underlying bit width of the plaintext space. This is left for lowerings to decide.

The presence of this attribute as the encoding attribute of a tensor indicates that the tensor is an LWE ciphertext.

Example (CGGI):

#encoding = #lwe.bit_field_encoding<cleartext_start=30, cleartext_bitwidth=3>
!plaintext = !lwe.lwe_plaintext<encoding = #encoding>

%0 = arith.constant 4 : i3
%1 = lwe.encode %0 { encoding = #encoding }: i3 to !plaintext

The above represents an LWE plaintext encoding the 3-bit cleartext 4 as an LWE ciphertext in a 32-bit integer, with a single bit of padding at the MSB. This corresponds to the following, where 0 denotes a 0 bit, b denotes a bit of the cleartext, n denotes a bit reserved for noise, and | is a visual aid to show where the bit fields begin and end.

   0|bbb|nn...n
MSB^          ^LSB

Example (BGV):

Note: BGV uses the RLWE encodings, but they have the same bit-field encoding attributes as here. So this example serves mainly to show how this attribute can be used to specify storing bits in the LSB of a plaintext.

#encoding = #lwe.bit_field_encoding<cleartext_start=4, cleartext_bitwidth=4>
!plaintext = !lwe.lwe_plaintext<encoding = #encoding>

%0 = arith.constant 9 : i4
%1 = lwe.encode %0 { encoding = #encoding }: i4 to !plaintext

The above represents an LWE plaintext encoding a 4-bit cleartext as an LWE ciphertext in the least-significant bits of a larger integer. This corresponds to the following.

   nn...n|bbbb
MSB^         ^LSB

Parameters:

LWEParamsAttr

Syntax:

#lwe.lwe_params<
  IntegerAttr,   # cmod
  unsigned   # dimension
>

Parameters:

RLWEParamsAttr

Syntax:

#lwe.rlwe_params<
  unsigned,   # dimension
  ::mlir::heir::polynomial::RingAttr   # ring
>

An attribute describing classical RLWE parameters:

• dimension: the number of polynomials used in an RLWE sample, analogous to LWEParams.dimension.
• ring: the polynomial ring to use.

Parameters:

UnspecifiedBitFieldEncodingAttr

An attribute describing unspecified bit field encodings.

Syntax:

#lwe.unspecified_bit_field_encoding<
  unsigned   # cleartext_bitwidth
>

See LWE_BitFieldEncoding for a description of bit field encodings.

This attribute describes an unspecified bit field encoding; this is where the starting bit position of the cleartext bit field is unspecified, but its width is fixed. A noise growth analysis should be performed to determine the optimal amount of bits needed for noise and padding to specify the bit field encodings starting bit position.

Example:

#lwe_encoding = #lwe.unspecified_bit_field_encoding<cleartext_bitwidth=3>
%lwe_ciphertext = arith.constant <[1,2,3,4]> : tensor<4xi32, #lwe_encoding>

Parameters:

InverseCanonicalEmbeddingEncodingAttr

An attribute describing encoded RLWE plaintexts via the rounded inverse canonical embedding.

Syntax:

#lwe.inverse_canonical_embedding_encoding<
  unsigned,   # cleartext_start
  unsigned   # cleartext_bitwidth
>

Let $n$ be the degree of the polynomials in the plaintext space. An “inverse canonical embedding encoding” of a list of real or complex values $v_1, \dots, v_{n/2}$ is (almost) the inverse of the following decoding map.

Define a map $\tau_N$ that maps a polynomial $p \in \mathbb{Z}[x] / (x^N + 1) \to \mathbb{C}^{N/2}$ by evaluating it at the following $N/2$ points, where $\omega = e^{2 \pi i / 2N}$ is the primitive $2N$th root of unity:

[ \omega, \omega^3, \omega^5, \dots, \omega^{N-1} ]

Then the complete decoding operation is $\textup{Decode}(p) = (1/\Delta)\tau_N(p)$, where $\Delta$ is a scaling parameter and $\tau_N$ is the truncated canonical embedding above. The encoding operation is the inverse of the decoding operation, with some caveats explained below.

The map $\tau_N$ is derived from the so-called canonical embedding $\tau$, though in the standard canonical embedding, we evaluate at all odd powers of the root of unity, $\omega, \omega^3, \dots, \omega^{2N-1}$. For polynomials in the slightly larger space $\mathbb{R}[x] / (x^N + 1)$, the image of the canonical embedding is the subspace $H \subset \mathbb{C}^N$ defined by tuples $(z_1, \dots, z_N)$ such that $\overline{z_i} = \overline{z_{N-i+1}}$. Note that this property holds because polynomial evaluation commutes with complex conjugates, and the second half of the roots of unity evaluate are complex conjugates of the first half. The converse, that any such tuple with complex conjugate symmetry has an inverse under $\tau$ with all real coefficients, makes $\tau$ is a bijection onto $H$. $\tau$ and its inverse are explicitly computable as discrete Fourier Transforms.

Because of the symmetry in canonical embedding for real polynomials, inputs to this encoding can be represented as a list of $N/2$ complex points, with the extra symmetric structure left implicit. $\tau_N$ and its inverse can also be explicitly computed without need to expand the vectors to length $N$.

The rounding step is required to invert the decoding because, while cleartexts must be (implicitly) in the subspace $H$, they need not be the output of $\tau_N$ for an integer polynomial. The rounding step ensures we can use integer polynomial plaintexts for the FHE operations. There are multiple rounding mechanisms, and this attribute does not specify which is used, because in theory two ciphertexts that have used different roundings are still compatible, though they may have different noise growth patterns.

The scaling parameter $\Delta$ is specified by the cleartext_start and cleartext_bitwidth parameters, which are applied coefficient-wise using the same semantics as the bit_field_encoding.

This attribute can be used in multiple ways:

• On a poly.poly, it asserts that the polynomial has been transformed from a coefficient list using the canonical embedding.
• On a tensor of poly.poly, it asserts that the tensor is an RLWE ciphertext for some RLWE scheme that supports the approximate embedding encoding.

A typical flow for the CKKS scheme using this encoding would be to apply an inverse FFT operation to invert the canonical embedding to be a polynomial with real coefficients, then encrypt scale the resulting polynomial’s coefficients according to the scaling parameters, then round to get integer coefficients.

Example:

#generator = #poly.polynomial<1 + x**1024>
#ring = #poly.ring<cmod=65536, ideal=#generator>
#lwe_encoding = #lwe.polynomial_evaluation_encoding<cleartext_start=30, cleartext_bitwidth=3>

%evals = arith.constant <[1, 2, 4, 5]> : tensor<4xi16>
%poly1 = poly.intt %evals : tensor<4xi16, #ring> -> !poly.poly<#ring, #eval_encoding>
%poly2 = poly.intt %evals : tensor<4xi16, #ring> -> !poly.poly<#ring, #eval_encoding>
%rlwe_ciphertext = tensor.from_elements %poly1, %poly2 : tensor<2x!poly.poly<#ring, #eval_encoding>>

See bit_field_encoding for the definition of the cleartext_start and cleartext_bitwidth fields.

Parameters:

PolynomialCoefficientEncodingAttr

An attribute describing encoded RLWE plaintexts via coefficients.

Syntax:

#lwe.polynomial_coefficient_encoding<
  unsigned,   # cleartext_start
  unsigned   # cleartext_bitwidth
>

A coefficient encoding of a list of integers asserts that the coefficients of the polynomials contain the cleartexts, with the same semantics as bit_field_encoding for per-coefficient encodings.

The presence of this attribute as the encoding attribute of a tensor of poly.poly indicates that the tensor is an RLWE ciphertext for some RLWE scheme that supports the coefficient encoding.

See bit_field_encoding for the definition of the cleartext_start and cleartext_bitwidth fields.

Example:

#generator = #poly.polynomial<1 + x**1024>
#ring = #poly.ring<cmod=65536, ideal=#generator>
#coeff_encoding = #lwe.polynomial_coefficient_encoding<cleartext_start=15, cleartext_bitwidth=4>

%poly1 = poly.from_tensor %coeffs1 : tensor<10xi16> -> !poly.poly<#ring>
%poly2 = poly.from_tensor %coeffs2 : tensor<10xi16> -> !poly.poly<#ring>
%rlwe_ciphertext = tensor.from_elements %poly1, %poly2 : tensor<2x!poly.poly<#ring>, #coeff_encoding>

Parameters:

PolynomialEvaluationEncodingAttr

An attribute describing encoded RLWE plaintexts via evaluations at fixed points.

Syntax:

#lwe.polynomial_evaluation_encoding<
  unsigned,   # cleartext_start
  unsigned   # cleartext_bitwidth
>

A “evaluation encoding” of a list of integers $(v_1, \dots, v_n)$ asserts that $f(x_1 ) = v_1, \dots, f(x_n) = v_n$ for some implicit, but fixed and distinct choice of inputs $x_i$. The encoded values are also scaled by a scale factor, having the same semantics as bit_field_encoding, but applied entry-wise (to either the coefficient or evaluation representation).

This attribute can be used in multiple ways:

• On a poly.poly, it asserts that the polynomial has been transformed from an evaluation tensor.
• On a tensor of poly.poly, it asserts that the tensor is an RLWE ciphertext for some RLWE scheme that supports the evaluation encoding.

A typical workflow for the BFV/BGV schemes using this encoding would be to apply a INTT operation to the input list of cleartexts to convert from evaluation form to coefficient form, then encrypt the resulting polynomial in coefficient form, then apply NTT back to the evaluation form for faster multiplication of ciphertexts.

The points chosen are fixed to be the powers of a primitive root of unity of the coefficient ring of the plaintext space, which allows one to use NTT/INTT to tansform quickly between the coefficient and evaluation forms.

Example:

#generator = #poly.polynomial<1 + x**1024>
// note that the cmod should be chosen so as to ensure a primitive root of
// unity exists in the multiplicative group (Z / cmod Z)^*
#ring = #poly.ring<cmod=65536, ideal=#generator>
#lwe_encoding = #lwe.polynomial_evaluation_encoding<cleartext_start=30, cleartext_bitwidth=3>

%evals = arith.constant <[1, 2, 4, 5]> : tensor<4xi16>
%poly1 = poly.intt %evals : tensor<4xi16, #ring> -> !poly.poly<#ring, #eval_encoding>
%poly2 = poly.intt %evals : tensor<4xi16, #ring> -> !poly.poly<#ring, #eval_encoding>
%rlwe_ciphertext = tensor.from_elements %poly1, %poly2 : tensor<2x!poly.poly<#ring, #eval_encoding>>

See bit_field_encoding for the definition of the cleartext_start and cleartext_bitwidth fields.

Parameters:

LWE types

LWECiphertextType

A type for LWE ciphertexts

Syntax:

!lwe.lwe_ciphertext<
  ::mlir::Attribute,   # encoding
  LWEParamsAttr   # lwe_params
>

A type for LWE ciphertexts.

This type keeps track of the plaintext integer encoding for the LWE Ciphertext to ensure proper decoding after decryption. It also keeps track of the ring where the LWE ciphertext is defined, which provides information on the ciphertext shape and the ring operations used in LWE operations.

Parameters:

LWEPlaintextType

A type for LWE plaintexts

Syntax:

!lwe.lwe_plaintext<
  ::mlir::Attribute   # encoding
>

A type for LWE plaintexts.

This type keeps track of the plaintext integer encoding for the LWE plaintext before it is encrypted.

Parameters:

RLWECiphertextType

A type for RLWE ciphertexts

Syntax:

!lwe.rlwe_ciphertext<
  ::mlir::Attribute,   # encoding
  RLWEParamsAttr,   # rlwe_params
  Type   # underlying_type
>

Parameters:

RLWEPlaintextType

A type for RLWE plaintexts

Syntax:

!lwe.rlwe_plaintext<
  ::mlir::Attribute,   # encoding
  ::mlir::heir::polynomial::RingAttr,   # ring
  Type   # underlying_type
>

Parameters:

RLWEPublicKeyType

A public key for RLWE

Syntax:

!lwe.rlwe_public_key<
  RLWEParamsAttr   # rlwe_params
>

Parameters:

RLWESecretKeyType

A secret key for RLWE

Syntax:

!lwe.rlwe_secret_key<
  RLWEParamsAttr   # rlwe_params
>

Parameters:

LWE ops

lwe.encode (heir::lwe::EncodeOp)

Encode an integer to yield an LWE plaintext

Syntax:

operation ::= `lwe.encode` $plaintext attr-dict `:` qualified(type($plaintext)) `to` qualified(type($output))

Encode an integer to yield an LWE plaintext.

This op uses a an encoding attribute to encode the bits of the integer into an LWE plaintext value that can then be encrypted.

Examples:

%Y = lwe.encode %value {encoding = #enc}: i1 to !lwe.lwe_plaintext<encoding = #enc>

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Operands:

Results:

lwe.rlwe_decode (heir::lwe::RLWEDecodeOp)

Decode an RLWE plaintext to an underlying type

Syntax:

operation ::= `lwe.rlwe_decode` $input attr-dict `:` qualified(type($input)) `->` qualified(type($output))

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Operands:

Results:

lwe.rlwe_encode (heir::lwe::RLWEEncodeOp)

Encode an integer to yield an RLWE plaintext

Syntax:

operation ::= `lwe.rlwe_encode` $input attr-dict `:` qualified(type($input)) `->` qualified(type($output))

Encode an integer to yield an RLWE plaintext.

This op uses a an encoding attribute to encode the bits of the integer into an RLWE plaintext value that can then be encrypted.

Examples:

%Y = lwe.rlwe_encode %value {encoding = #enc, ring = #ring}: i1 to !lwe.rlwe_plaintext<encoding = #enc, ring = #ring>

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Operands:

Results:

lwe.trivial_encrypt (heir::lwe::TrivialEncryptOp)

Create a trivial encryption of a plaintext.

Syntax:

operation ::= `lwe.trivial_encrypt` operands attr-dict `:`  qualified(type(operands)) `to` qualified(type(results))

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Operands:

Results:

lwe.reinterpret_underlying_type (heir::lwe::ReinterpretUnderlyingTypeOp)

A placeholder cast from one ciphertext type to another

Syntax:

operation ::= `lwe.reinterpret_underlying_type` $input attr-dict `:` qualified(type($input)) `to` qualified(type($output))

The cast op is thus used to translate underlying_type between ciphertexts in particular situations , such as when lowering to an API that does not keep track of types for you.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results: