Ten prominent patents

Ten prominent patents are discussed in this section, in order as per Table 15.2.


Patent #

Issue date


Major claim or area

Okamoto et al.


Nov. 25 1986


ESIGN signatures



May 31 1988


Fiat-Shamir identification

Matyas et al.


Jul. 18 1989


control vectors



Jul. 18 1989


FEAL cipher

Brachtl et al.


Mar. 13 1990


MDC-2, MDC-4 hashing



Feb.19 1991


Schnorr signatures



Aug. 18 1992


GQ identification



May 25 1993


IDEA cipher



Jul. 27 1993


DSA signatures



Jan. 04 1994


‘fair’ key escrow

Table 15.2: Ten prominent U.S. cryptographic patents.

(i) ESIGN signatures

The Okamoto-Miyaguchi-Shiraishi-Kawaoka patent (4,625,076) covers the original ESIGN signature scheme (see §11.7.2). The patent was filed March 11 1985 and assigned to the Nippon Telegraph and Telephone Corporation (Tokyo), with priority data listed as March 19 1984 (Japanese patent office). The objective is to provide a signature scheme faster than RSA. The patent contains twenty-five (25) claims.

(ii) Fiat-Shamir identification and signatures

The Shamir-Fiat patent (4,748,668) covers Fiat-Shamir identification (§10.4.2) and signatures (§11.4.1). It was filed July 9 1986, and assigned to Yeda Research and Development Co. Ltd. (Israel). For identification, the inventors suggest a typical number of rounds t as 1 to 4, and parameter selections including к = 5 (secrets), t = 4 for a 2-20 probability of forgery, and к = 6, t = 5 for 2-30. A range of parameters k, t for kt = 72 is tabulated for the corresponding signature scheme, showing tradeoffs between key storage, signature size, and real-tune operations required. Noted features relative to prior art include being able to pipeline computations, and being able to change the security level after the key is selected (e.g., by changing t). Generalizations noted include replacing square roots by cubic or higher roots. There are forty-two (42) claims.

(iii) Control vectors for key management

The Matyas-Meyer-Brachtl patent (4,850,017) is one of several in the area of control vectors for key management, in this case allowing a sending node to constrain the use of keys at a receiving node. It was filed May 29 1987 and assigned to the IBM Corporation. Control vectors reduce the probability of key misuse. Two general methods are distinguished. In the first method, the key and a control value are authenticated before use through verification of a special authentication code, the key for which is part of the data being authenticated. In the second method (see §13.5.2), the key and control value are cryptographically bound at the time of key generation, such that recovery of the key requires specification of the correct control vector. In each method, additional techniques may be employed to control which users may use the key in question. The patent contains twenty-two (22) claims.

(iv) FEAL block cipher

The Shimizu-Miyaguchipatent (4,850,019) gives the originally proposed ideas of the FEAL block cipher (see §7.5). It was filed November 3 1986 and assigned to the Nippon Telegraph and Telephone Corporation (Токую), with priority data listed as November 8 1985 (Japanese patent office). Embodiments of FEAL with various numbers of rounds are described, with figures including four- and six-round FEAL (now known to be insecure - see Note 7.100), and discussion of key lengths including 128 bits. The patent makes twenty-six (26) claims.

(v) MDC-2/MDC-4 hash functions

The patent of Brachtl et al. (4,908,861) covers the MDC-2 and MDC-4 hash functions (§9.4.1). It was filed August 28 1987 and assigned to the IBM Corporation. The patent notes that interchanging internal key halves, as is done at a particular stage in both algorithms, is actually required for security in MDC-2 but not MDC-4; however, the common design was nonetheless used, to allow MDC-4 to be implemented using MDC-2 twice. A preliminary section of the patent discusses alternatives for providing message authentication (see §9.6), as well as estimates of the security of the new hash functions, and justification for fixing certain bits within the specification to avoid effects of weak DES keys. There are twenty-one (21) claims, mainly on building 2Л'-bit hash functions from .V-bit block ciphers.

(vi) Schnorr identification and signatures

The Schnorr patent (4,995,082) covers Schnorr’s identification (§10.4.4) and signature (§11.5.3) schemes, and optimizations thereof involving specific pre-processing. It was filed February 23 1990, with no assignee fisted, and priority data given as February 24 1989 (European patent office). There are eleven (11) claims. Part of Claim 6 covers a specific variation of the Fiat-Shamir identification method using a prime modulus p, such that p - 1 is divisible by a prime q, and using a base (3 of order q.

(vii) GQ identification and signatures

The Guillou-Quisquater patent (5,140,634) addresses GQ identification (Protocol 10.31) and signatures (Algorithm 11.48). It was filed October 9 1991, as a continuation-in-part of two abandoned applications, the first filed September 7 1988. The original assignee was the U.S. Philips Corporation (New York). The disclosed techniques allow for authentication of so-called accreditation information, authentication of messages, and the signing of messages. The central authentication protocol involves a commitment-challenge-response method and is closely related to the zero-knowledge-based identification technique of Fiat and Shamir (Protocol 10.24). However, it requires only a single protocol execution and single accreditation value, rather than a repetition of executions and a plurality of accreditation values. The cited advantages over previous methods include smaller memory requirements, and shorter overall duration due to fewer total message exchanges. The main applications cited are those involving chipcards in banking applications. There are twenty-three (23) claims, including specific claims involving the use of chipcards.

(viii) IDEA block cipher

The Massey-Lai patent (5,214,703) covers the IDEA block cipher (§7.6), proposed as a European or international alternative to DES offering greater key bitlength (and thereby, hopefully greater security). It was filed May 16 1991, and assigned to Ascom Tech AG (Bern), with priority data given as May 18 1990 from the original Swiss patent. A key concept in the cipher is the use of at least two different types of arithmetic and logical operations, with emphasis on different operations in successive stages. Three such types of operation are proposed: addition mod 2m, multiplication mod 2m + 1, and bitwise exclusive-or (XOR). Symbols denoting these operations, hand-annotated in the European version of the patent (WO 91/18459, dated 28 November 1991, in German), appear absent in the text of the U.S. patent, making the latter difficult to read. There are fourteen (14) figures and ten (10) multipart claims.

(ix) DSA signature scheme

The patent of Kravitz (5,231,668), titled “Digital Signature Algorithm”, has become widely known and adopted as the DSA (§11.5.1). It was filed July 26 1991, and assigned to “The United States of America as represented by the Secretary of Commerce, Washington, D.C.” The background section includes a detailed discussion of ElGamal signatures and Schnorr signatures, including their advantage relative to RSA - allowing more efficient on-line signatures by using off-line precomputation. Schnorr signatures are noted as more efficient than ElGamal for communication and signature verification, although missing some “desirable features of ElGamal” and having the drawback that cryptanalytic experience and confidence associated with the ElGamal system do not carry over. DSA is positioned as having all the efficiencies of the Schnorr model, while remaining compatible with the ElGamal model from an analysis perspective. In the exemplary specification of DSA, the hash function used was MD4. The patent makes forty-four (44) claims.

(x) Fair cryptosystems and key escrow

Micali’s patent (5,276,737) and its continuation-in-part (5,315,658), respectively filed April 20 1992 and April 19 1993 (with no assignees listed), cover key escrow systems called “fair cryptosystems” (cf. §13.8.3). The subject of the first is a method involving a public-key cryptosystem, for allowing third-party monitoring of communications (e.g., government wiretapping). A number of shares (see secret-sharing - §12.7) created from a user-selected private key are given to a set of trustees. By some method of verifiable secret sharing, the trustees independently verify the authenticity of the shares and communicate this to an authority, which approves a user’s public key upon receiving all such trustee approvals. Upon proper authorization (e.g., a court order), the trustees may then subsequently provide their shares to the authority to allow reconstruction of a user private key. Exemplary systems include transforming Diffie-Hellman (see paragraph below) and RSA public-key systems into fair cryptosystems. Modifications require only к out of n trustees to contribute shares to recover a user secret and prevent trustees from learning the identity of a user whose share is requested. The patent contains eighteen (18) claims, the first 14 being restricted to publickey systems.

A fair cryptosystem for Diffie-Hellman key agreement modulo p, with a generator g and n trustees, may be constructed as follows. Each user A selects n integers si,... , sn in the interval [l,p — 1], and computes s = J^”=1 s mo<l P> public shares y, = gs> mod p, and a public key у = gs mod p. Trustee T,, 1 < i < n, is given y, public shares yi,... ,yn, and the secret share s, to be associated with A. Upon verifying yt = gSl ,T, stores (A. y, and sends the authority a signature on (i,y, yi,... , yn). Upon receiving such valid signatures from all n trustees, verifying the У = П Vi ino(l die authority authorizes у as A’s Diffie-Hellman public key.

The continuation-in-part pursues time-bounded monitoring in greater detail, including use of tamper-proof chips with internal clocks. Methods are also specified allowing an authority (hereafter, the government) access to session keys, including users employing a master key to allow such access. A further method allows verification, without monitoring content, that transmitted messages originated from government-approved devices. This may involve tamper-proof chips in each communicating device, containing and employing a government master key Km- Such devices allow verification by transmitting a redundant data string dependent on this key. The continuation-in-part has thirteen (13) claims, with the first two (2) restricted to public-key systems. Claims 11 and 12 pursue methods for verifying that messages originate from a tamper-proof device using an authorized encryption algorithm.

< Prev   CONTENTS   Source   Next >