Digital signature and authentication method and apparatus

A method for signing and verifying a digital document D, comprising the steps of:

• selecting a hash function;
• selecting an integer q;
• generating polynomials f and g;
• determining the inverse f−1, where
• f−1*f=1(mod q);
• producing a public key that includes h, where
• h=f−1*g(mod q);
• producing a private key that includes f and g;
• producing a message digest m by applying the hash function to the digital document D;
• producing a digital signature s by digitally signing the message digest m using the private key;
• verifying the digital signature on the digital document D by verifying one or more specified conditions using the hash function, the public key h, the digital signature s, and the integer q.

A method for authenticating, by a second user, the identity of a first user, that includes a challenge communication from the second user to the first user, a response communication from the first user to the second user, and a verification by the second user, comprising the steps of:

• 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;
• generating a public key that includes h, where h is equal to a product that can be derived using g and f−1;
• generating a private key from which f and g can be derived;
• generating a challenge communication C by the second user;
• generating a challenge digest m by applying the hash function to the challenge communication C;
• generating a response communication s by digitally signing the message digest m using the private key;
• verifying the response communication s by verifying one or more specified conditions using the hash function, the response communication s, challenge communication C and the public key.

A method for authenticating, by a second user, the identity of a first user, that includes a challenge communication from the second user to the first user, a response communication from the first user to the second user, and a verification by the second user, comprising the steps of:

• selecting a hash function;
• selecting an integer q;
• generating polynomials f and g;
• determining the inverse f−1, where
• f−1*f=1(mod q);
• producing a public key that includes h, where
• h=f−1*g(mod q);
• producing a private key that includes f and g;
• generating a challenge communication by the second user that includes selection of a challenge C in the ring R;
• generating a response communication by the first user that includes computation of a response s in the ring R, wherein s is derived using f and a challenge digest m derived by applying the hash function to the challenge C;
• and
• performing a verification by the second user that includes verifying one or more specified conditions using the challenge C, the hash function, the public key h, the response s, and the integer q.