LWE

’lwe’ Dialect

The lwe dialect is a dialect for concepts related to cryptosystems in the Learning With Errors (LWE) family.

See Wikipedia for an overview of LWE and the related RLWE problem.

While one might expect this dialect to contain types along the lines of LWE and RLWE ciphertexts, and operations like encryption, decryption, adding and multiplying ciphertexts, these concepts are not centralized here because they are too scheme-specific.

Instead, this dialect provides attributes that can be attached to tensors of integer or poly.poly types, which indicate that they are semantically LWE and RLWE ciphertexts, respectively.

LWE attributes

ApplicationDataAttr

Syntax:

#lwe.application_data<
  mlir::Type,   # message_type
  Attribute   # overflow
>

An attribute describing the semantics of the underlying application data.

The messageType parameter is used to describe the type and bits of the original application data, e.g. i1, i32, f32. This type is later mapped into the plaintext space of an FHE scheme by embedding, scaling, or other techniques.

This attribute also contains information about the overflow semantics of the data in the application. By default, we assume that the application program was written so that the overflow is not expected and the overflow attribute can can be no_overflow. For LWE-based CGGI ciphertexts, the overflow attribute will usually be preserve_overflow, since messages will overflow into padding bits.

Parameters:

CiphertextSpaceAttr

Syntax:

#lwe.ciphertext_space<
  ::mlir::heir::polynomial::RingAttr,   # ring
  ::mlir::heir::lwe::LweEncryptionType,   # encryption_type
  unsigned   # size
>

An attribute describing the ciphertext space and the transformation from plaintext space to ciphertext space of an FHE scheme.

The ciphertext space information includes the ring attribute, describing the space that the ciphertext elements belong to. The ring attribute contains a coefficient type attribute that describes the semantics of the coefficient. For example, a ring modulo $1 + x^1024$ with coefficients modulo $q = 298374$ will be described as

!cmod = !mod_arith.int<298374 : i64>
#ring = #polynomial.ring<coefficientType = !cmod, polynomialModulus = <1 + x**1024>>
#ciphertext_space = #lwe.ciphertext_space<ring = #ring, encryption_type = lsb>

Ciphertexts using an RNS representation for $q$ will use an RNS type in their ring’s coefficient type attribute.

!limb1 = !mod_arith.int<2251799814045697 : i64>
!limb2 = !mod_arith.int<65537 : i64>
#rns_mod = !rns.rns<!limb1, !limb2>
#ring = #polynomial.ring<coefficientType = #rns_mod, polynomialModulus = <1 + x**1024>>
#ciphertext_space = #lwe.ciphertext_space<ring = #ring, encryption_type = lsb>

Scalar LWE ciphertexts (like those used in CGGI) use an ideal polynomial of degree 1, $x$. CGGI ciphertexts will typically use a power of two modulus and may use a native integer type for its coefficient modulus.

#ring = #polynomial.ring<coefficientType = i32, polynomialModulus = <1 + x**1024>>
#ciphertext_space = #lwe.ciphertext_space<ring = #ring, encryption_type = lsb>

The ciphertext encoding info is used to describe the way the plaintext data is encoded into the ciphertext (in the MSB, LSB, or mixed).

The size parameter is used to describe the number of polynomials comprising the ciphertext. This is typically 2 for RLWE ciphertexts that are made up of an $(a, b)$ pair and greater than 2 for LWE instances. For example, after an RLWE multiplication of two size 2 ciphertexts, the ciphertext’s size will be 3.

Parameters:

CoefficientEncodingAttr

An encoding of cleartexts directly as coefficients.

Syntax:

#lwe.coefficient_encoding<
  int64_t   # scaling_factor
>

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

A scaling_factor is optionally applied on the scalar when converting from a rounded floating point to an integer.

Example:

#coeff_encoding = #lwe.coefficient_encoding<scaling_factor=10000>

Parameters:

ConstantCoefficientEncodingAttr

An encoding of a scalar in the constant coefficient

Syntax:

#lwe.constant_coefficient_encoding<
  int64_t   # scaling_factor
>

An encoding of a single scalar into the constant coefficient of the plaintext.

All other coefficients of the plaintext are set to be zero. This encoding is used to encode scalar LWE ciphertexts where the plaintext space is viewed as a polynomial ring modulo x.

The scalar is first multiplied by the scaling_factor and then rounded to the nearest integer before encoding into the plaintext coefficient.

Example:

#coeff_encoding = #lwe.constant_coefficient_encoding<scaling_factor=10000>

Parameters:

FullCRTPackingEncodingAttr

An encoding of cleartexts via CRT slots.

Syntax:

#lwe.full_crt_packing_encoding<
  int64_t   # scaling_factor
>

This encoding maps a list of integers via the Chinese Remainder Theorem (CRT) into the plaintext space.

Given a ring with irreducible ideal polynomial f(x) and coefficient modulus q, f(x) can be decomposed modulo q into a direct product of lower-degree polynomials. This allows full SIMD-style homomorphic operations across the slots formed from each factor.

This attribute can only be used in the context of on full CRT packing, where the polynomial f(x) splits completely (into linear factors) and the number of slots equals the degree of f(x). This happens when q is prime and q = 1 mod n.

A scaling_factor is optionally applied on the scalar when converting from a rounded floating point to an integer.

Example:

#coeff_encoding = #lwe.full_crt_packing_encoding<scaling_factor=10000>

Parameters:

InverseCanonicalEncodingAttr

An encoding of cleartexts via the inverse canonical embedding.

Syntax:

#lwe.inverse_canonical_encoding<
  int64_t   # scaling_factor
>

Let $n$ be the degree of the polynomials in the plaintext space. An “inverse_canonical_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 scaling_factor, which are applied coefficient-wise using the same semantics as the constant_coefficient_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:

#canonical_encoding = #lwe.inverse_canonical_encoding<scaling_factor=10000>

Parameters:

KeyAttr

Syntax:

#lwe.key<
  int   # slot_index
>

An attribute describing the key with which the message is currently encrypted.

The key attribute describes the key with which the message is currently encrypted and decryption can be performed. For example, if the decryption of a ciphertext $c = (c_0(x), c_1(x))$ is performed by computing the inner product $(c_0(x), c_1(x)) \cdot (1, s(x))$ then the key is $(1, s(x))$.

The slot_index describes the key after using a Galois automorphism to rotate the plaintext slots by slot_index. This will correspond to an action $\phi_k: x \rightarrow x^k$ for some k that depends on the structure of the Galois group for the chosen scheme parameters. The corresponding key will have a new basis $(1, s(x^(k)))$.

Parameters:

ModulusChainAttr

Syntax:

#lwe.modulus_chain<
  ::llvm::ArrayRef<mlir::IntegerAttr>,   # elements
  int   # current
>

An attribute describing the elements of the modulus chain of an RLWE scheme.

Parameters:

NoOverflowAttr

An attribute informing that application data never overflows.

Syntax: #lwe.no_overflow

This attribute informs lowerings that a program is written so that the message data will never overflow beyond the message type.

// FIXME: Have a separate WraparoundOverflow, which lowers the same as NoOverflow?

PlaintextSpaceAttr

Syntax:

#lwe.plaintext_space<
  ::mlir::heir::polynomial::RingAttr,   # ring
  Attribute   # encoding
>

An attribute describing the plaintext space and the transformation from application data to plaintext space of an FHE scheme.

The plaintext space information is the ring structure, which contains the plaintext modulus $t$, which may be a power of two in the case of CGGI ciphertexts, or a prime power for RLWE. LWE ciphertexts use the ideal polynomial of degree 1 $x$. The plaintext modulus used in LWE-based CGGI plaintexts describes the full message space $\mathbb{Z}_p$ including the padding bits. The application data info attribute describes the space $\mathbb{Z}_p’$ where $p’ < p$ that the underlying message belongs to.

For RLWE schemes, this will include the type of encoding of application data integers to a plaintext space Z_p[X]/X^N + 1. This may be a constant coefficient encoding, CRT-based packing for SIMD semantics, or other slot packing. When using full CRT packing, the ring must split into linear factors. The CKKS scheme will also include attributes describing the complex encoding, including the scaling factor, which will change after multiplication and rescaling.

Parameters:

PreserveOverflowAttr

An attribute informing that application data overflows in the message type.

Syntax: #lwe.preserve_overflow

This attribute informs lowerings that a program is written so that the message data may overflow beyond the message type.

LWE types

LWECiphertextType

A ciphertext type

Syntax:

!lwe.lwe_ciphertext<
  ApplicationDataAttr,   # application_data
  PlaintextSpaceAttr,   # plaintext_space
  CiphertextSpaceAttr,   # ciphertext_space
  KeyAttr,   # key
  ModulusChainAttr   # modulus_chain
>

An LWE ciphertext will always contain the application data, plaintext space, ciphertext space, and key information.

A modulus chain is optionally specified for parameter choices in RLWE schemes that use more than one of modulus. When no modulus chain is specified, the ciphertext modulus is always the ciphertext ring’s coefficient modulus.

Parameters:

LWEPlaintextType

A plaintext type

Syntax:

!lwe.lwe_plaintext<
  ApplicationDataAttr,   # application_data
  PlaintextSpaceAttr   # plaintext_space
>

Parameters:

LWEPublicKeyType

A public key for LWE

Syntax:

!lwe.lwe_public_key<
  KeyAttr,   # key
  ::mlir::heir::polynomial::RingAttr   # ring
>

Parameters:

LWESecretKeyType

A secret key for LWE

Syntax:

!lwe.lwe_secret_key<
  KeyAttr,   # key
  ::mlir::heir::polynomial::RingAttr   # ring
>

Parameters:

LWE ops

lwe.add (heir::lwe::AddOp)

Add two LWE ciphertexts

Syntax:

operation ::= `lwe.add` operands attr-dict `:` type($output)

Traits: AlwaysSpeculatableImplTrait, Commutative, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

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

Encode an integer to yield an LWE plaintext

Syntax:

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

Encode an integer to yield an LWE plaintext.

This op uses an overflow attribute to indicate the overflow semantics. For CGGI ciphertexts, this will typically be preserve_overflow to indicate that the message bits can overflow into the carry bit space.

The LWE plaintext ring is constructed with a plaintext bit width using plaintext_bits and a polynomial modulus of x.

Examples:

%Y = lwe.encode %value {overflow = #overflow, plaintext_bits = 3}: i1 to !lwe.lwe_plaintext<application_data = #app_data, plaintext_space = #space>

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Operands:

Results:

lwe.mul_scalar (heir::lwe::MulScalarOp)

Multiply an LWE ciphertext by a scalar

Syntax:

operation ::= `lwe.mul_scalar` operands attr-dict `:`  functional-type(operands, results)

Traits: AlwaysSpeculatableImplTrait, Elementwise, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

lwe.radd (heir::lwe::RAddOp)

Add two RLWE ciphertexts

Syntax:

operation ::= `lwe.radd` operands attr-dict `:`  functional-type(operands, results)

Traits: AlwaysSpeculatableImplTrait, Commutative, Elementwise, InferTypeOpAdaptor, SameOperandsAndResultPlaintextTypes, SameOperandsAndResultRings, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

lwe.radd_plain (heir::lwe::RAddPlainOp)

Addition between RLWE ciphertext-plaintext

Syntax:

operation ::= `lwe.radd_plain` operands attr-dict `:`  functional-type(operands, results)

Traits: AlwaysSpeculatableImplTrait, Commutative, InferTypeOpAdaptor, IsCiphertextPlaintextOp, SameOperandsAndResultPlaintextTypes

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

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_decrypt (heir::lwe::RLWEDecryptOp)

Decrypt an RLWE ciphertext to a RLWE plaintext

Syntax:

operation ::= `lwe.rlwe_decrypt` operands attr-dict `:`  functional-type(operands, results)

Decrypt an RLWE ciphertext to yield a RLWE plaintext

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

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. CKKS cleartext inputs may be floating points, and a scaling factor described by the encoding will be applied.

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.rlwe_encrypt (heir::lwe::RLWEEncryptOp)

Encrypt an RLWE plaintext to a RLWE ciphertext

Syntax:

operation ::= `lwe.rlwe_encrypt` operands attr-dict `:`  functional-type(operands, results)

Encrypt an RLWE plaintext to yield a RLWE ciphertext.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

lwe.rmul (heir::lwe::RMulOp)

Multiplies two RLWE ciphertexts

Syntax:

operation ::= `lwe.rmul` operands attr-dict `:`  functional-type(operands, results)

Traits: AlwaysSpeculatableImplTrait, Commutative, Elementwise, InferTypeOpAdaptor, SameOperandsAndResultRings, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

lwe.rmul_plain (heir::lwe::RMulPlainOp)

Multiplication between RLWE ciphertext-plaintext

Syntax:

operation ::= `lwe.rmul_plain` operands attr-dict `:`  functional-type(operands, results)

Traits: AlwaysSpeculatableImplTrait, Commutative, InferTypeOpAdaptor, IsCiphertextPlaintextOp

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

lwe.rnegate (heir::lwe::RNegateOp)

Negate a RLWE ciphertexts

Syntax:

operation ::= `lwe.rnegate` operands attr-dict `:` type($output)

Traits: AlwaysSpeculatableImplTrait, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

lwe.rsub (heir::lwe::RSubOp)

Subtract two RLWE ciphertexts

Syntax:

operation ::= `lwe.rsub` operands attr-dict `:`  functional-type(operands, results)

Traits: AlwaysSpeculatableImplTrait, Elementwise, InferTypeOpAdaptor, SameOperandsAndResultPlaintextTypes, SameOperandsAndResultRings, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

lwe.rsub_plain (heir::lwe::RSubPlainOp)

Subtraction between RLWE ciphertext-plaintext

Syntax:

operation ::= `lwe.rsub_plain` operands attr-dict `:`  functional-type(operands, results)

Traits: AlwaysSpeculatableImplTrait, InferTypeOpAdaptor, IsCiphertextPlaintextOp, SameOperandsAndResultPlaintextTypes

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

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

Create a trivial encryption of a plaintext.

Syntax:

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

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Operands:

Results:

lwe.reinterpret_application_data (heir::lwe::ReinterpretApplicationDataOp)

A placeholder cast from one ciphertext type to another

Syntax:

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

The cast op is thus used to translate application data (e.g., message_type) between ciphertexts in particular situations, such as when the bitwidth of the message type changes, but this change is not observed in the plaintext space, or when lowering to an API that does not keep track of types.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

LWE additional definitions

LweEncryptionType

An enum attribute representing an encryption method

Cases: