IEEE P1363a: Provably secure signatures


The Korean Certificate-based Digital Signature Algorithm
KCDSA Task Force Team, August 1998.
Presented at the August 1998 meeting.

As a contribution to IEEE P1363a, we propose a provably secure digital signature algorithm called the Korean Certificate-based Digital Signature Algorithm (KCDSA, in short) and its elliptic curve variant (EC-KCDSA). We believe that the proposed signature schemes are more advantageous than DSA/EC-DSA in both security and efficiency. No patent related with KCDSA/EC-KCDSA has been submitted, and there are no known limitation and disadvantage. This paper describes these signature algorithms and discusses their security and efficiency aspects.

PostScript File (292K)
Zipped Postscript File (76K)
Adobe Acrobat (.pdf) File (238K)


PSS: Provably Secure Encoding Method for Digital Signatures
Mihir Bellare and Phillip Rogaway, August 1998.
Presented at the
August 1998 meeting.

We describe two encoding methods: EMSA-PSS, for signing with appendix, and EMSR-PSS, for signing with message recovery. These encodings are appropriate for signatures based on the RSA or Rabin/Williams primitive. The methods are as simple and efficient as the methods in the current P1363 draft (based on X9.31 and ISO 9796), but they have better demonstrated security. In particular, treating the underlying hash function as ideal, EMSA-PSS and EMSR-PSS give rise to provably-secure schemes: the ability to forge implies the ability to invert the underlying trapdoor permutation. In fact, when the underlying primitive is RSA, the schemes are not only provably secure, but are so in a tight way: the ability to forge with a certain amount of computational resources implies the ability to invert RSA (on the same size modulus) with essentially the same computational resources. Additional benefits are described in the body of this paper.

The methods described in this contribution are from our Eurocrypt 96 paper, The exact security of digital signatures--- How to sign with RSA and Rabin.

PostScript File of the Submission (501K)
PostScript File of the Eurocrypt paper (590K)
Zipped Postscript File of the Submission (103K)
Zipped Postscript File of the Eurocrypt paper (131K)
Adobe Acrobat (.pdf) File of the Submission (250K)
Adobe Acrobat (.pdf) File of the Eurocrypt paper (311)


This site was last modified on March 14, 2000.
IEEE Logo IEEE Standards Logo P1363 Logo
IEEE Home Page IEEE Standards P1363 Home Page