Abstract
In this paper we describe simple identification and signature schemes which
enable any user to prove his identity and the authenticity of his messages to
any other user without shared or public keys. The schemes are provably secure
against any known or chosen message attack if factoring is difficult, and
typical implementations require only 1 to 4 of the number of modular
multiplications required by RSA scheme. Due to their simplicity, security and
speed, these schemes are ideally suited for microprocessor-bases devices such
as smart cards, personal computers, and remote control systems.
