Patent ID: 7308097

Claim:
A method for signing and verifying a digital document D, comprising the following steps implemented using at least one processor-based subsystem: selecting a ring R, an ideal q of R, and a hash function; generating elements f and g of the ring R, and generating an element f −1 that is an inverse of f in the ring R modulo q; producing a public key that includes h, where h is equal to a product that can be derived using g and f −1 ; producing a private key from which f and g can be derived; producing additional elements F and G in R derived from the private key, wherein the element E=f*G−g*F is in the ideal q, and wherein the quotient q/(E) is a small finite set; producing a message digest m by applying the hash function to the digital document D; producing a digital signature s by producing elements B and b in R that are derived from the elements f, g, F, G and from the message digest m, the digital signature s being derived by the formula f*B−F*b (mod g); and verifying the digital signature s by verifying one or more specified conditions using the digital document D and the public key.