L3 · FUNCTIONALMEASURED

Encrypted Singular Value Decomposition

encrypted-svd · spec v0.1.0 · 0 implementations · 6 runners

Create implementationSpecification

DESCRIPTION

Factors an encrypted matrix A into U · Σ · Vᵀ, or into the leading components of that factorization.

This is the hardest of the linear algebra kernels: the decomposition is defined by an eigenvalue problem, and every classical algorithm for it is iterative with data-dependent stopping. Under encryption the stopping rule cannot depend on the data, so a realization runs a fixed schedule and reports what it converged to.

Most uses do not need the full factorization. A truncated decomposition — the leading k singular values with their vectors — is the practical target, and the truncation rank is a parameter rather than a shortcut.

INTERFACE

encrypted_svd(
  in  ct     : Ciphertext  // the encrypted matrix A
  out ct     : Ciphertext  // the encrypted components: singular vectors and singular values
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

rowsinteger1 – 2^12

columnsinteger1 – 2^12

rankinteger1 – 2^12

target_precisionnumber0.5 – 1

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

CORRECTNESS

01Reconstructing from the returned components approximates the input within the declared precision.

02Singular values come back in descending order.

03Singular vectors are orthonormal within the declared precision; a factorization that loses orthogonality is not one.

SECURITY PROPERTIES

The matrix and every intermediate stay encrypted. The iteration schedule is fixed in advance, since a data-dependent one would leak the spectrum.

ASSUMPTIONS

The dimensions and the truncation rank are public.

REFERENCES

repoFHERMA participation guide

paperFHERMA Cookbook — linear algebra components