Digital signature scheme using non-squarematrices
Jiale Chen, Dima Grigoriev, Vladimir Shpilrain

Computability in Europe, July 2023

Setup
Let K = Zq [x1 , . . . , xn ] denote the algebra of polynomials in n variables
over the ring Zq of integers modulo q, where an integer q is notnecessarily a prime.

2 / 27

Setup
Let K = Zq [x1 , . . . , xn ] denote the algebra of polynomials in n variables
over the ring Zq of integers modulo q, where an integer q is notnecessarily a prime.

Public:– k × l left invertible matrix M, with k > l, whose entries are sparse
polynomials from the algebra K .
– a hash function H (e.g., SHA-512) and a (deterministic) procedure forconverting values of H to vectors of sparse polynomials from the algebra
K.

3 / 27

Setup
Let K = Zq [x1 , . . . , xn ] denote the algebra of polynomials in n variables
over the ring Zq of integers modulo q, where an integer q is notnecessarily a prime.

Public:– k × l left invertible matrix M, with k > l, whose entries are sparsepolynomials from the algebra K .
– a hash function H (e.g., SHA-512) and a (deterministic) procedure forconverting values of H to vectors of sparse polynomials from the algebra
K.

Private: l × k right invertible matrix L over K , such that LM is the l × l
identity matrix.
4 / 27

Signature scheme

Signing a message m:

1

Apply a hash function H to m. Convert H(m) to a vector
U = (P1 , . . . , Pl ) of l (sparse) polynomials from the algebra K using
a deterministic public procedure.

2

Multiply the vector U by the (private) matrix L on the right to get avector V = UL = (Q1 , . . . , Qk ) of k polynomials from K .

3

The signature is the vector V.

5 / 27

Verification

1

The verifier computes the hash H(m) and converts H(m) to a vector
U = (P1 , . . . , Pl ) of l (sparse) polynomials using a deterministic
public procedure.

2

The verifier multiplies the signature vector V by the public matrix M
on the right to get a vector W.

3

The signature is accepted if and only if W = U.

6 / 27

Verification

1

The verifier computes the hash H(m) and converts H(m) to a vector
U = (P1 , . . . , Pl ) of l (sparse) polynomials using a deterministic
public procedure.

2

The verifier multiplies the signature vector V by the public matrix M
on the right to get a vector W.

3

The signature is accepted if and only if W = U.

Correctness is obvious since W = VM = (UL)M = U(LM) = U.

7 / 27

Generating a (left) invertible k × l matrix
Let k > l. To generate a (left) invertible k × l matrix, one can first
generate an invertible square k × k matrix and then remove k − lcolumns, selected at random.

8 / 27

Generating a (left) invertible k × l matrix
Let k > l. To generate a (left) invertible k × l matrix, one can first
generate an invertible square k × k matrix and then remove k − lcolumns, selected at random.
To generate an invertible square k × k matrix, one can do the following.
1
Generate an upper unitriangular k × k matrix U as a product ofelementary matrices Eij (u). A matrix Eij (u) has 1s on the diagonal
and 0s elsewhere, except that it has a polynomial u = u(x1 , . . . , xn )in the (i, j)th place, where j > i.
2
Thus, for every pair of integers (i, j) with 1 ≤ i < j ≤ k, select arandom t-sparse polynomial u = uij and make an elementary matrix
Eij (u).
3
Finally, an upper unitriangular k × k matrix U is computed as a2
product of k 2−k elementary matrices selected that way.

9 / 27

Generating a (left) invertible k × l matrix
Let k > l. To generate a (left) invertible k × l matrix, one can first
generate an invertible square k × k matrix and then remove k − lcolumns, selected at random.
To generate an invertible square k × k matrix, one can do the following.
1
Generate an upper unitriangular k × k matrix U as a product ofelementary matrices Eij (u). A matrix Eij (u) has 1s on the diagonal
and 0s elsewhere, except that it has a polynomial u = u(x1 , . . . , xn )in the (i, j)th place, where j > i.
2
Thus, for every pair of integers (i, j) with 1 ≤ i < j ≤ k, select arandom t-sparse polynomial u = uij and make an elementary matrix
Eij (u).
3
Finally, an upper unitriangular k × k matrix U is computed as a2
product of k 2−k elementary matrices selected that way.
4
A lower unitriangular k × k matrix K is built a similar way, exceptthat in the elementary matrices Eij (u), one should have
1 ≤ j < i ≤ k.

10 / 27

Generating a (left) invertible k × l matrix
Let k > l. To generate a (left) invertible k × l matrix, one can firstgenerate an invertible square k × k matrix and then remove k − lcolumns, selected at random.
To generate an invertible square k × k matrix, one can do the following.
1
Generate an upper unitriangular k × k matrix U as a product ofelementary matrices Eij (u). A matrix Eij (u) has 1s on the diagonal
and 0s elsewhere, except that it has a polynomial u = u(x1 , . . . , xn )in the (i, j)th place, where j > i.
2Thus, for every pair of integers (i, j) with 1 ≤ i < j ≤ k, select arandom t-sparse polynomial u = uij and make an elementary matrix
Eij (u).
3Finally, an upper unitriangular k × k matrix U is computed as a2
product of k 2−k elementary matrices selected that way.
4
A lower unitriangular k × k matrix K is built a similar way, exceptthat in the elementary matrices Eij (u), one should have
1 ≤ j < i ≤ k.
5
An invertible k × k square matrix S is now computed as a product
UP1 KP2 , where Pi are matrices corresponding to random
permutations of columns and rows of a k × k matrix. (Entries of Pi
11 / 27

Computing the (left) inverse of a matrix

Having generated an invertible k × k square matrix S = UP1 KP2 , wecompute its inverse as S −1 = P2−1 K −1 P1−1 U −1 . Computing Pi−1 istrivial, and computing the inverse of a unitriangular square matrix U orK is done by computing the product of inverses of the elementary
matrices Eij (u), in the reverse order. Note that the inverse of Eij (u) isjust Eij (−u).

12 / 27

Computing the (left) inverse of a matrix

Having generated an invertible k × k square matrix S = UP1 KP2 , wecompute its inverse as S −1 = P2−1 K −1 P1−1 U −1 . Computing Pi−1 istrivial, and computing the inverse of a unitriangular square matrix U or
K is done by computing the product of inverses of the elementary
matrices Eij (u), in the reverse order. Note that the inverse of Eij (u) isjust Eij (−u).

Now suppose the (left) invertible k × l matrix M was obtained from thesquare k × k matrix S by removing k − l columns Ci1 , . . . , Cik−l . Then, toget a left inverse of M, we just remove the corresponding rows
Ri1 , . . . , Rik−l from S −1 .

13 / 27

Suggested parameters
For the hash function H, we suggest SHA-512.

For the integer q in Zq , we suggest q = 6.

For the number n of variables, we suggest n = 64.

For the dimensions of the matrix M, we suggest k = 10, l = 5.

For the number t of monomials in t-sparse polynomials that entries of
the unitriangular matrices, we suggest t = 3.

14 / 27

What is the hard problem here?
The (computationally) hard problem that we employ in our construction
is finding a left inverse of a given left invertible matrix M. That is,solving the matrix equation XM = I , where X is the unknown matrix ofgiven dimensions.

15 / 27

What is the hard problem here?
The (computationally) hard problem that we employ in our construction
is finding a left inverse of a given left invertible matrix M. That is,solving the matrix equation XM = I , where X is the unknown matrix ofgiven dimensions.

If matrices in this equation were considered over a field, then this matrix
equation would translate to a system of linear equations (in the entries ofthe matrix X ), and therefore would be easily solvable.

16 / 27

What is the hard problem here?
The (computationally) hard problem that we employ in our construction
is finding a left inverse of a given left invertible matrix M. That is,solving the matrix equation XM = I , where X is the unknown matrix ofgiven dimensions.

If matrices in this equation were considered over a field, then this matrix
equation would translate to a system of linear equations (in the entries ofthe matrix X ), and therefore would be easily solvable.

In our situation, where matrices are considered over a polynomial algebra,
the problem can still be reduced to a system of linear equations, this timein the coefficients of polynomials that are entries of the matrix X . If thenumber n of variables xi is not too small (we suggest n = 64), then thenumber of different monomials (and therefore the number of unknown
coefficients of polynomials) is quite large, so that the relevant system of
linear equations becomes intractable.
17 / 27

Completing a left invertible matrix to an invertible squarematrix
Another possible way to find a left inverse of a given left invertible matrix
M is to complete M to an invertible square matrix by adding morecolumns, and then find the inverse of this square matrix (which isrelatively easy since one can use determinants).

18 / 27

Completing a left invertible matrix to an invertible squarematrix
Another possible way to find a left inverse of a given left invertible matrix
M is to complete M to an invertible square matrix by adding morecolumns, and then find the inverse of this square matrix (which isrelatively easy since one can use determinants).
Perhaps surprisingly, it was a major open problem (Serre’s problem) inalgebra whether or not any left invertible matrix over a polynomial
algebra can be completed to an invertible square matrix by adding morerows (or columns). This problem was answered in the affirmative
independently by Quillen and Suslin.

19 / 27

Completing a left invertible matrix to an invertible squarematrix
Another possible way to find a left inverse of a given left invertible matrix
M is to complete M to an invertible square matrix by adding morecolumns, and then find the inverse of this square matrix (which isrelatively easy since one can use determinants).
Perhaps surprisingly, it was a major open problem (Serre’s problem) inalgebra whether or not any left invertible matrix over a polynomial
algebra can be completed to an invertible square matrix by adding morerows (or columns). This problem was answered in the affirmative
independently by Quillen and Suslin.
The question that matters to us though is that of the computational
complexity of completing M to an invertible square matrix. It was shownin [H. Lombardi, I. Yengui, Suslin’s algorithms for reduction ofunimodular rows, J. Symbolic Comput. 39 (2005), 707–717] that there isa relevant algorithm whose complexity is exponential in the square of thenumber of variables xi . This is yet another reason why the number ofvariables should not be too small.
20 / 27

Performance and signature size

For our computer simulations, we used Apple MacBook Pro, M1 CPU (8Cores), 16 GB RAM computer.

With the suggested parameters, signature verification takes about 0.2 sec
on average, which is not bad, but the signature is rather large, about
4,200 bytes on average.

21 / 27

Performance and signature size

For our computer simulations, we used Apple MacBook Pro, M1 CPU (8Cores), 16 GB RAM computer.

With the suggested parameters, signature verification takes about 0.2 secon average, which is not bad, but the signature is rather large, about
4,200 bytes on average.

The size of the private key (the matrix L) is about 2,000 bytes, and so is
the size of the public key (the matrix M).

22 / 27

Public key encryption
Our digital signature scheme can be easily converted to a public key
encryption scheme, as follows.

23 / 27

Public key encryption
Our digital signature scheme can be easily converted to a public key
encryption scheme, as follows.
Private: k × l left invertible matrix M, with k > l, whose entries aresparse polynomials from the algebra K .
Public: l × k right invertible matrix L over K , such that LM is the l × l
identity matrix.

24 / 27

Public key encryption
Our digital signature scheme can be easily converted to a public key
encryption scheme, as follows.
Private: k × l left invertible matrix M, with k > l, whose entries aresparse polynomials from the algebra K .
Public: l × k right invertible matrix L over K , such that LM is the l × l
identity matrix.
Encrypting a message m:
1Convert m to a vector U = (P1 , . . . , Pl ) of l (sparse) polynomials.

2

Multiply the vector U by the (public) matrix L on the right to get avector V = (Q1 , . . . , Qk ) of k polynomials from K . This vector V isthe encryption of m.

25 / 27

Decryption

Multiply the vector V = UL by the private matrix M on the right to get
VM = ULM = U.

26 / 27

Thank you

27 / 27