Introducing latticealgebra: An elegant, highperformance postquantum cryptography library
technical research proofofstake
18th February 2022
We are excited to announce the public release of our python implementation of some of the algebra underlying latticebased postquantum cryptography. In partnership with The QRL Foundation and created by Geometry Labs, the code is now available as free and open source software published on GitHub and distributed through PyPi (install with: pip install latticealgebra
). This library will be used to prototype a variety of new features for the QRL protocol, such as latticebased proofofstake signatures, trustless crosschain atomic swaps (QRL↔BTC, QRL↔ETH, etc), and ‘lightning network’ style payment channels.
Sharing the building blocks
The mathematical objects and calculations handled by this package are foundational for lattice algebra, with a variety of applications ranging from signature aggregation to zeroknowledge proofs. The module highly prioritizes developer experience for researchers and engineers, by allowing them to work with a few high level objects (e.g. polynomials, polynomial vectors) that contain builtin methods to abstractly handle the ways that they interact with each other. The goal is to lower the barrier for creating lattice cryptography primitives and applications by allowing the developers to focus on securely building the higherlevel constructs without having to worry about implementing the underlying algebra as well.
The module is specifically designed for building cryptographic schemes in the Ring/Module/Ideal Short Integer Solution setting with secrets uniformly distributed with respect to the infinitynorm and onenorm; it can also be used to implement schemes in the Ring/Module/Ideal Learning With Errors setting. The library’s lead author Brandon Goodell explained how the high level objects are efficiently implemented under the hood, “to manipulate equations of polynomials, we carry out the computations with vectors and matrices, with highly optimized algebraic operations.”
In this article series, we’ll show how the latticealgebra
library can be used to implement a Schnorrlike onetime signature scheme, an extension for noninteractive aggregatable onetime signatures, and adaptor signature functionality. Possible future applications include zeroknowledge arguments of knowledge, mofn multisig wallets with aggregatable signatures, and a python implementation of the NIST competitor CRYSTALSDilithium signature scheme.
Mathematical background
In many latticebased cryptographic schemes, primitives are constructed from polynomials in the ring R = Zq[X]/(X^d + 1)
where we denote the integers modulo a prime q
with Zq
, with a degreed
that is a power of two such that (q1) % (2*d) = 0
. Keys are often vectors from the vector space V=R^l
or matrices with entries from V = R^(k * l)
for dimensions k
, l
. For example, the CRYSTALSDilithium scheme sets q = 2^23  2^13 + 1
, d = 256
, and uses 4x4
, 6x5
, and 8x7
matrices, depending on security level.
For certain choices of d
, q
, and l
, it is thought to be hard to find any vector (or matrix) x
that is small enough (in terms of one or more norms on the ring R
) such that some matrix equation A * x = 0
is satisfied, where A
is a suitably random challenge from V
. From this hardness assumption, the map carrying suitably small vectors (or matrices) x
to their images A * x
is a oneway function. Simulationbased security proofs in the lattice setting are based on extracting a suitably small vector or matrix (called a witness) that satisfies some system of linear equations. Overall security of the scheme is based on how small the adversary can make this witness in terms of the norm of the witness.
The infinitynorm and the onenorm are of particular interest: the infinitynorm of a polynomial is the absolute maximum coefficient, and the onenorm is the absolute sum of coefficients. We can extend this definition to vectors by taking the maximum norm of the entries of the vector. We note that if we count only the weight of a polynomial, in terms of the number of nonzero coefficients, then we have that one_norm <= infinity_norm * weight
. Consequently, bounding the infinity norm and the weight of a polynomial also has the effect of bounding the infinity norm and the onenorm. Taking into account both the infinity norm and the weight of the polynomial (number of nonzero entries) enables tighter inequalities that lead to smaller witnesses. This means we can achieve the same security level with smaller parameters (the CRYSTALSDilithium scheme is an exemplary implementation of this technique).
Nothing in latticealgebra
limits which hardness assumptions are underlying the cryptographic scheme being constructed. Since the library merely handles polynomials from R
and vectors from V=R^l
, schemes based on other hardness assumptions (such as the Ring Learning With Errors assumption) that take place over the same ring can be securely implemented as well.
Designed for cryptography developers
The library is designed to make it easy for developers to write clean code that securely implements latticebased cryptography for protocols and applications. The package is optimized to use the Number Theoretic Transform (NTT) to multiply polynomials in time O(2dlog(2d))
, and uses constanttime modular arithmetic to avoid timing attacks. For convenience, we included tools for both hashing to and sampling from these “suitably small” polynomials and vectors. Both the hashing and sampling are carried out such that the bias of the resulting distribution is negligibly different from uniform.
One way that the latticealgebra
toolkit helps developers write succinct code is by leveraging python’s magic methods for arithmetic with elements from R
and R^l
. For example, suppose we have two polynomials f
and g
. Simple expressions such as f + g
, f  g
, and f * g
carry out constanttime polynomial arithmetic such as addition, subtraction, and multiplication (respectively). Likewise if we have two vectors of polynomials x
and y
, several vector arithmetic methods are at our disposal: we can add them like x + y
, or calculate the dot product as x * y
. Additionally, x ** f
scales a vector x
by the polynomial f
, which is useful for constructing digital signatures.
To showcase this style, consider the aggregatable signatures described in Boneh and Kim based on the signatures described by Lyubashevsky and Micciancio. Signing keys sk = (s0, s1)
are pairs of elements sampled uniformly from the subset of R^l
with bounded norm. The signature challenge c
is computed from a hash function H_0
that digests a message m
and outputs an element in R
with bounded norm.
Here is how the process is described in the Boneh and Kim write up:
With proper parameters and key structure, we can implement a functioning “arithmeticy” version of sign
simply by transcribing the above blue boxes:


The ability to write such minimalist code limits the room for implementation errors and allows cryptography developers (and their code reviewers) to focus on the application or protocol itself.
Future work
Future work on the latticealgebra
package includes nonuniform key sampling, expanded linear algebra, and additional benchmarking tests. We will shortly be publishing articles with free opensource code for several cryptographic applications, including aggregatable signatures and adaptor signatures (which will be used to prototype the logic enabling crosschain atomic swaps and ‘lightning network’ style payment channels for the QRL protocol).
Library Contributors
Brandon Goodell (lead author), Mitchell P. KrawiecThayer, Rob Cannon
Correspondence: info@geometrylabs.io
This article is part of the Techniques for efficient post quantum finance series.
 Introducing latticealgebra: An elegant, highperformance postquantum cryptography library
 Techniques for efficient postquantum finance (Part 1: digital signatures)
 Techniques for efficient postquantum finance (Part 2: signature aggregation)
 Techniques for efficient postquantum finance (Part 3: adaptor signatures)
Proof of Stake technical research
18th February 2022