The problem of computing roots of a polynomial over the ring Z_n is equivalent to factoring n. Starting from this intractable problem we construct a public key encryption scheme where the message blocks are encrypted as roots of a polynomial over Z_n and a signature scheme where the signature belonging to a message is a (set of) root (s) of a polynomial having the message blocks as coefficients. These schemes can be considered as extensions of Rabin's encryption and signature scheme. However, our signature scheme has some new properties: a short signature can be generated for a long message without using a hash function, and the security features of the scheme can be chosen either to be similar to those of the RSA shceme or to be equivalent to those of Rabin's scheme.
展开▼
