Encrypted Matrix Multiplication

Definition

Matrix multiplication forms the product of two matrices. For square operands of order $N$,

so each entry of $C$ is the inner product of a row of $A$ with a column of $B$. Here both operands arrive encrypted, and the product is computed homomorphically without decrypting either.

Mathematical Domain

Matrix multiplication is defined over any ring of entries — integers, finite fields, or the real and complex numbers. Under a homomorphic scheme the entries live in the scheme's plaintext domain, and the arithmetic is the scheme's arithmetic — approximate for CKKS, exact for a BGV/BFV-style scheme — rather than textbook field arithmetic.

The product also depends on how each matrix is packed into ciphertext slots. An $N\times N$ product admits many layouts — one ciphertext per matrix, one ciphertext per row, a diagonal encoding, or two matrices packed together — and each trades homomorphic rotations against multiplications and against multiplicative depth. The kernel fixes none of this; a specification pins the entry domain, the packing freedom, and the correctness rule.

Parameters Defined by Specifications

A specification narrows the general operation into a concrete computational problem by fixing:

• the entry domain and homomorphic scheme (for example f64 under CKKS)
• the matrix order $N$ and shape constraints (here, square)
• which operands are secret and which are public
• the encoding / packing freedom and how the result is decoded
• the correctness or accuracy rule and how it is scored
• which evaluation keys (rotation, relinearization) an answer may declare and use

Applications

Matrix multiplication is the inner loop of linear algebra and of machine learning: dense layers, attention, and the forward and backward passes of training are all chains of matrix products. Its encrypted cost therefore decides whether private inference and confidential analytics are practical, and the depth a product spends matters as much as its wall-clock time — a shallow product leaves room in the same ciphertext budget for the layers that follow. A known winning solution (Aikata's, published in the polycircuit library and answering secret-matrices@1.0.0) computes the $N\times N$ product with a row-wise encoding in multiplicative depth 2, using $N + N\log_2 N + 1$ rotations in place of the naive $N^2$.