Patent ID: 8677135

Claim:
A computer-implemented method, comprising: providing representations of a public verification key polynomial a, signing key polynomials s and t, and verification key error polynomials e_ 1 and e_ 2 , providing the representations comprising: limiting values of coefficients of each of the polynomials a, s, t, e_ 1 , and e_ 2 ; and computing the polynomials s, t, e_ 1 , and e_ 2 using a randomization technique comprising one or more randomization operations; generating a signing key comprising a representation of the polynomial s and a representation of the polynomial t; and a key generation computer system generating a verification key comprising a representation of the polynomial a, a representation of a polynomial b, and a representation of a polynomial c, the generation of the verification key comprising: computing the polynomial b, the computation of the polynomial b comprising computing a product using the polynomial a and the polynomial s, and adding the polynomial e_ 1 ; and computing the polynomial c, the computation of the polynomial c comprising computing a product using the polynomial a and the polynomial t, and adding the polynomial e_ 2 .