IEEE P1363 Research Contributions:
Cryptographic Schemes and Protocols

Key Agreement Protocols and their Security Analysis
Simon Blake-Wilson, Don Johnson, and Alfred Menezes

This paper proposes new protocols for two goals: authenticated key agreement and authenticated key agreement with key confirmation in the asymmetric (public-key) setting. A formal model of distributed computing is provided, and a definition of the goals within this model supplied. The protocols proposed are then proven correct within this framework in the random oracle model. We emphasize the relevance of these theoretical results to the security of systems used in practice. Practical implementation of the protocols is discussed. Such implementations are currently under consideration for standardization.

Adobe Acrobat (.pdf) File

An Efficient Protocol for Authenticated Key Agreement
Laurie Law, Alfred Menezes, Minghua Qu, Jerry Solinas and Scott Vanstone

This paper proposes a new and efficient two-pass protocol for authenticated key agreement in the asymmetric (public-key) setting. The protocol is based on Diffie-Hellman key agreement and can be modified to work in an arbitrary finite group and, in particular, elliptic curve groups. Two modifications of this protocol are also presented: a one pass authenticated key agreement protocol suitable for environments where only one entity is on-line, and a three-pass protocol in which key confirmation is additionally provided. The protocols are currently under consideration for standardization in ANSI X9.42, ANSI X9.63, and IEEE P1363.

PostScript File (August 28, 1998) (210K)
Zipped PostScript File (August 28, 1998) (62K)
Adobe Acrobat (.pdf) File (August 28, 1998) (228K)

On the Security Properties of OAEP as an All-or-nothing Transform
Victor Boyko

This paper studies All-or Nothing Transforms (AONTs), which have been proposed by Rivest as a mode of operation for block ciphers. An AONT is an unkeyed, invertible, randomized transformation, with the property that it is hard to invert unless all of the output is known. Applications of AONTs include improving the security and efficiency of symmetric-key and public-key encryption. We give several formal definitions of security for AONTs that are stronger than the original ones and are more suited to practical applications. We then prove that Optimal Asymmetric Encryption Padding (OAEP), which was originally introduced by Bellare and Rogaway in a different context, satisfies these definitions (in the random oracle model). This is the first construction of an AONT that has been proven secure in the strong sense. The adversary's advantage in getting information about the input of the OAEP is shown to be inversely exponential in the number of bits removed from the output. Our bound is nearly optimal, in the sense that no adversary can do substantially better against the OAEP than by exhaustive search. We also show that no AONT can achieve substantially better security than OAEP.

PostScript File (August 8, 1999) (676K)
Zipped PostScript File (August 8, 1999) (150K)
Adobe Acrobat (.pdf) File (August 8, 1999) (306K)

Improving The Exact Security Of Digital Signature Schemes
Silvio Micali and Leonid Reyzin

We provide two contributions to exact security analysis of digital signatures:

  1. We put forward a new method of constructing Fiat-Shamir-like signature schemes that yields better "exact security" than the original Fiat-Shamir method; and

  2. We extend exact security analysis to exact cost-security analysis by showing that digital signature schemes with "loose security" may be preferable for reasonable measures of cost.

PostScript File (August 25, 1999) (619K)
Adobe Acrobat (.pdf) File (August 25, 1999) (334K)

Signing on a Postcard
David Naccache and Jacques Stern

We investigate the problem of signing short messages using a scheme that minimizes the total length of the original message and the appended signature. This line of research was motivated by several postal services interested by stamping machines capable of producing digital signatures. Although several message recovery schemes exist, their security is questionable. This paper proposes variants of DSA and ECDSA allowing partial recovery: the signature is appended to a truncated message and the discarded bytes are recovered by the verification algorithm. Still, the signature authenticates the whole message. Our scheme has some form of provable security, based on the random oracle model. Using further optimizations we can lower the scheme's overhead to 26 bytes for a 2-80 security level, compared to forty bytes for DSA and ECDSA and 128 bytes 1024-bit RSA.

PostScript File (February 14, 2000) (4315K)
Zipped PostScript File (February 14, 2000) (151K)
Adobe Acrobat (.pdf) File (February 14, 2000) (259K)

Generic Groups, Collision Resistance, and ECDSA
Daniel R. L. Brown, February 2002

Proved here is the sufficiency of certain conditions to ensure the Elliptic Curve Digital Signature Algorithm (ECDSA) existentially unforgeable by adaptive chosen-message attacks. The sufficient conditions include (i) a uniformity property and collision-resistance for the underlying hash function, (ii) pseudo-randomness in the private key space for the ephemeral private key generator, (iii) generic treatment of the underlying group, and (iv) a further condition on how the ephemeral public keys are mapped into the private key space. For completeness, a brief survey of necessary security conditions is also given. Some of the necessary conditions are weaker than the corresponding sufficient conditions used in the security proofs here, but others are identical. Despite the similarity between DSA and ECDSA, the main result is not appropriate for DSA, because the fourth condition above seems to fail for DSA. (The corresponding necessary condition is plausible for DSA, but is not proved here nor is the security of DSA proved assuming this weaker condition.) Brickell et al., Jakobsson et al. and Pointcheval et al. only consider signature schemes that include the ephemeral public key in the hash input, which ECDSA does not do, and moreover, assume a condition on the hash function stronger than the first condition above. This work seems to be the first advance in the provable security of ECDSA.

This work supersedes the paper "The Exact Security Of ECDSA", posted to this site in January 2001.

PostScript File (372K)

New Security Results on Encrypted Key Exchange
Emmanuel Bresson, Olivier Chevassut and David Pointcheval, October 2004

Schemes for encrypted key exchange are designed to provide two entities communicating over a public network, and sharing a (short) password only, with a session key to be used to achieve data integrity and/or message confidentiality. An example of a very efficient and ``elegant'' scheme for encrypted key exchange considered for standardization by the IEEE P1363 Standard working group is AuthA. This scheme was conjectured secure when the symmetric-encryption primitive is instantiated via either a cipher that closely behaves like an ``ideal cipher'', or a mask generation function that is the product of the message with a hash of the password. While the security of this scheme in the former case has been recently proven, the latter case was still an open problem. For the first time we prove in this paper that this scheme is secure under the assumptions that the hash function closely behaves like a random oracle and that the computational Diffie-Hellman problem is difficult. Furthermore, since Denial-of-Service (DoS) attacks have become a common threat we enhance AuthA with a mechanism to protect against them.

Author's web site

Password authenticated key exchange by juggling
Feng Hao and Peter Ryan, April 2008

Abstract: Password-Authenticated Key Exchange (PAKE) studies how to establish secure communication between two remote parties solely based on their shared password, without requiring a Public Key Infrastructure (PKI). Despite extensive research in the past decade, this problem remains unsolved. Patent has been one of the biggest brakes in deploying PAKE solutions in practice. Besides, even for the patented schemes like EKE and SPEKE, their security is only heuristic; researchers have reported some subtle but worrying security issues. In this paper, we propose to tackle this problem using an approach different from all past solutions. Our protocol, Password Authenticated Key Exchange by Juggling (J-PAKE), achieves mutual authentication in two steps: first, two parties send ephemeral public keys to each other; second, they encrypt the shared password by juggling the public keys in a verifiable way. The first use of such a juggling technique was seen in solving the Dining Cryptographers problem in 2006. Here, we apply it to solve the PAKE problem, and show that the protocol is zero-knowledge as it reveals nothing except one-bit information: whether the supplied passwords at two sides are the same. With clear advantages in security, our scheme has comparable effciency to the EKE and SPEKE protocols.

Adobe Acrobat (.pdf) File (April 2008) (146K)

This page was last modified on October 10, 2008.
IEEE Logo IEEE Standards Logo IEEE P1363 Logo
IEEE Home Page IEEE Standards IEEE P1363