Z rather than Zq . The signature algorithm will create random polynomials which are small with respect to a particular infinity norm bound. This is easily done by randomly generating all of the coefficients of the polynomial (a0, ..., an-1) in a manner which is guaranteed or very likely to be less than or equal to this bound. In the literature on Ring Learning with Errors, there are two common ways to do this: Using Uniform Sampling - The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let b be an integer that is much less than q. If we randomly choose polynomial coefficients from the set: { -b, -b+1, -b+2. ... -2, -1, 0, 1, 2, ... , b-2, b-1, b} the infinity norm of the polynomial will be ≤ (b). Using Discrete Gaussian Sampling - For an odd integer q, the coefficients are randomly chosen by sampling from the set { -(q-1)/2 to (q-1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter σ. The references provide more details on this method. In the RLWE signature GLYPH used as an example below, coefficients for the "small" polynomials will use the uniform sampling method and the value b will be much smaller than the value q. Hashing to a "small" polynomial Most RLWE signature algorithms also require the ability to cryptographically hash arbitrary bit strings into small polynomials according to some distribution. The example below uses a hash function, POLYHASH(ω), which accepts a bit string, ω, as input and outputs a polynomial with n coefficients such that exactly k of these coefficients have absolute value greater than zero and less than an integer bound b (see above). Rejection sampling A key feature of RLWE signature algorithms is the use of a technique known as rejection sampling. In this technique, if the infinity norm of a signature polynomial exceeds a fixed bound, β, that polynomial will be discarded and the signing process will begin again. This process will be repeated until the infinity norm of the signature polynomial is less than or equal to the bound. Rejection sampling ensures that the output signature is not exploitably correlated with the signer's secret key values. In the example which follows, the bound, β, will be (b - k), where b is the range of the uniform sampling described above and k will