Cryptography

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 one-way function. If no additional information is leaked about a small secret vector (such as how long it takes to perform arithmetic operations), then this can be used to build secure cryptographic schemes.

Simulation-based 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. The infinity-norm and the one-norm are of particular interest: the infinity-norm of a polynomial is the absolute maximum coefficient, and the one-norm 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 non-zero 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 one-norm. Taking into account both the infinity norm and the weight of the polynomial (number of non-zero entries) enables tighter inequalities that lead to smaller witnesses. This means we can achieve the same security level with smaller parameters (the CRYSTALS-Dilithium scheme is an exemplary implementation of this technique).

Nothing in lattice-algebra 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.