be the number of non-zero coefficients allowed in an "accepted" polynomial Other parameters Following GLYPH and as noted above, the maximum degree of the polynomials will be n-1 and therefore have n coefficients. Typical values for n are 512, and 1024. The coefficients of these polynomials will be from the field Fq where q is an odd prime congruent to 1 mod 4. For n=1024, GLYPH sets q = 59393, b=16383 and k the number of non-zero coefficients in the output of Polyhash equal to 16. The number of non-zero coefficients k produced by the hash function is equal to 32 for both cases. The security of the signature scheme is closely tied to the relative sizes of n, q, b, and k. Details on setting these parameters can be found in references 5 and 6 below. As noted above, the polynomial Φ(x) which defines the ring of polynomials used will be xn + 1. Finally, a(x) will be a randomly chosen and fixed polynomial with coefficients from the set { -(q-1)/2 to (q-1)/2 }. The polynomial a(x) should be chosen in a "Nothing Up My Sleeve" manner such as one-way hashing the output of a true noise random number generator (TRNG) or using the digital expansion of well known mathematical constans such as pi or e. All signers and verifiers of signatures will know n, q, b, k, Φ(x), a(x) and β = b-k. Public key generation An entity wishing to sign messages generates its public key through the following steps: Generate two small polynomials s(x) and e(x) with coefficients chosen uniformly from the set {-b,...-1, 0, 1, ..., b} Compute t(x) = a(x)·s(x) + e(x) Distribute t(x) as the entity's public key The polynomials s(x) and e(x) serve as the private key and t(x) is the corresponding public key. The security of this signature scheme is based on the following problem. Given a polynomial t(x) find small polynomials f1(x) and f2(x) such that: a(x)·f1(x) + f2(x) = t(x) If this problem is difficult to solve, then the signature scheme will be difficult to forge. [See the Wikipedia article on Ring Learning with Errors or Ideal Lattice Cryptography for more details on the theoretical difficulty of this problem] Signature generation Following GLYPH, to sign a message m expressed as a bit string, the signing entity does the following: Generate two small polynomials y1(x) and y2(x) with coefficients from the