**Authenticated Public Key Encryption Schemes using Universal Hashing
Yuliang Zheng, October 1996 (Updated July 1998).**
Presented at the August 1998 meeting.

This proposal describes a technique for strengthening public key encryption so that it is secure against adaptively chosen ciphertext attacks. It uses universal hash functions in two different ways:

- to extract randomness hidden in a longer string,
- to authenticate a message for the purpose of non-malleability of a ciphertext.

PostScript File (247K)

Zipped PostScript File (68K)

Adobe Acrobat (.pdf) File (35K)

MSWord for Windows File (126K)

**DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem
Michel Abdalla, Mihir Bellare and Phillip Rogaway, August 1998 (Updated March 1999).**
Presented at the August 1998 meeting.

This paper describes a Diffie-Hellman based encryption scheme, DHAES. The scheme is as efficient as ElGamal encryption, but has stronger security properties. Furthermore, these security properties are proven to hold under appropriate assumptions on the underlying primitive.

We show that DHAES has not only the ``basic'' property of secure encryption (namely privacy under a chosen-plaintext attack) but also achieves privacy under both non-adaptive and adaptive chosen-ciphertext attacks. (And hence it also achieves non-malleability.)

DHAES is built in a generic way from lower-level primitives: a symmetric encryption scheme, a message authentication code, group operations in an arbitrary group, and a cryptographic hash function. In particular, the underlying group may be an elliptic-curve group or the multiplicative group of integers modulo a prime number.

The proofs of security are based on appropriate assumptions about the hardness of the Diffie-Hellman problem and the assumption that the underlying symmetric primitives are secure. The assumptions are all standard in the sense that no random oracles are involved.

We suggest that DHAES provides an attractive starting point for developing public-key encryption standards based on the Diffie-Hellman assumption.

PostScript File (713K)

Zipped Postscript File (161K)

Adobe Acrobat (.pdf) File (404K)

**PSEC: Provably Secure Elliptic Curve Encryption Scheme
Tatsuaki Okamoto, Eiichiro Fujisaki and Hikaru Morita, March 1999.**
Presented at the March 1999 meeting.

We describe an elliptic curve encryption scheme, PSEC (provably secure elliptic curve encryption scheme), which has two versions: PSEC-1 and PSEC-2. PSEC-1 is a public-key encryption system that uses the elliptic curve ElGamal trapdoor function and a random function (hash function). PSEC-2 is a public-key encryption system that uses the elliptic curve ElGamal trapdoor function, two random functions (hash functions) and a symmetric-key encryption (e.g., one-time padding and block-ciphers).

PSEC has several outstanding properties as follows:

- PSEC-1 is semantically secure or non-malleable against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model under the elliptic curve decision Diffie-Hellman (EC-DDH) assumption.
- PSEC-2 with one-time padding is semantically secure or non-malleable against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model under the elliptic curve Diffie-Hellman (EC-DH) assumption.
- PSEC-2 with symmetric encryption is semantically secure or non-malleable against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model under the elliptic curve Diffie-Hellman (EC-DH) assumption, if the underlying symmetric encryption is secure against passive attacks.
- If the underlying random function is replaced by a practical random like function (e.g., SHA and MD5), PSEC is almost as efficient as the elliptic curve ElGamal scheme, and is almost three times as efficient as the elliptic curve Cramer-Shoup scheme.

The encryption scheme described in this contribution is obtained by using two results on conversion techniques using random functions.

PostScript File (360K)

Zipped Postscript File (140K)

Adobe Acrobat (.pdf) File (94K)

David Pointcheval, October 1999.

This paper describes a new hybrid RSA-based public-key encryption scheme, the HD-RSA. It relies on the recently proposed Dependent-RSA problem, which can be proven as difficult as the original RSA problem, in some circumstances. The basic scheme, using the "one-time pad" symmetric encryption, provides a both very efficient scheme and secure relative to the sole Dependent-RSA problem. A more general proposal, by integrating symmetric encryption schemes, allows much higher rates under a very weak assumption about the symmetric scheme used.

The general scheme is first presented together with a careful study of its security relative to the Dependent-RSA problem. Then, the hardness of this new problem is discussed, namely by proving its equivalence with RSA, for well-chosen exponents. Therefore, it results that this new encryption scheme is semantically secure against any kind of attacks, namely non-adaptive and even adaptive chosen-ciphertext ones.

Moreover, with a similar security as OAEP-RSA (PKCS #1 v2.0), this scheme can reach higher speed rates. Furthermore, if one compares it with the DHAES or EPOC (two other IEEE P1363a candidates for encryption), efficiency gets many times better.

PostScript File (332K)

Zipped PostScript File (99K)

Adobe Acrobat (.pdf) File (361K)

Thomas Schweinberger and Victor Shoup, March 1, 2000.

This document describes a preliminary version of the Advanced Cryptographic Engine (ACE). It specifies a public key encryption scheme as well as a digital signature scheme with enough detail to ensure interoperability between different implementations. These schemes are almost as efficient as commercially used schemes, yet unlike such schemes, can be proven secure under reasonable and well-defined intractability assumptions. A concrete security analysis of both schemes is presented.

Adobe Acrobat (.pdf) File (368K)

Tatsuaki Okamoto and David Pointcheval, May 23, 2000.

We describe a new version of the elliptic curve encryption schemes PSEC (Provably Secure Elliptic Curve). PSEC-3 is a public-key encryption system that uses the elliptic curve El Gamal trapdoor function and two random functions (hash functions) as well as any semantically secure symmetric encryption scheme, such as the one-time pad, or any classical block-cipher.

Furthermore, we define a new problem, the Elliptic Curve Gap Diffie-Hellmann problem (EC-Gap-DH) which is likely stronger than the more classical Elliptic Curve Decision Diffie-Hellman (EC-DDH) problem. Indeed, its tractability would imply the equivalence between the Computational and the Decisional versions of the Elliptic Curve Diffie-Hellman problem.

PostScript File (200K)

Zipped PostScript File (48K)

Adobe Acrobat (.pdf) File (189K)

IEEE Home Page | IEEE Standards | P1363 Home Page |