Patent ID: 9634840
Date: 2017-04-25
CPC Classifications: H04L

Claim:
1. A method for signing and subsequently verifying a digital message, comprising the following steps implemented using at least one processor-based subsystem: selecting parameters that include first and second primes, a ring of polynomials related to said primes, and first and second range-defining integers; deriving private and public keys respectively related to a random polynomial private key of the ring of polynomials, and to evaluations of roots of unity of the random polynomial to obtain a public key set of integers; storing the private key and publishing the public key; signing the digital message by: (A) generating a noise polynomial, (B) deriving a candidate signature by obtaining a hash of the digital message and the public key evaluated at the noise polynomial, and determining the candidate signature using the private key, a polynomial derived from the hash, and the noise polynomial, (C) determining whether the coefficients of the candidate signature are in a predetermined range dependent on said first and second range-defining integers, and (D) repeating steps (A) through (C) until the criterion of step (C) is satisfied, and outputting the resultant candidate signature in electronic form as an encoded signed message; and performing a verification procedure utilizing the encoded signed message and the public key to determine whether the encoded signed message is valid and outputting, in electronic form, an indication of validity or invalidity.