L3 · FUNCTIONALMEASURED

Encrypted Matrix Inversion

encrypted-matrix-inversion · spec v0.1.0 · 0 implementations · 6 runners

Create implementationSpecification

DESCRIPTION

Computes A⁻¹ for an encrypted non-singular matrix, so that A × A⁻¹ = I.

Direct elimination is out of reach: pivoting means choosing a row by looking at values, and nobody can look. Realizations therefore iterate — Newton and Goldschmidt schemes converge to the inverse using only multiplication and subtraction, which is exactly the instruction set encrypted arithmetic offers. Depth grows with the number of iterations, so accuracy is bought in units of depth.

Singularity is the open edge of the problem. The kernel assumes the input is invertible, because detecting that it is not would itself require a decision on encrypted data.

INTERFACE

encrypted_matrix_inverse(
  in  ct     : Ciphertext  // the encrypted non-singular matrix A
  out ct     : Ciphertext  // the encrypted inverse of A
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

sizeinteger1 – 2^10

element_abs_maxnumber0.001 – 1000

condition_number_maxnumber1 – 1000000

target_precisionnumber0.5 – 1

The schema belongs to the kernel. Each implementation declares which part of it it supports.

CORRECTNESS

01The product of the input and the result approximates the identity within the declared precision.

02Accuracy is reported for the declared conditioning, not for well-conditioned inputs only.

03The number of iterations, and therefore the depth consumed, is reported with the result.

SECURITY PROPERTIES

The matrix stays encrypted throughout, and the iteration count must not depend on its contents, since that would leak conditioning.

ASSUMPTIONS

The input is non-singular. Detecting singularity is out of scope precisely because it is a decision on encrypted data.

REFERENCES

repoFHERMA participation guide

paperFHERMA Cookbook — linear algebra components