An efficient method for finding minimum hash chain of multi-payword chains in micropayment

In recent years, e-commerce grows rapidly and therefore a secure and efficient shopping and payment scheme is an important issue today. The micropayment scheme is safe, easy and quick and can be used in some e-commerce applications such as mobile commerce services or Web-based interactive video services that require the small amounts of money in transaction. In Rivest and Shamir (1997) proposed a micropayment system that use hash function to generate a sequence of paywords for making small amount of purchases. They use the low-cost hash operations to reduce the usage of high-cost public key operations to enhance efficiency. However, in Rivest and Shamir´s scheme, only one single payword chain is generated and used. If users are able to spend distinct values of paywords on shopping, the system would be more efficient in computation and storage cost due to the different denominations of multi-payword chains. In this paper, two using modes of the multi-payword chains are proposed based on new partition problems for finding minimal multi-payword chains in the transaction process such that the hash operations can be reduced.