Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!nike!ucbcad!ucbvax!wisdom.BITNET!mike
From: mike@wisdom.BITNET (Mike Trachtman)
Newsgroups: net.crypt
Subject: Efficient identification and signature schemes
Message-ID: <8607201331.AA27476@ucbvax.Berkeley.EDU>
Date: Sun, 20-Jul-86 09:31:59 EDT
Article-I.D.: ucbvax.8607201331.AA27476
Posted: Sun Jul 20 09:31:59 1986
Date-Received: Mon, 21-Jul-86 04:48:21 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: University of California at Berkeley
Lines: 33


  Identification and signature schemes have many commercial and military
applications. The main problem is to enable anyone to verify proofs of
identity without telling him how to generate such proofs by himself
(so he will not be able to misrepresent himself or forge new signatures
later). The RSA public key scheme (developed in 1977 at MIT by Rivest,
Shamir and adleman) provides a possible solution to this problem,
but for many applications its complexity is prohibitive: it requires about 750
modular multiplications of 500 bit numbers, and its software implementations
are quite slow.
  A new paper which has just been published by Fiat and Shamir
from the Weizmann Institute provides a novel solution to this problem.
It describes exceptionally simple identification and signature schemes
which require only 1% to 4% of the number of modular multiplications required
by the RSA scheme. The new schemes require no shared or public keys, can
easily scale up to nation-wide networks, and are provably secure against
any known or chosen message attack if factoring large numbers is difficult.
  The new schemes are particularly well suited to microprocessor-based
applications since they can be implemented in software in a fraction of
a second.  Combined with the emerging technology of smart cards, they
can lead to a new generation of unforgeable ID cards (passports, driver's
licenses, credit cards, access control cards, etc). Other applications
include remote control systems (with verifiable commands), secure operating
systems (with hacker-proof logon procedures), data bases (with an unforgeable
audit trail for any access), and telecomunication devices (to prevent
spoofing).
  Copies of the paper "How to Prove Yourself: Practical solutions to
Identification and Signature Problems" by Fiat and Shamir can be obtained
by writing to the secretary of the Applied Mathematics Dept of the Weizmann
Institute of Science, Rehovot 76100, Israel.


mike