Presentations and Documents for the August 2005 Working Group Meeting

1363-2000 review

HMQV: A High-Performance Secure Diffie-Hellman Protocol, Hugo Krawczyk.
Paper (pdf), Presentation (ppt).

The MQV protocol of Law, Menezes, Qu, Solinas and Vanstone is possibly the most efficient of all known authenticated Diffie-Hellman protocols that use public-key authentication. In addition to great performance, the protocol has been designed to achieve a remarkable list of security properties. As a result MQV has been widely standardized, and has recently been chosen by the NSA as the key exchange mechanism underlying “the next generation cryptography to protect US government information”. One question that has not been settled so far is whether the protocol can be proven secure in a rigorous model of key-exchange security. In order to provide an answer to this question we analyze the MQV protocol in the Canetti-Krawczyk model of key exchange. Unfortunately, we show that MQV fails to a variety of attacks in this model that invalidate its basic security as well as many of its stated security goals. On the basis of these findings, we present HMQV, a carefully designed variant of MQV, that provides the same superb performance and functionality of the original protocol but for which all the MQV’s security goals can be formally proved to hold in the random oracle model under the computational Diffie-Hellman assumption.

Another Look At HMQV, Alfred Menezes. (available from IACR ePrint Archive)

HMQV is a `hashed variant' of the MQV key agreement protocol. It was recently introduced by Krawczyk, who claimed that HMQV has very significant advantages over MQV: (i) a security proof under reasonable assumptions in the (extended) Canetti-Krawczyk model for key exchange; and (ii) superior performance in some situations.

In this paper we demonstrate that HMQV is insecure by presenting realistic attacks in the Canetti-Krawczyk model that recover a victim's static private key. We propose HMQV-1, a patched version of HMQV that resists our attacks (but does not have any performance advantages over MQV). We also identify the fallacies in the security proof for HMQV, critique the security model, and raise some questions about the assurances that proofs in this model can provide.


Performance Improvements and a Baseline Parameter Generation Algorithm for NTRUSign, Jeff Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte.

A presentation (ppt) on this paper

The original presentation of the NTRUSign signature scheme gave a set of parameters that were claimed to give 80 bits of security, but did not give a general recipe for generating parameter sets to a specific level of security. In line with recent research on NTRUEncrypt, this paper presents an outline of such a recipe for NTRUSign. We also present certain technical advances upon which we intend to build in subsequent papers.


P1363.2 Update, David Jablon, Phil MacKenzie. Powerpoint presentation

Status report on P1363.2.

OPAKE: Password Authenticated Key Exchange based on the Hidden Smooth Subgroup assumption, Craig Gentry, Philip MacKenzie, Zulfikar Ramzan. Powerpoint Presentation. A novel password-based public key technique.

PAK-Z+, Craig Gentry, Philip MacKenzie, Zulfikar Ramzan, PDF file

We present a revised version of the of the PAK-Z protocol, called the PAK-Z+ protocol, and give a complete proof of security.

Editorial changes to APKAS-PAKZ, David Jablon. PDF file or Word .doc.

Planned changes to P1363.2 D21 PAKZ to fix missing and incorrect octet-string conversion functions to allow PAKZ to use any 1363 signature scheme, plus other editorial changes.

Proposed changes to APKAS-AMP, Taekyoung Kwon, editted by David Jablon. PDF file. or Word .doc.

A proposed change to P1363.2 D21 AMP to prevent an attacker from masquerading as the Client using the password verification data vπ.

Proposed changes to APKAS-PAKZ, Phil MacKenzie, editted by David Jablon. PDF File or Word .doc,

A proposed change to P1363.2 D21 PAKZ to prevent an attacker from masquerading as the Client using the password verification data.


Standard for pairing-based cryptographic techniques, Guido Appenzeller.
Presentation (pdf).

An overview of the timetable and process for 1363.3.

An Efficient ID-KEM Based On The Sakai–Kasahara Key Construction, L. Chen, Z. Cheng, J. Malone–Lee, and N.P. Smart. Paper (pdf), Presentation (pdf).

Sakai et. al in 2000 produced a method of construction identity based public/private key pairs using pairings on elliptic curves. In 2001, using the same key construction as Sakai et. al., Boneh and Franklin presented the first efficient and provably secure identity-based encryption scheme. In 2003 Sakai and Kasahara proposed another method of constructing identity based keys, also using pairings, which has the potential to improve performance. Later, Chen and Cheng gave a provably secure identity based scheme using this second construction. Both the Boneh–Franklin scheme and the scheme based on the second construction are not true hybrid encryption schemes in the traditional of the public key KEM/DEM approach. To address this issue, Bentahar et. al. extended the idea of key encapsulation mechanism to the identity based setting and presented three constructions in line with the original Sakai et. al. method of constructing identity based keys. In this paper we present another ID-KEM based on the second method of constructing identity based keys and prove its security. The new scheme has a number of advantages over all previous ID-based encryption schemes.

Other Projects

Proposed PAR for Standard Specification for Public Key Cryptography based on Class Groups Of Imaginary Quadratic Number Fields (IQ Cryptography), Mike Jacobson.
Word Doc, presentation (pdf)

The IEEE 1363 and 1363a standards provide a comprehensive framework for the implementation of various forms of public key cryptographic protocols. The computational problems upon which these protocols are based are the discrete logarithm, integer factorization and elliptic curve families. Using imaginary quadratic class fields, we find analogous problems that are at least as hard as their regular counterparts, and appear to be harder in some cases. More importantly, the hardness of the IQ problems appears to be independent of the hardness of other variants of the same problems. As there are no rigorous proofs of the difficulty of any of these problems, and progress is continually being made in finding more efficient solutions, having an independent set of problems upon which to base cryptographic systems is desirable.

This page was last modified on August 17, 2005.
IEEE Logo IEEE Standards Logo IEEE P1363 Logo
IEEE Home Page IEEE Standards IEEE P1363