set {-b, ..., 0, ...., b} Compute w(x) = a(x)·y1(x) + y2(x) Map w(x) into a bit string ω Compute c(x) = POLYHASH(ω | m) (This is a polynomial with k non-zero coefficients. The "|" denotes concatenation of strings) Compute z1(x) = s(x)·c(x) + y1(x) Compute z2(x) = e(x)·c(x) + y2(x) Until the infinity norms of z1(x) and z2(x) ≤ β = (B - k) go to step 1. (This is the rejection sampling step noted above) The signature is the triple of polynomials c(x), z1(x) and z2(x) Transmit the message along with c(x), z1(x) and z2(x) to the verifier. Signature Verification Following GLYPH, to verify a message m expressed as a bit string, the verifying entity must possess the signer's public key (t(x)), the signature (c(x), z1(x), z2(x)), and the message m. The verifier does the following: Verify that the infinity norms of z1(x) and z2(x) ≤ β , if not reject the signature. Compute w'(x) = a(x)·z1(x) + z2(x) - t(x)c(x) Map w'(x) into a bit string ω' Compute c'(x) = POLYHASH(ω' | m) If c'(x) ≠ c(x) reject the signature, otherwise accept the signature as valid. Notice that: a(x)·z1(x) + z2(x) - t(x)c(x) = a(x)·[s(x)·c(x) + y1(x)] + z2(x) - [a(x)·s(x) + e(x)]c(x) a(x)·y1(x) + z2(x) - e(x)·c(x) a(x)y1(x) + e(x)·c(x) + y2(x) - e(x)·c(x) a(x)y1(x) + y2(x) = w(x) (as defined above) This brief derivation demonstrates that the verification process will have c'(x) = c(x) if the signature was not tampered with. Further developments The GLYPH signature scheme described in this document closely follows the work of Lyubashevsky, Gunesyu and Popplemen from 2011 and 2012. There are a number of other variations to their work. These include: Work by Bai and Galbraith on short signatures documented here. Work by Akleylek, Bindel, Buchmann, Kramer and Marson on security proofs for the signature with fewer security assumptions and documented here. Another approach to signatures based on lattices over Rings is a variant of the patented NTRU family of lattice based cryptography. The primary example of this approach is a signature known as the Bimodal Lattice Signature Scheme (BLISS). It was developed by Ducas, Durmas, Lepoint and Lyubashevsky and documented in their paper "Lattice Signatures and Bimodal Gaussians." See BLISS signature scheme References Post-quantum cryptography Lattice-based cryptography