Path: utzoo!utgpu!water!watmath!clyde!rutgers!cmcl2!husc6!mailrus!umix!uunet!mcvax!prlb2!quisquat
From: quisquat@prlb2.UUCP (Jac. Quisquater)
Newsgroups: news.admin
Subject: Re: Bizarre authentication scheme
Keywords: 10371664694678927135158569960683451164025292213568271978668183
Message-ID: <425@prlb2.UUCP>
Date: 19 Feb 88 17:44:38 GMT
References: <8802080327.AA02920@jiff>
Reply-To: quisquat@prlb2.UUCP (Jean-Jac. Quisquater)
Organization: Philips Research Laboratory, Brussels
Lines: 32

In article <8802080327.AA02920@jiff> gsmith@brahms.BERKELEY.EDU () writes:
>
> If anyone feels strongly enough about protection against
>forgeries, one system which does not involve any fixes by anyone
>but the user himself is to post a large number which is the
>product of two large enough (say, ~10^30) primes or pseudoprimes.
>In any subsequent article you wish to authenticate, you give a
>pointer to the previous article and the factorization. Then you
>supply a new composite number.
>

Incorrect. 

(1) Your number (1037...183) must be really related to the message you
send. Otherwise, If I copy the header of your article using some forgery, 
your scheme permits also to authenticate my message. That is, you need a true 
signature scheme with shadow or imprint.

(2) I can also forge any message including a large number. In any subsequent
article I give a pointer to this article and the factorization. The only
thing you can prove is: ``Somebody knows the factorization: nothing else!''.

In other words, it is very difficult (impossible?) to imagine an (off-line)
identification scheme without any authority. You need this authority to 
initialize the scheme, not to run the system. (see the works of Shamir, 
Desmedt, Guillou and Quisquater for the identity-based cryptosystems, and 
the works of Goldreich, Goldwasser, Micali, Rackoff, Brassard, Chaum, Crepeau,
Fiat, Shamir, Feige, Desmedt, Guillou, Quisquater ... for the zero-knowledge 
-- minimum disclosure -- protocols).

Jean-Jacques Quisquater,