Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57
schnorr (schnorr@research.bell-labs.com)
Mon, 10 Aug 1998 11:53:50 -0400
RE: Coverage of the DSA by EP-Patent 0384475 of May 1998, see
http://grouper.ieee.org/groups/1363/letters/SchnorrMar98Study.ps
Here comes a replay to emails received until August 4.
The DSS is a ZERO-INVENTION designed to.......
The discussion on the coverage of the DSS by the Schnorr patents
misses a crucial point:
The Schnorr signature algorithm had already been adopted by internal
committees of the NSA/NIST as the "future signature standard" as it
became
known that this is a patented algorithm. The principal goal of the
DSS design is to steal the core of that invention. The recipe for
such robbery is well known:
1. Take the core of the invention that provides the novel
advantages --- in our case the small groups provide a speed up.
2. Change the embodiment of the invention by changes that are
irrelevant to the core of the invention.
3. Show that the changed embodiment is not covered by the patented
invention for a sufficiently narrow concept of "step equivalence".
The real issue is not to narrow down the concept of "step equivalence"
to
much. Otherwise you cannot prevent stealing inventions by mere
detoriation.
An important question is whether the transformation of Schnorr
signatures
towards the DSS bears any advantage that makes out a true invention or
whether the transform was merely designed to bypass a patent. So
far the NSA/NIST did not claim any advantage for the DSS. Nor has any
advantage been pointed out in the published literature. This indicates
that the principal purpose of this transform is to steal an
invention. If the NSA/NIST really wants the truth to be known they
should lay out the design goals of the DSS. Then we will see the
goals that the DSS meets.
Let us consider the "equivalence" of addition and division in the
signature
formula in more detail. It is true that addition and division induce
different formulas for verification. The verification for division
is due to ElGamal, IEEE-IT, pp. 469 -472, (1985). It uses that the
division distributes with addition: (a + b)/c = a/c + b/c. This
work is cited in my patent. I have great respect for the genuine
contribution of ElGamal. My invention starts from ElGamal signatures
and simplifies both signature generation and verification by replacing
the division by the simpler addition.
Of course you can undo my transformation and go back to division. But
that is not a novel thing. Nobody makes us believe that
nobody understood ElGamal signatures until they were reinvented at
NSA/NIST. It would certainly be interesting to let independent
cryptographic experts judge on the degree of novelty to reintroduce
the division into the signature formula and to go back to ElGamal's
verification formula.
Then what is the novelty in the DSS ? The use of the division and the
corresponding verification formula is prior art due to ElGamal. What
else is
the genuine contribution in the DSS ? --- Nothing: THE DSS IS A
ZERO-INVENTION.
Nobody writes:
" People may differ in their opinions about the degree of novelty in
the
change from addition to modular division. It is not obvious a
priori that
such a change is acceptable. (Perhaps it is obvious to Dr. Schnorr,
one of
the top cryptographers in the world, but the usual test is whether a
typical professional in the field would view the change as obvious).
Certainly it is the case that not every step in the signature
calculation
can freely change between addition and division. Rather, any such
change
must be carefully analyzed, bearing in mind the mathematical
relationships
as well as cryptographic considerations. The verification formula
changes,
and there has to be study as to whether it becomes possible to forge
new
signatures from a collection of old ones."
Then what is the new research that goes beyond ElGamal and makes a
difference between Schnorr signatures and the DSS ? I could find
virtually nothing in the literature that makes a difference merely
between the addition versus division in the signature formula except
that the division complicates everything.
Does the division bring any advantage at all ? It certainly
complicates the generation as well as the verification of
signatures. Does it enhance security ?
There is no such claim neither by NSA/NIST nor in the literature. On
the contrary the division complicates the security analysis in a
similar way as it complicates the generation and verification of
signatures. Therefore we must conclude:
THE DSS IS A ZERO-INVENTION THAT DETORIATES A PRIOR INVENTION.
However, there are studies on other aspects of the transform from
Schnorr signatures to the DSS. They are quite negative for the DSS:
Pointcheval and Stern show [ Proceedings of Eurtocrypt'96, LNCS 1070,
pp. 387-398 ] that Schnorr signatures are provably secure against
chosen message attacks. They also explain why their methods fail to
prove security for the DSS. It is because the DSS deviates from
Schnorr signatures.
Moreover the DSS has weaknesses that are not in Schnorr signatures.
Vaudenay shows in the Proceedings of CRYPTO'95 that the DSS is
vulnerable if the primes in the DSS are not carefully chosen. This
weakness does hold for Schnorr signatures. Again this shows:
THE DSS is a ZERO-INVENTION that DETORIATES a prior invention.
Nobody writes
"If Dr. Schnorr really wanted to claim variants on the arithmetic
formula,
he could have done so within the patent. He already claims many
minor
variations, such as claim 7 which specifies that the bit lengths of
the
various values can be chosen to be less than the bit length of p, a
seemingly obvious consideration given that he has already pointed
out that
they can be chosen mod q where q divides p-1. Given that he has
gone to
some effort to cast a wide net with his patent, it seems reasonable
to
suppose that he would have included those variants on the
mathematical
formula which he was aware of at the time."
Nobody blames me that I did not include possible DETORIATIONS of my
invention into the patent filing. In fact the patent does not cover
any possible DETORIATION whatsoever. On the contrary it only covers
possible IMPROVEMENTS of the invention. It is impossible to cover in a
patent filing all possible ways to detoriate, to complicate and to
worsen an invention.
Let us go over Nobody's minor nit-picks, Nobody writes:
" Schnorr patents a system in which there are certain s_j values used
in
his formulas in a specific way, such that the s_j values are secret,
and not known to the verifier. In order to achieve DSS equivalence
he
must assume that one of the s_j values is publicly known to be the
value
1. This is not a secret value and hence the information
relationships
described in the Schnorr patent do not apply.
Schnorr's patent requires that the hash value be sent as part of the
signature. In order to achieve DSS equivalence he must modify this
so
that only half of the hash is sent as the signature. This departs
from
the claim of his patent."
Nobody is right that the equivalence transformation from Schnorr
signatures to the DSS stretches the design of Schnorr signatures. But
this
is necessary to introduce the weakness of the DSS that are not contained
in Schnorr signatures. Without stretching the design of my signature
scheme the eqivalence transformation would prove that the DSS is as
secure as
Schnorr signatures, which is not provable by known methods. Here,
Nobody tries to narrow down the concept of "step equivalence" so that
mere detoriation of an invention bypasses patent coverage.
Nobody claims that the rejuvenation process described in claims 4 and 5
is practically not important. Recently Venkatesan et alii propose [
Proceedings of Eurocrypt'98, Springer LNCS 1403, pp. 221 -235 ] a
preprocessing scheme that falls in the framework of my claims 4 and 5.
Microsoft is filing a patent on it. The world software leader
disagrees with Nobody.
Nobody writes that my patents are only valid for "smart cards". The word
"smart card" does not appear in the patent filings. The european filing
uses
the broader term "Prozessor-Chip Karte". If signatures are not
computed by processors but calculated by hand my patents do in fact not
apply.
SUMMARY
Nobody pushes to apply a narrow, formal concept of "step equivalence".
This
makes it difficult to cover the detoriated scheme created by the
NSA/NIST by
the Schnorr patents. If that approach gets approved then
STEALING INVENTIONS BY ZERO-INVENTIONS AND MERE DETORIATION
becomes an accepted method. This would be very destructive.
On the contrary, I argue that a broader concept of "step equivalence"
must
be used which includes step transformations that are known to be
equivalent by prior art, in particular when the transformation does
not bear an advantage. For that broader notion I have shown that the
DSS and Schnorr signatures are step by step equivalent. The division
in the signature formula is equivalent to the addition by prior art
due to ElGamal.
Sincerely,
Dr. Claus Peter Schnorr
Universitaet Frankfurt
Fachbereich Mathematik/Informatik
( currently at leave at Bell Labs,
Murray Hill, New Jersey, USA )
>
> -----------------
> Replies to Dr. Schnorr on the Coderpunk List:
> -----------------
>
> Date: Mon, 03 Aug 1998 23:10:00 +0100
> From: Ben Laurie <ben@algroup.co.uk>
> Organization: A.L. Group plc
> MIME-Version: 1.0
> To: schnorr <schnorr@research.bell-labs.com>
> CC: Vin McLellan <vin@shore.net>, jim@rsa.com, burt@rsa.com, ari@rsa.com,
> schnorr@cs.uni-frankfurt.de, timd@consensus.com, CodherPlunks@toad.com,
> 3umoelle@informatik.uni-hamburg.de
> Subject: Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon.
>
> schnorr wrote:
> > The point is that the DSS performs step by step the same or equivalent
> > operations as the Schnorr signature algorithm. The DSS performs the same
> > steps throughout and at one point performs a division instead of an
> > addition. At that point the DSS performs a more complicated but
> > equivalent operation. Most importantly, the DSS does not cancel out a
> > single step of Schnorr signatures. Even the addition step is still
> > there, it is part of the division which contains many additions.
>
> At the risk of repeating Nobody, I have to say that I find this very
> difficult to buy. It seems to me that the logical consequence of this is
> that all equations are essentially the same. If division is really just
> addition in disguise, I'm sure we'll all have no problem at all with the
> following statements:
>
> 1. Multiplication is addition.
> 2. Raising to a power is multiplication (and hence addition).
> 3. Subtraction is addition.
> 4. Taking a log is raising to a power (and hence multiplication, thus
> addition).
>
> So, if I perform the patented operation a+b, I also cover all equations
> using multiplication, subtraction, division, powers and logs.
>
> Proof:
>
> a+b is just a+c+d, so I can add an extra operator without any trouble.
> That operator can become *, /, ^, log or -. And, since I can add an
> infinite number of them, I guess we can include sin, cos, tan, etc.
>
> Hence, any algebraic operation is just a+b in diguise. Q.E.D.
>
> Cheers,
>
> Ben.
>
> --
> Ben Laurie |Phone: +44 (181) 735 0686| Apache Group member
> Freelance Consultant |Fax: +44 (181) 735 0689|http://www.apache.org/
> and Technical Director|Email: ben@algroup.co.uk |
> A.L. Digital Ltd, |Apache-SSL author http://www.apache-ssl.org/
> London, England. |"Apache: TDG" http://www.ora.com/catalog/apache/
>
> WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/
>
> -------------------------------
>
> Date: Tue, 4 Aug 1998 01:51:15 +0200
> From: Anonymous <nobody@replay.com>
> Comments: This message did not originate from the Sender address above.
> It was remailed automatically by anonymizing remailer software.
> Please report problems or inappropriate use to the
> remailer administrator at <abuse@replay.com>.
> Subject: Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon.
> To: CodherPlunks@toad.com
> Sender: owner-CodherPlunks@toad.com
> Precedence: bulk
>
> Dr. Schnorr's argument for coverage of the DSS by his patent is at:
>
> http://grouper.ieee.org/groups/1363/letters/SchnorrMar98Study.ps
>
> His U.S. patent is at
>
> http://www.patents.ibm.com/details?patent_number=4995082
>
> >From here you can read the claims in textual form or look at photographs of
> the patent pages, where the claims are on the last two pages.
>
> As is typical, the patent is structured such that later claims depend
> on earlier ones. Specifically we have, after claim 1:
>
> 2. A method for generating a signature according to the method of
> claim 1, wherein...
>
> 3. A method for generating an abbreviated signature for a message to
> be transmitted in a data exchange system according to the method of
> claim 1, and further comprising steps defined as...
>
> 4. The method of claim 3, and further comprising the steps of...
>
> 5. The method of claim 4, and further defined as comprising...
>
> 6. The method of claim 5, and further defined as...
>
> 7. The method of claim 6, and further defined as...
>
> etc.
>
> Each of these encryption claims builds on earlier ones, all going back to
> claim 1.
>
> Claim 1 starts with:
>
> 1. In a method for mutual identification of subscribers in a data
> exchange system working with processor chip cards and using
> identification data coded into the cards by a card-issuing center
> including subscriber-related public keys and stored in the respective
> chip cards along with private keys which have a logical relationship
> to the public keys, whereby random number-dependent check data are
> exchanged between the subscribers...
>
> It appears that claim 1, and hence all the dependent signature claims, only
> apply to processor chip cards, aka smart cards. None of the signature
> claims attempt to expand coverage to general purpose computers. (The last
> two claims, 10 and 11, relate to signature verification and are not
> conditional on claim 1 and not specific to smart cards, but they may not be
> so easy to transform into something close to the DSS verification.)
>
> The claim which covers using a subgroup of order q such that q divides
> p-1 is claim 6. However note from the above that claim 6 is based on
> claims 1, 3, 4, and 5. Hence it only applies to a system which uses
> features from those earlier claims.
>
> Claims 4 and 5 cover the use of a specific optimization to save the
> chip card the effort of computing exponentiations. Instead the card
> holds a series of r_i values along with g^r_i, all precomputed. It
> uses one of those values and replaces that r_i with a combination of
> the other r_i values (a process Schnorr calls "rejuvenation"). In
> this way the chip card never has to exponentiate.
>
> However, this optimization is usually unnecessary for general purpose
> computers, and is not likely to be widely used in chip cards because there
> is an attack against it by de Rooij published in J. Cryptology, v10 n1,
> Winter, 1997, improving an earlier attack he presented at Eurocrypt 91.
> For the case where 8 r_i values are stored, a parameter suggested
> originally by Schnorr, de Rooij shows how to retrieve the secret key with
> 2^31 steps by examining 700 signatures. So a larger number of r_i values
> would have to be stored, which may begin to cause memory problems on a
> smart card.
>
> An implementation which does not use this rejuvenation optimization is
> not covered by claims 4-5, and hence not by claim 6, the one which covers
> the use of a subgroup. Therefore DSS would not be covered unless it uses
> rejuvenation.
>
> An implementation which is not used on a smart card is not covered by
> any of the signature claims.
>
> The European patent may be different; Dr. Schnorr indicates that it does
> not require that the chain of claims be set up precisely as in the U.S.
> patent.
>
> Dr. Schnorr writes, regarding the fact that DSS divides by k where his
> signature scheme adds k,
>
> > It is correct that I do not turn an addition into a division which is
> > actually more complicated. But that is not necessary. You do not escape
> > patent coverage by simply complicating or repeating some step. If you
> > apply RSA twice and add further scrambling you still use RSA.
> >
> > The point is that the DSS performs step by step the same or equivalent
> > operations as the Schnorr signature algorithm. The DSS performs the same
> > steps throughout and at one point performs a division instead of an
> > addition. At that point the DSS performs a more complicated but
> > equivalent operation. Most importantly, the DSS does not cancel out a
> > single step of Schnorr signatures. Even the addition step is still
> > there, it is part of the division which contains many additions.
>
> It is clearly incorrect to say that because division contains many
> additions, the DSS still infringes the patent. Schnorr's patent does
> not cover just any addition. It covers a specific mathematical formula,
> where k is added to the sum of the hash and x*r. That is the specific
> addition step which must be present in order to infringe the claim.
>
> DSS divides that same sum by k instead of adding. It is not true that this
> division infringes the claim, because it does not involve an addition of k
> to the sum of hash and x*r. In fact, the way modular division is usually
> implemented is that the inverse of k mod q is found using the extended
> Euclidean algorithm, such that k_inv * k = 1 mod q. This k_inv is then
> multiplied by the sum of hash and x*r, mod q. Neither this multiplication
> step nor the Euclidean algorithm involves adding k to the sum of hash and
> x*r at any point. Therefore the Schnorr sequence of operations never
> occurs during the DSS and the claim that the DSS does not cancel any of the
> Schnorr steps is wrong.
>
> Schnorr also argues:
>
> > In summary, DSS signatures perform the same steps as Schnorr signatures
> > for a particular choice of parameters except that one addition is
> > replaced by a division.
> > Replacing an addition by a division is certainly not a novel
> > invention, in particular as the division was already present in the
> > previous ElGamal signatures. This modification is fully covered by lines
> > 65 - 68, page 10, lines 1-5, page 11 of the US filing of my patent:
> > "Although I have described my invention by reference to particular
> > illustrative embodiments thereof, many changes and modifications of the
> > invention may become apparent to those skilled in the art without
> > departing from the spirit and scope of the invention. I therefore intend
> > to include within the patent warranted hereon all such changes and
> > modifications as may reasonably and properly be included within the
> > scope of my contribution of the art."
>
> People may differ in their opinions about the degree of novelty in the
> change from addition to modular division. It is not obvious a priori that
> such a change is acceptable. (Perhaps it is obvious to Dr. Schnorr, one of
> the top cryptographers in the world, but the usual test is whether a
> typical professional in the field would view the change as obvious).
> Certainly it is the case that not every step in the signature calculation
> can freely change between addition and division. Rather, any such change
> must be carefully analyzed, bearing in mind the mathematical relationships
> as well as cryptographic considerations. The verification formula changes,
> and there has to be study as to whether it becomes possible to forge new
> signatures from a collection of old ones.
>
> If Dr. Schnorr really wanted to claim variants on the arithmetic formula,
> he could have done so within the patent. He already claims many minor
> variations, such as claim 7 which specifies that the bit lengths of the
> various values can be chosen to be less than the bit length of p, a
> seemingly obvious consideration given that he has already pointed out that
> they can be chosen mod q where q divides p-1. Given that he has gone to
> some effort to cast a wide net with his patent, it seems reasonable to
> suppose that he would have included those variants on the mathematical
> formula which he was aware of at the time.
>
> Last, a couple of relatively minor nit-picks regarding the claimed
> equivalence:
>
> Schnorr patents a system in which there are certain s_j values used in
> his formulas in a specific way, such that the s_j values are secret,
> and not known to the verifier. In order to achieve DSS equivalence he
> must assume that one of the s_j values is publicly known to be the value
> 1. This is not a secret value and hence the information relationships
> described in the Schnorr patent do not apply.
>
> Schnorr's patent requires that the hash value be sent as part of the
> signature. In order to achieve DSS equivalence he must modify this so
> that only half of the hash is sent as the signature. This departs from
> the claim of his patent.
>
> Dr. Schnorr offers the challenge:
>
> > I offer an award of $ 1.000 ( one thousand USD ) for the first who can
> > recast Schnorr signatures to be quite similar to a previously published
> > scheme of discrete log signatures.
>
> The problem is that his patent is written broadly so that it is not clear
> which of the claims represents "Schnorr signatures". If we look at the
> simplest form as described in claims 1-3, the signatures are about as
> similar to ElGamal signatures as they are to DSS. However if we take
> the signatures as described in claims 6-7, which use subgroups, then that
> is a genuinely novel aspect.
>
> No one is claiming that the patent is invalid or that it covers old ground.
> But by the same token it cannot be taken to cover every signature algorithm
> that uses a subgroup.
>
> -------------------------
>
> Date: Tue, 04 Aug 1998 12:23:25 +0100
> From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
> Organization: Studenten; LRZ; Universitaet Muenchen
> MIME-Version: 1.0
> To: Anonymous <nobody@replay.com>
> CC: CodherPlunks@toad.com
> Subject: Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon.
> Sender: owner-CodherPlunks@toad.com
> Precedence: bulk
>
> Anonymous wrote:
>
> > Schnorr also argues:
> > > previous ElGamal signatures. This modification is fully covered by lines
> > > 65 - 68, page 10, lines 1-5, page 11 of the US filing of my patent:
> > > "Although I have described my invention by reference to particular
> > > illustrative embodiments thereof, many changes and modifications of the
> > > invention may become apparent to those skilled in the art without
> > > departing from the spirit and scope of the invention. I therefore intend
> > > to include within the patent warranted hereon all such changes and
> > > modifications as may reasonably and properly be included within the
> > > scope of my contribution of the art."
> >
> > People may differ in their opinions about the degree of novelty in the
> > change from addition to modular division. It is not obvious a priori that
>
> It is extremely interesting that sentences as flexible as the above
> could be filed as patent documents. Who is going to decide on the
> reasonableness and properly-ness of the said kind of inclusions?
> The patent holder??
>
> M. K. Shen
>
> -----
> Vin McLellan + The Privacy Guild + <vin@shore.net>
> 53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
> -- <@><@> --
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57