This letter gives a study of additionY=X+K mod 2w which is used in some cryptosystems as RC5. Our results enables us to express the differential and linear probability of addition as a function of addendK. To detect a good differential characteristics or linear approximation of a cryptosystem in which extended key is used as addend, we need to consider how the characteristics or approximations behave depending upon the value of the addend, which are clarified by our results.

In Asiacrypt '96, Bleichenbacher et al. showed the upper limit of the efficiency of one-time digital signature scheme using a directed graph of tree structure as its base. They also claimed that there exists more effective signature scheme on general directed graphs, and showed an example of a method to construct more effective signature schemes as a witness. Unfortunately, their example does not achieve the efficiency as they claimed. This paper shows the upper limit of the efficiency of the signature scheme on general directed graphs by showing no signature scheme is more effective than the optimal signature scheme on trees (or forests). Further, we introduce another signature scheme named pseudo k-time signature scheme. This signature scheme allows signers to sign k-time which is no less efficient than the one time signature scheme.