Representations of polynomials a, s, t, e—1 and e—2 can be provided. Values of coefficients of the polynomials can be limited, and can be computed using randomization techniques. A verification key can be generated to include representations of polynomials a, b, and c. Computation of b can include computing a product using a and s, and adding e—1. Computation of c can include computing a product using a and t, and adding e—2. A signing key can represent s and t. The signing key can be used to produce a message signature that can represent a sum of t and a product of s and m, with m being derived from a message to be signed. The verification key can be used to verify the signature by checking coefficient sizes of a polynomial represented by the signature, and of a checking polynomial derived from the verification key and the signature.