##
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:

- 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

- 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.*