[Cryptography] Anybody sorted out the MQV patent claims?

[Thierry Moreau]

Hi,

While looking at discrete logarithm signatures in relation with 
Diffie-Hellman key establishment, I (re-)discovered a whole facet of 
public key cryptography.

Certicom is aggressive in asserting intellectual property rights in this 
area.

In a 2005 letter to a standardization body, Certicom indicated four US 
patents as pertaining to the MQV protocol (two "continuation in part") 
and one european patent.

US 5,896,455 --> US 5,761,305

US 6,785,813 --> US 6,122,736 (EP 0 739 105)

In all of these, the independent claims include the limitation that each 
party computes a digital signature value separate from the ephemeral D-H 
shared secret.

However, the MTI (ref [47] in [0]) protocol (the seminal idea for MQV, 
HMQV, and OAKE [0] as well) precisely *avoids* such a signature value 
(and thus avoids the DSA-type vulnerability to ephemeral private random 
number leakage -- neat achievement).

Thus, I see the above four patents as claiming something other than MQV. 
Anybody ever sorted this out?

The question pertains to patents that appears either expired (in 
first-to-file jurisdictions) or about to expire (in first-to-invent 
jurisdiction). I ask because the technical issues at stake appear 
relatively simple: compare figure 2 in US 6,122,736 and/or claim 1 in EP 
0 739 105 with the basic MQV operating principle.

- Thierry Moreau

[0] Andrew C. Yao and Yunlei Zhao, "A New Family of Implicitly 
Authenticated Diffie-Hellman Protocols", Cryptology ePrint Archive: 
Report 2011/035, http://eprint.iacr.org/2011/035