IEEE P1363: Protocols from other families of public-key algorithms


EPOC: Efficient Probabilistic Public-Key Encryption
Tatsuaki Okamoto, Shigenori Uchiyama and Eiichiro Fujisaki, November 1998.
Presented at the
November 1998 and October 1999 meetings.

We describe a novel public-key cryptosystem, EPOC (Efficient Probabilistic Public Key Encryption), which has two versions: EPOC-1 and EPOC-2. EPOC-1 is a public-key encryption system that uses a one-way trapdoor function and a random function (hash function). EPOC-2 is a public-key encryption system that uses a one-way trapdoor function, two random functions (hash functions) and a symmetric-key encryption (e.g., one-time padding and block-ciphers).

EPOC has several outstanding properties as follows:

  1. EPOC-1 is semantically secure or non-malleable against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model under the p-subgroup assumption, which is comparable to the quadratic residue and higher degree residue assumptions.
  2. EPOC-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 factoring assumption.
  3. EPOC-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 factoring assumption, if the underlying symmetric encryption is secure against passive attacks.
  4. The trapdoor technique with EPOC is fundamentally different from any other previous scheme including RSA-Rabin and Diffie-Hellman-ElGamal.
  5. Under the most practical environment in which public-key cryptosystems would be used, the encryption and decryption speeds of EPOC are comparable (several times slower) to those of elliptic curve cryptosystems. Compared with OAEP (RSA) with small e (e.g.,216 + 1), although the encryption speed of EPOC is slower than that of OAEP, the decryption speed is faster than that of OAEP.

The encryption scheme described in this contribution is obtained by combining three results: one [25] on the trapdoor function technique is by Okamoto and Uchiyama, and the others [13, 14] on conversion techniques using random functions are by Fujisaki and Okamoto.

PostScript File (420K)
Zipped Postscript File (100K)
Adobe Acrobat (.pdf) File (219K)


TSH-ESIGN: Efficient Digital Signature Scheme Using Trisection Size Hash
Tatsuaki Okamoto, Eiichiro Fujisaki and Hikaru Morita, November 1998.
Presented at the
November 1998 and October 1999 meetings.

We describe a practical digital signature scheme, TSH-ESIGN, which is more efficient than any representative signature scheme such as elliptic curve and RSA based signature schemes. Moreover, TSH-ESIGN is provably secure in the strongest sense (existentially unforgeable against adaptive chosen message attacks) in the random oracle model under the approximate e-th root assumption which is an approximate version of the RSA assumption.

The digital signature scheme described in this contribution is obtained by combining two results: one [5] is by Okamoto, and the other [4] by Fujisaki and Okamoto.

PostScript File (216K)
Zipped Postscript File (52K)
Adobe Acrobat (.pdf) File (118K)

A discussion of the security of this scheme can be found here.


EPOC and ESIGN
Tatsuaki Okamoto, February 2000.

This draft proposes a public-key encryption scheme, EPOC, and digital signature scheme, ESIGN, to IEEE P1363a. In this document, the description of EPOC is divided into three parts: one is new encryption primitives, IFEP-OU and IFDP-OU, known as OU (for "Okamoto-Uchiyama"), and two new encryption schemes, IFES2 and IFIES, based on the OU primitives, known as EPOC-1 and EPOC-2 respectively. ESIGN is described as a new signature primitive, IFSP-ESIGN and IFVP-ESIGN. The related description is shown in IFSSA .

PostScript File (386K)
Zipped PostScript File (82K)
Adobe Acrobat (.pdf) File (242K)


NTRU: A Public Key Cryptosystem
Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, August 1999.
Presented at the August 1999 and October 1999 meetings.

This purpose of this paper is to submit the NTRU public key cryptosystem for consideration for inclusion into the P1363a standard.

Compared to other public key cryptosystems at roughly equivalent levels of security, NTRU offers: more efficient encryption and decryption, in both hardware and software implementations; much faster key generation, allowing the use of ``disposable'' keys (because keys are computationally ``cheap'' to create).

NTRU was originally presented by Jeffrey Hoffstein in the rump session at CRYPTO '96, and was published in 1998. Since that time, NTRU Cryptosystems, Inc. has issued a number of technical reports. In some cases, these reports have described amplifications on the techniques in in order to deal with new attacks (e.g., to deal with issues of plaintext awareness). In other cases, these reports have described fast algorithms for carrying out some of the computations required by NTRU. In this document, we have freely copied from the original paper introducing NTRU and other NTRU Cryptosystems, Inc. publications whenever appropriate.

PostScript File (526K)
Zipped PostScript File (111K)
Adobe Acrobat (.pdf) File (268K)


EPOC-3: Efficient Probabilistic Public-Key Encryption (Version 2)
Tatsuaki Okamoto and David Pointcheval, May 23, 2000.

We describe a novel version of the public-key cryptosystems EPOC (Efficient Probabilistic Public-Key Encryption). EPOC-3 is a public-key encryption system that uses the Okamoto-Uchiyama one-way trapdoor function and two random functions (hash functions) as well as any symmetric encryption scheme such as the one-time pad, or any classical block-cipher.

We furthermore define a new variant of the High-Residuosity problem, named the Gap-High-Residuosity problem which is likely stronger than the classical High-Residuosity problem.

PostScript File (237K)
Zipped PostScript File (56K)
Adobe Acrobat (.pdf) File (217K)


IQ-Cryptography Primitives and Schemes
Safuat Hamdy and Paul Dickinson, June 2004.
Submitted June 2004.

We propose public-key primitives and schemes based on IQ-related com-putational problems for standardisation and deployment. IQ refers to class groups of imaginary quadratic orders, and IQ-cryptography to schemes using these groups. IQ-cryptography offers another secure and efficient alternative to other forms of pub-lic key cryptography. Class groups of imaginary quadratic number fields are finite Abelian groups for which several apparently intractable problems exist. These prob-lems include computation of discrete logarithms, roots, and Diffie-Hellman secrets. Therefore, class groups admit to cryptographic schemes of Diffie-Hellman and ElGamal type.

In this article, we present two schemes in the context of IQ-cryptography from a practical standpoint with a view towards including them in a future IEEE standards document. The schemes are a variant of the Schnorr signature scheme and the Guillou-Quisquater signature scheme. We also include information on how to implement primitives necessary to perform IQ-cryptography in general.

Adobe Acrobat (.pdf) File (220K)

This page was last modified on Jul 18, 2004.

IEEE Logo IEEE Standards Logo P1363 Logo
IEEE Home Page IEEE Standards P1363 Home Page