To: rivest@theory.lcs.mit.edu Subject: Re: Software patents and self-revealing inventions Ok, I'll admit it. The notion of public key cryptography was a clever invention. It would probably have been deserving of patent protection if it was the case that the prospect of gaining a patent had led to its original invention. However all the evidence I have seen suggests that this was not the case. The invention came first, and the decision to obtain a patent came later. It would have been invented whether the patent system existed or not. This the patent system has been detrimental to the development of public key technology. I personally feel that the RSA algorithm was not sufficiently novel to be granted a patent. Once the notion of public key cryptography was out, I feel certain that someone else would have invented it well before the current RSA patent expires. rivest@theory.lcs.mit.edu (Ron Rivest): > .. There are certainly many bad software patents that have been issued .. Appalling. I guess you are aware of the trends in cryptographic patents. Virtually every trivial application and algorithm is now being patented. These are orders of magnitude more trivial than anything I am aware of you having filed. For instance I did a survey of the patents granted in one arbitrary week. The following are the cryptographic patents granted in that week. My rather glib and often opinionated comments are in brackets. 5,001,750 Secret Communication Control Apparatus filed 1990-03-07 granted 1991-03-19 assignee Aisin Seiki Kabushiki Kaisha inventor Hidehorn Kato, Yoshihiro Naruse, Yoshifami Iwata Encryption devices for connection between a modem, fax or similar, and a phone line, which performs encryption on message data, but not on communication protocol data. Encryption step obviously requiring demodulation, encryption and remodulation. Non-encryption involving the direct connection of the input and output signals. [Intention is to provide secrecy, without significantly increasing protocol latency.] 5,001,752 Public/Key Date-time Notary Facility filed 1989-10-13 granted 1991-03-19 assignee as below inventor Addison M. Fischer 30. A method of digitally time notarizing a digital message comprising the steps of: receiving a digital message to be date/time notarized by a special purpose digital notarizing device; generating clock signals indicative of time within said device; accessing a private key created for said device and stored in a tamper proof storage device in said notarization device, said private key having a corresponding device public key, said device public key having been certified by a trusted authority; and operating on said digital message, and said clock signals, using said private key, whereby a notarized time stamp is generated by said notarization device. [This is not an invention. The use of public key technology to provide time stamping is well known. The suitability and advantages of special purpose hardware for this task are equally obvious. I had hoped that with the expiration of the Diffie Hellman patent in 1997 (1994 Australia) public key technology would become widely available. However I have recently discovered that there are a whole pile of trivial patents on virtually every aspect of its use, granted from the mid to late 1980's. This is true in Australia, and it would appear that the same is true in the U.S.] 5,001,753 Cryptographic System and Process and Its Apparatus filed 1988-03-07 granted 1991-03-19 assignee U.S. Philips Corporation inventor More Davio, Philippe Gantler, and three others A method of storing a table for performing a permutation and its inverse in which the forward permutation is stored directly in a table containing the the new index positions, while the reverse permutation is stored using a table that maps each position to a group of entries in the forward table, which must then be searched to find the appropriate entry. Thus fewer bits are required for storing each of the reverse entries than would otherwise be the case. [This is only useful if the object to be permuted just fits in memory so that it must be permuted in situ and furthermore if it is prohibitively expensive to store both the forward and reverse permutation tables in full. For instance if a machine has 1M of memory, the full forward permutation table requires 600k, and the object to be permuted consumes 300k. The most likely application is probably far more modest: smart cards in which the available RAM to store the object to be permuted might be limited to 64 bits, and the ROM used to store the permutation table might be limited to 512 bits. It took me 5 hours to understand the claims on their own, I wonder if the full patent was written to be intentionally confusing. Claim 2, probably the easiest claim to understand, has 6 errors in it and it is only 8 lines long.] 5,001,754 Encryption System and Method filed 1990-02-01 granted 1991-03-19 assignee The Trustees of Princeton University inventor Kenneth S. Deffeyes Encryption by generation of a pseudo-random sequence to be xored with the plain text, in which the pseudo-random sequence is generated by, presumably using a video bit blitter, to repeatedly xor regions of video memory together which initially contained data derived from the key. The regions of memory to be xored together being selected in accordance with a predetermined function. Claim 3 is for the improvement in which the initial data constitutes the bit map representation of the alphanumeric key. [I am not sure which I find more threatening: the patent office considering something so trivial to be an invention, or that Princeton University is so totally inept. The conservative property of xor makes it useless for the generation of cryptographic randomness. And along with the use of a predetermined key this makes this scheme equivalent to the standard standing joke in cryptography of performing encryption by xoring a password with successive portions of the plain text. To be fair claim 4 is for the improvement in which the key is used to modify the predetermined function, but I think I will still stick with DES for the time being. I am totally aghast by all the other claims. Why are cryptographic weenies so attracted to the patent system. A recently Australian patent application I came across was for a brilliant invention which consisted of the storing of a one time pad on a hard disk. So far the patent office has spent three years trying to decide whether to grant it. I could have decided the matter in 30 seconds. I don't know if I am putting too much faith in the Patent Office by assuming the application will be dismissed, but if it isn't it will constitute a very large club with which to beat them over the head. The Australian Patent Act means that if the patent is granted the assignee will be able to sue for retrospective infringement, so despite the apparent ridiculous nature of the application, the doubts I have in regards to the competence of the Patent Office, mean that I can't totally ignore it.] 5,001,755 Security System Network filed 1990-03-21 granted 1991-03-19 assignee Vindicator Corporation inventor Daniel L. Skret 7. A security system for encrypting at least a portion of data transmissions between nodes comprising: means for generating an identical sequence of pseudorandom numbers at both a transmitting and receiving node; means for providing a key identifying a starting position in said sequence to both said transmitting and receiving nodes; and means for incrementing the position in said sequence at both said transmitting and receiving nodes for each predetermined portion of data transmission between said nodes; and means for encrypting segments of said data transmissions using said pseudorandom numbers using said starting position for a first segment corresponding to said first position and using subsequent numbers for succeeding segments corresponding to succeeding portions with each node using a different sequence position for each node it communicates with. [Conspiracy theory time. The Patent Office is in league with the NSA to prevent the widespread adoption of cryptographic technology. Explicit orders have been given to ignore the normal novelty, and non-obviousness criteria. I mean with a name like Vindicator Corporation it just has to be another front for the "secret team". I am not being serious, but if it wasn't for the fact that the Patent Office appears to be incompetent in so many other fields of technology, I might have drawn such a conclusion.] Only according to the most niave of rationales for the patent system could these be considered anything other than appalling. > Suppose someone proves that P = NP, and in doing so develops a > polynomial-time algorithm for solving any problem in NP. Depending on > whether or not his algorithm was patentable, he would very likely (if > he were motivated to capitalize on his efforts), do one of two things: > (A) if his algorithm was not patentable, he would set up shop solving > other people's problems, keeping his algorithm a trade secret. > In other words, you bring your traveling salesman, knapsack > or integer programming problem to him, and he solves it for > $5,000 a problem. The algorithm might remain secret for > many years, and might even die with him, not to be discovered > for centuries. (What was Fermat's proof for his Last Theorem, > anyway?) > (B) if his algorithm is patentable, he discloses it in a patent, > collects royalties for 17 years, and then the idea is in the > public domain. > > I think scenario (B) is arguably preferable to scenario (A), in terms > of any reasonable measure of social utility. (We may presuppose that, > since it is not our invention, no other choices are open to us. We > have to define the rules for inventors to live by.) Achieving (B) is > exactly the kind of thing that the patent law is intended to > do---require someone to disclose his invention in return for a > limited-time exclusive use (or licensing rights). Society is better > off if such an invention were, after a limited time, in the public > domain. I think any argument against this interpretation would > probably have to be against all patents per se. But I would like to > hear opinions. This is the classical "exchange for secrets" rationale for the patent system. It can largely be refuted by the following simple observation: "An inventor who, optimistically, thinks he need not fear that others would either find out his secret or come independently upon the same idea, will not go to the expense and trouble of taking a patent; he will disclose only what he fears cannot be kept secret." -- F. Machlup, An Economic Review of the Patent System, [A commissioned report for the] Study of the Subcommittee on Patents Trademarks and Copyrights, Committee on the Judiciary, United States Senate, 1958. I will leave the details for you to formulate, but in my opinion the "exchange for secrets" rationale has little merit. > One plausible argument against most software patents is that they are > generally self-revealing. Self-revealing inventions are a little bit > strange to patent, because its not clear why the goverment should > choose to grant a patent for one. If the goal of the patent process > is to get inventions in the public domain, eventually, then modifying > the law to exclude the patentability of self-revealing inventions > would also meet that goal. Once the invention is made, the only way > to practice it is in some self-revealing manner that effectively > places it in the public domain. I concede that rationalizing the patent system is a very tricky business. But I feel that you are approaching things from the wrong end. If you start from the viewpoint that inventions already exist then as far as I am aware no reasonable arguments can be made in favour of granting patents. The only argument in favour of patents that I can agree with is that on account of the appropriable nature of inventions it is necessary to grant patents so as to provide an incentive to encourage invention. And from this perspective the notion of "self-revealing" inventions is largely irrelevant. Patents should be granted on self-revealing, and non-self-revealing inventions alike. The patent system exists to encourage invention, not disclosure. In an "ideal" free market economy I think this "incentive for invention" argument would always be valid. The only issues that need to be addressed are the degree of novelty and length of time that patents should be granted for. These matters are largely economic considerations. I feel that given the current degree of novelty a term of 2 weeks might be appropriate. But we do not live in an "ideal" free market economy. Associated with granting a patent there are administrative and legal costs. Many inventions would occur without the patent system. Government funding for inventive activity exists. Business decisions are hampered by uncertainty (something which patents increase). The desire to provide product differentiation already acts as an incentive to innovate. I feel every one of these is sufficient on their own to nullify the "incentive for invention" argument in favour of software patents. Put simply the incentive to invent already exists. Any firm that does not produce innovative software will loose market share. And I might add in a time period much less than that for which patents currently last. The above arguments apply to all field of inventive activity. However they do not apply equally. For instance in the case of pharmaceuticals in the absence of any government funding for invention a period of perhaps 10 years might still be appropriate. I know too little about the pharmaceutical industry to attempt to make any definite pronouncements on this. On the other hand I feel mechanical, electrical, and general patents should probably be either abolished, or the degree of novelty required drastically increased. Although in none of these cases do I feel the economic pressures are as great as they are in the case of software. Gordon Irlam (gordoni@cs.adelaide.edu.au) "I'll make a patent abolitionist out of you yet. But seriously, feel free to continue this discussion, even if you are not at liberty to discuss cryptographic patents."