One-Time Identification with Low Memory

In this paper, a practical cryptosystem based on an authentication tree is described. It is an extension of Ralph Merkle's results. The security of the system depends on assumptions on a one-way function . This cryptosystem allows to make interactive proofs of knowledge using keys only once. Thus, it can be used to prove one's identity or to sign some message. Moreover, we can use it to achieve an electronic cash system. A very efficient implementation can be done on a low-cost smart card. This cryptosystem is thus an alternative to the zero-knowledge algorithms.