Which new RSA-signatures can be computed from certain given RSA- signatures! (Q1184507)

Many cryptographic protocols use signature schemes as building blocks in which one party, called the signature authority, can create signatures, and issues them to other parties, called the individuals. Such protocols are proposed, e.g. in electronic payment systems [cf. \textit{D. Chaum}, \textit{H. den Boer}, \textit{E. van Heyst}, \textit{S. Mjølsnes} and \textit{A. Steenbeek}, Efficient offline electronic checks, Lect. Notes Comput. Sci. 434, 294-301 (1989)]. In such systems a signature represents money. Suppose a signature authority issues RSA-signatures of certain types to an individual, and the individual tries, by using the signatures it received, to compute an RSA-signature of a type not issued by the authority. The aim of the present paper is to investigate whether the individual is able to misbehave in this way. It is shown that computing an RSA-signature of a particular type from given RSA-signatures of other types is polynomial time reducible to computing RSA-roots \(x^{1/d}\pmod N\) for random \(x\) and some positive integer \(d\). (Observe that for every integer \(b\) coprime to \(\varphi(N)\), the congruence \(y^ b\equiv x \pmod N\) has a unique solution (mod \(N\)) which is denoted by \(x^{1/b}\). If \(b>1\), \(x^{1/b}\) is called an RSA- root mod \(N\).) This reduction extends results of \textit{Akl} and \textit{Taylor} [ACM Trans. Comput. Syst. 1, 239-248 (1983)] and \textit{Shamir} [ACM Trans. Comput. Syst. 1, 38-44 (1983)]. As an application of the result, and under the assumption that for the individual it is infeasible to compute RSA-roots, necessary and sufficient conditions are given whether it is feasible for that individual to compute RSA-signatures of a specific type from signatures of other types it may have received before from the authority.