Digitalized Signatures and Public-Key Functions as Intractable as Factorization

摘要

We introduce a new class of public-key functions involving a number n = p.q having two large prime factors. As usual, the key n is public, while p and q are the private key used by the issuer for production of signatures and function inversion. These functions can be used for all the applications involving public-key functions, including digitalized signatures. We prove that for any given n, if we can invert the function y = E sub n(x) for even a small percentage of the values y then we can factor n. Thus as long as factorization of large numbers remains practically intractable, for appropriately chosen keys not even a small percentage of signatures are forgerable. Breaking the RSA function is at most as hard as factorization, but is not known to be equivalent to factorization even in the weak sense that ability to invert all function values entails ability to factor the key. Computation time for these functions, i.e., signature verification, is several hundred times faster than for the RSA scheme. Inversion time, using the private key, is comparable. The almost-everywhere intractability of signature-forgery for our functions (on the assumption that factoring is intractable) is of great practical significance and seems to be the first proved result of this kind.