The Oldest Algorithmic Patent?
While doing some research on cryptographic history, I stumbled on what may be one of the oldest algorithmic patents. That is, what is patented is an algorithm, rather than a physical, biological, or electronic device. It’s US patent 1,356,546, filed on December 4, 1918, and issued on October 26, 1920. It’s Lyman Morehouse’s two-tape variant of Vernam’s one-time pad encryptor, and is thus historically significant as well.
The story of Gilbert Vernam’s invention is told in in David Kahn’s The Codebreakers. (You can read Vernam’s original paper here.) Briefly, Vernam’s original form was a teletype with a very long paper tape with a true-random keystream on it; reusing any portion of the tape would completely gut the security of the system. (That’s what the Soviets did with their manual one-time pads during World War II; the American Venona project exploited the error.) The key stream byte (in reality, 5 bits) was exclusive-ORed with the plaintext byte to encrypt, or with the ciphertext byte to decrypt. It’s hard to produce and handle that much keying material, though. The obvious solution is to create a paper tape loop; that, however, generates repetitions too quickly. Lyman Morehouse came up with the idea of using two tapes of relatively prime lengths; that way, the total cycle time before repetition of the effective key byte is the product of the two lengths. It’s not as strong as the true one-time pad, but it’s pretty good. (More on that some other time.)
As Vernam had done with his idea a few months earlier, Morehouse filed a patent. That’s where things get interesting. To explain, though, I need to say a bit about the structure of patents.
Philosophically, a patent is a contract between an inventor and society. In exchange for teaching people about the invention, the inventor is granted a limited-term monopoly on the invention. The teaching is done in what is called the "specification"; the scope of the invention—that is, the outer boundary of the inventor’s monopoly—is set forth in a series of "claims". The specification is more or less an ordinary technical paper, albeit written in a somewhat stylized fashion; drafting a good set of claims, though, is what you pay patent attorneys to do. A good set of claims can be really hard to construct; for that matter, it’s not always easy to read them… Why is it so hard? Because you want to claim as many variants of the invention as you can get away with, to prevent people from inventing their way around your patent by coming up with a trivial variant not covered by your claims.
Let me give an example, one I heard when I was learning about patents at Bell Labs. Suppose you’ve invented the stool and want to patent it. Your claim describes a device comprising a "flat surface and four legs descending from it to the ground." Sound good? No: if you’ve patented that, I’ll build a stool with three legs; your patent requires four. On the other hand, I can’t build a five-legged stool without infringing; that device has the four legs that your invention requires, and thus infringes. Yes, it has something else as well, but that doesn’t matter; it could also have a back, decorations, a drink holder, and more, all without affecting whether or not it infringes your patent. The proper claim language is probably something like "a seat and one or more elongated support members for supporting the seat above an underlying surface".
I’ll skip the rest of the patent tutorial, save for one point: you typically include language in the specification to show that you’re aware of trivial or obvious variants. For this stool you’ve invented, you might say something like "it is obvious that the legs need not be wood, but may instead be metal, plastic, or any other suitably strong substance". That will protect you, even if all of the rest of the language in the specification speaks of wood.
Now let’s look at Morehouse’s patent. It starts off normally enough, describing things electrically (page 1, line 26):
The circuits of the sending and receiving relays, instead of all being grounded upon one side, may thus be connected to either battery or ground, depending on the positions of the contacts of this second transmitter.There is conventional language about using more than two tapes (page 3, line 67):
To practice the invention it is only necessary that there shall be plurality of series of ciphering characters, differing in length.So far, so good. Now look at page 3, line 43:
It will be clear that the invention is not limited to the use of perforated tapes, or any other particular form of record for the series of ciphering characters nor to any particular electrical or mechanical means for combining the characters from the several series to produce the running key by which the enciphering and deciphering are accomplished.Again, conventional enough, mentioning some obvious variants. But the patent goes on to say
It is not important in the use of the invention that the effect of combining the two or more characters from different series should be actually manifested in a discernible form.No "discernible form"? Presumably, Morehouse was thinking of hand-encryption rather than software (not surprising in 1919…), but that sure sounds like an algorithm.
The crucial question, though, is what he claimed. Was he actually trying to say that his invention need not be implemented in terms of electricity, gears, paper tapes, etc.? It sounds it to me. Here’s the first claim, in its entirety:
The method of enciphering or deciphering messages which consists in forming a plurality of series of ciphering characters different in each series, selecting characters from each series in a fixed order to form a continuous sequence by retraversing the series as it is exhausted, and altering the message characters in accordance with a predetermined rule whose effect upon successive message characters is dependent upon the concurrent use of characters so selected from different cipher series.There’s no mention of relays, currents, contacts, paper tapes, grounds, batteries, etc. The description is purely algorithmic. The patent claims don’t even mention paper tape loops until claim 12. Electrical contacts are not mentioned until the last claim.
Not convinced? Let’s compare that to the first claim of Vernam’s patent.
The method of enciphering signals where the characters are represented by a number of periods of different current values which consists in altering the normal code impulses of a character to be transmitted in accordance with a rule represented by some other character in a like code.Vernam speaks of electricity: "current values" and "code impulses". Morehouse speaks of "characters". It’s not that Vernam’s patent is too specific; page 4, line 89 notes that it is "obvious" that "any known medium" of transmission, including wireless, can be used. But Vernam’s claims are for a concrete mechanism; Morehouse’s are for an algorithm.
I don’t know that this is the oldest algorithmic patent, but I suspect that it’s one of the oldest.
