# Are there any signatures based on matrix multiplication with noise?

Are there any signatures based on matrix multiplication with noise? Representing the message as a matrix and multiplying with some randomness coming from another matrix such that the signature itself is a matrix?

• Jul 19 '16 at 22:15
• Lamport One Way signatures use a matrix as rivate and public key, but the input and output are no matrix. Do you have a special case where you need the input and ouptu to be a matrix? Or what is the motivation for this? There are some gutter based cryptographical primitives though but I am not fully familiar with them. And out of curiosity, one can format any matrix into a string, what is the desired advantage of the matrix? Some hash functions use matrix multiplications during hashing to introduce artificial noise though...
– JRsz
Jul 25 '16 at 10:05
• My motivation is non-cummutative signature aggregation Jul 25 '16 at 19:08
• Sounds to me like McEliece, see en.wikipedia.org/wiki/McEliece_cryptosystem May 2 '17 at 17:07

There are two major families of signature schemes that bear some resemblance what you described.

## Code-based signatures: Courtois–Finiasz–Sendrier, or CFS

The CFS family of signature schemes is based on code-based cryptography first introduced by Robert McEliece in 1978 and dualized by Niederreiter. We work with binary linear codes, of length $n$ and rank $k$ correcting up to $t$ errors.

In the error-correcting code scenario, a sender with a $k$-bit message $m$ redundantly encodes it as an $n$-bit codeword $c$ from a $k$-dimensional subspace of all $n$-bit strings, and sends it along a noisy channel; the receiver, on receiving a possibly modified message $c' = c + e$, can uniquely recover $c$ as the codeword nearest to $c'$ as long as the error pattern $e$ has no more than $t$ bits set, i.e. as long as the Hamming weight of $e$ is at most $t$.

The generator matrix of a linear code is a $k$-by-$n$ matrix $G$ that that transforms $k$-bit messages to $n$-bit codewords: $c = G m$. The parity-check matrix of a linear code is an $n$-by-$(n-k)$ matrix $K$ that transforms $n$-bit strings to $(n-k)$-bit syndromes. An $n$-bit string is a codeword in the code if and only if its syndrome is zero: $K c = 0$, and $H c' = K\cdot(c + e) = K c + K e = K e$. The syndrome decoding problem is to find $e$ given $K e$. The premise of CFS signatures is that finding the noise given a syndrome given only the parity-check matrix $K$ seems to be difficult without additional information about the structure of the linear code.

Parameters. Bit sizes $n$, $k$, $t$ for a family of binary linear codes, usually binary Goppa codes (other proposals like Reed–Solomon codes have been broken, although there are new candidates, e.g. Reed–Muller codes in the pqsigRM submission to NIST PQCRYPTO), and a random function $H\colon \{0,1\}^* \to \mathbb F_2^{n-k}$ from messages to syndromes.

Public keys. Alice's public key is the parity-check matrix $K$ of a binary linear code of length $n$ and rank $k$ correcting up to $t$ errors.

Signatures. A signature by Alice on a message $m$ is an error pattern $e \in \mathbb F_2^n$ such that $K e = H(m)$. That is, a signature is the noise whose multiplication by a parity-check matrix yields a syndrome that is the hash of a message.

Private keys and signing. Too complicated to fit in the margins of this crypto.se post; see McBits for a modern implementation strategy of CFS signatures and Niederreiter KEM, and Classic McEliece for a NIST PQCRYPTO submission based on it (but KEM-only, no signatures), which also have concrete parameter suggestions for reasonable post-quantum security levels. (The pqsigRM submission to NIST PQCRYPTO may have some implementation ideas too, but its supporting documentation makes no mention of side channel attacks or constant-time algorithms, and a brief look at the code makes me suspicious.)

## Lattice-based signatures

Let $q$ be a prime, and let $F$ be the field $\mathbb Z/q\mathbb Z$. Fix a secret vector $s \in F^n$, a sample of uniform random vectors $a_i \in F^n$, and a sample of errors $e_i \in \mathbb Z$ with some distribution $\chi$

The computational learning with errors problem, introduced by Regev in 2005, is to find $s$ given the sample $(a_i, \langle a_i, s\rangle + e_i) \in F^n \times F$ with nonnegligible probability.

The decisional learning with errors problem is to distinguish it from $(a_i, v_i)$ for uniform random $v_i \in F$. There are a few variants on the theme: for example, in the ring learning with errors problem, we replace the vector space $F^n$ by the ring $F/(x^n + 1)$ when $n$ is a power of two, or $F/(\Phi(x))$ for some polynomial $\Phi(x) \in F[x]$, which was introduced by Lyubashevsky, Peikert, and Regev in 2010 to admit much smaller parameters.

This is a sketch of the Lyubahsevsky's learning with errors signature scheme, derived from the same Fiat–Shamir transform used to derive Schnorr signatures, and on which newer systems such as the NIST PQCRYPTO submission qTESLA are based.

Parameters. Field $F$; dimensions $n$, $m$, and $k$; bound $d$; bounded distribution $\chi$ on $\mathbb Z^m$; a standard $n$-by-$m$ matrix $A$ in $F$; and a random function $H\colon \{0,1\}^* \to \{-1,0,+1\}^k$ such that $\lVert H(M)\rVert_1$ is bounded.

Public keys. Alice's public key is an $n$-by-$k$ matrix $T$ in $F$.

Signatures. A signature by Alice on a message $\mu$ is a pair of $z \in \mathbb Z^m$ and $c \in \mathbb Z^k$ such that

1. $\lVert z\rVert^2 = \sum_i {z_i}^2$ is small, and
2. $c = H(\underline{A z_q - T c_q} \mathbin\Vert \mu)$, where $z_q$ and $c_q$ are the componentwise projections of $z$ and $c$ onto $F = \mathbb Z/q\mathbb Z$, and the underline is some canonical bit string encoding of $F$.

(For the technical details of what ‘small’ means, see the paper.)

Private key and signing. Alice's private key is a secret $m$-by-$k$ matrix $S$ in $\mathbb Z$ whose elements are chosen uniformly at random from integers at most $d$ in absolute value. Let $S_q$ be the componentwise projection of the matrix $S$ onto $F$. Alice computes her public key by $T = A S_q$. (With an appropriate transformation of $A$, this is not far from the form of the learning-with-errors problem.)

To sign a message $\mu$, Alice draws $y \in \mathbb Z^m$ from $\chi$, computes $c = H(\underline{A y_q} \mathbin\Vert \mu)$ and $z = S c + y$, and, with some rejection sampling on $z$, reveals $(c, z)$.

This satisfies criterion (1) of signatures because of the bounds on $S$, $c = H(\cdots)$, and $y \sim \chi$.

This satisfies criterion (2) of signatures because $A z_q - T c_q = A S_q c_q + A y_q - A S_q c_q = A y_q$, so $c = H(\underline{A y_q} \mathbin\Vert \mu) = H(\underline{A z_q - T c_q} \mathbin\Vert \mu)$.

Filling in details is left as an exercise for a less tired ossifrage than this one, preferably when day is not breaking.