Prior Art Patents and PEKE

CONNOTECH Experts-conseils Inc.

In considering the patent licensing requirements for an application of the PEKE technology, the facts related in this annex may be considered. For the cryptography expert, most of these facts are elementary, or can be easily inferred from reading the references. For the legal advisor, these facts (validated by an independent expert if need be) may constitute the basis for a legal opinion.

In the field of public key cryptography, the following concepts are defined:

Public key encryption is a process in which a message is encrypted using the public key of the legitimate recipient. Only the legitimate recipient is capable of decrypting the message encrypted in this way.

A digital signature is the transformation of a message by a signer using secret information (a private key), this transformation being impossible to achieve without knowledge of this secret information. Any party knowing the signer's public key can verify the digital signature.

The Diffie-Hellman cryptosystem, USA patent document 4,200,770 [2] (see also [1]), offers neither a public key encryption technology nor a digital signature capability. Instead, it allows two parties to establish a secret session key without sharing any prior secret information and without using a third party. There is no recognized generic term for this secret key exchange capability. With the exception of the PEKE technology, no cryptosystem besides Diffie-Hellman offers the secret key exchange capability independently of the public key encryption capability.

The text of the Hellman-Merkle patent, USA patent document 4,218,582 [3], discloses the knapsack cryptosystem [4], [5], and contains claims (notably claims 1 and 6) describing in fairly generic terms the notion of public key encipherment. This patent also contains claims (notably claims 4 and 5) describing in fairly generic terms the notion of digital signatures. The Hellman-Merkle claims do not describe the notion of secret key exchange introduced by the Diffie-Hellman cryptosystem.

The PEKE technology offers neither a public key encryption capability nor a digital signature capability. The services and the protections offered by the PEKE technology are comparable to the Diffie-Hellman cryptosystem.


Differences between the PEKE technology and the Diffie-Hellman cryptosystem

Table: Differences between the PEKE technology and the Diffie-Hellman cryptosystem

There are many differences between the PEKE technology and the Diffie-Hellman cryptosystems in their operation. They are summarized in the table above and explained below:

A
The algorithm operations mandated by the PEKE technology are radically different from those of the Diffie-Hellman. In the case of PEKE, the initiating party has a very different set of mathematical formulas to apply than the responder party. With Diffie-Hellman, the same formulas are applied by both parties.
B
For PEKE, the type of public key cryptography functions is a one-way trap-door function (as is the case in most public key cryptography algorithms), which is also an "unpredictable to the left," "cryptographically-strong" pseudo-random number generator. Diffie-Hellman uses the different strategy of double application of a simple on-way function (that is a one-way function that has no trap-door). The Diffie-Hellman strategy is directly reflected in the wording of claims 1, 2, 4, 5, 6, 7, and 8 in the Diffie-Hellman patent.
C
For PEKE, the actual public key cryptography functions includes the x^2^t mod N one-way trap-door, and the "x² mod N" generator. For Diffie-Hellman, the exponentiation function a^x mod p one-way function is used. The Diffie-Hellman usage of the exponentiation function is directly reflected in the wording of claims 6, 7, and 8 in the Diffie-Hellman patent.
D
Accordingly, the security foundation of the PEKE technology is the difficulty of factoring large numbers. The security foundation of the Diffie-Hellman cryptosystem is the difficulty of computing the discrete logarithm for properly selected parameters a and p.
E
The public security parameter for PEKE is the public key N of one party in the protocol (namely the initiator party). For Diffie-Hellman, the parameters a and p are applicable to both parties indiscriminately, and may be common to a group of users.
F
PEKE provides authentication as an additional security service (in addition to secret key exchange). This authentication capability is unidirectional (the responder authenticates the initiator, but the reverse is not true). Diffie-Hellman may provide authentication, but then the secret key will not be unique to the session in which the authentication capability is used.
G
A specific protocol differentiation between PEKE and Diffie-Hellman is the characterization of the first message: only in the Diffie-Hellman case, the first message is the result of a transformation infeasible to invert. This Diffie-Hellman characteristic is directly reflected in the wording of claims 2, 4, and 6 in the Diffie-Hellman patent.

References

[1] Diffie, Bailey Whitfield, Hellman, Martin E., New Directions in Cryptography, IEEE Transactions in Information Theory, vol IT-22, 1976, pp 644-654

[2] USA patent document 4,200,770 Hellman, Martin E., Diffie, Bailey Whitfield, Merkle, Ralph C., Cryptographic Apparatus and Method, April 29, 1980 (the Canadian equivalent to this patent is patent number 1,121,480)

[3] USA patent document 4,218,582 Hellman, Martin E., Merkle, Ralph C., Public Key Cryptographic Apparatus and Method, August 19, 1980 (foreign equivalents: Australia 40 418/78, Belgium 871039, Canada 1 128 159, France 78 28474, Germany DE 28 43 583 C2, Italy 1099780, Japan 1,270,888, Spain 474.539, Sweden 78 10478-3, Switzerland 634161, United Kingdom 2 006 580 B)

[4] Merkle, Ralph C., Hellman, Martin E., Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, Vol. 24 (1978), pp 525-534

[5] Odlyzko, A.M., The Rise and Fall of Knapsack Cryptosystems, in Cryptology and Computational Number Theory, C. Pomerance, editor, American Mathematical Society, 1990, pp 75-88

[ Web Map for PEKE: http://www.connotech.com/pekemap.htm ]
[ CONNOTECH home page: http://www.connotech.com/ | about us | web editorial policy | e-mail to: info@connotech.com ]

CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691 Fax: +1-514-385-5900