Algebraic infrastructure for cryptographic schemes in lattice settings.
Project description
latticealgebra
This library is a fundamental infrastructure package for building latticebased cryptography.
 Installation:
pip install latticealgebra
 Documentation: https://geometrylabs.github.io/latticealgebra/
Introduction
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 deesigned for building cryptographic schemes in the Ring/Module/Ideal Short Integer Solution setting with with secrets uniformly distributed with respect to the infinitynorm and one_with_const_timenorm; 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.”
Features 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 lattice_algebra
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_with_const_time 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_with_const_time 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.
Contributors
Brandon Goodell (lead author), Mitchell "Isthmus" KrawiecThayer, Rob Cannon.
Built by Geometry Labs with funding from The QRL Foundation.
Running Tests
Use pytest test_lattices.py
. Basic tests cover almost every function, are generally short, and are all correct tests. However, test robustness can be greatly improved. For example, we implement the Number Theoretic transform function ntt
that calls (or uses data from) bit_rev
and make_zeta_and_invs
, among other functions, so we test all three of these with test_ntt
, test_bit_rev
, and test_make_zeta_and_invs
... but in all three of these tests, we only test a single example with small parameters.
Our tests do not have full coverage; we have not mocked any hash functions to test hash2bddpoly
and hash2bddpolyvec
. Interestingly, one_with_const_time can look at our tests as a Rosetta stone for our encoding and decoding of polynomials from binary strings, which is used in our hash functions. A keeneyed reader can compare decode2coef
in main with test_decode2coef
in test_lattices.py
, for example, to see where the test comes from and how the decoding scheme works. See also test_decode2indices
and test_decode2polycoefs
.
Building Docs
Docs are built with mkdocs. Run the following and navigate to http://127.0.0.1:8000/rsis/ which should update automatically as you write the docs.
pip install r docs/requirements.txt
mkdocs serve
License
This library is released as free and opensource software under the MIT License, see LICENSE file for details.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for lattice_algebra0.1.1py3noneany.whl
Algorithm  Hash digest  

SHA256  6c130761910fbe2b2550c5081b3f03a20a709b8dfeee1ca623cdacb43f184f2e 

MD5  cbbd0d680b4cf9c15e99f8510468c87e 

BLAKE2b256  460dc6e049c1670d7af5dd7de9a5c9806299db1362dcb8638051e0ee5b08e5d6 