RING-BASED SIGNATURE SCHEME

摘要

A method and system for generating and verifying a digital signature of a message is provided. The digital signature includes digital signature polynomials. Two relatively prime ideals p and q of a ring R(102) are selected. A private key and the second ideal q are used to generate a public key. One or more message polynomials are generated based on the message to be signed. The digital signature polynomials are generated (110) using at least one of the message polynomials, at least one of the private key polynomials, and at least one of the ideals p and q, wherein the digital signature polynomials in unreduced form are not multiples of the private key polynomials in the ring R. The signature is then verified (116) by confirming that a deviation between at least one of the messae polynomials and at least one of the digital signature polynomials is less than a predetermined deviation threshold.