Trapdoor one-way functions on elliptic curves and their application to shorter signatures and asymmetric encryption

• US 20060140400A1
• Filed: 11/14/2005
• Published: 06/29/2006
• Est. Priority Date: 11/11/2004
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Gallant, Robert P., Struik, Marinus, Brown, Daniel R.L., Vanstone, Scott A.
• Granted Patent: US 7,844,051 B2
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

The present invention provides a new trapdoor one-way function. In a general sense, some quadratic algebraic integer z is used. One then finds a curve E and a rational map defining [z] on E. The rational map [z] is the trapdoor one-way function. A judicious selection of z will ensure that [z] can be efficiently computed, that it is difficult to invert, that determination of [z] from the rational functions defined by [z] is difficult, and knowledge of z allows one to invert [z] on a certain set of elliptic curve points. Every rational map is a composition of a translation and an endomorphism. The most secure part of the rational map is the endomorphism as the translation is easy to invert. If the problem of inverting the endomorphism and thus [z] is as hard as the discrete logarithm problem in E, then the size of the cryptographic group can be smaller than the group used for RSA trapdoor one-way functions.

Claims

1. A cryptographic system operating on an elliptic curve E of order n, said cryptosystem having an endomorphism [z] corresponding to a quadratic algebraic integer z that has the form z²+uz+v=0, where u and v are secret integers, and v is relatively prime to n;

a public key operation to apply said endomorphism [z] to cryptographic data x to obtain modified data x′

; and

a private key operation to apply [−

w][u]+[z] to said modified data x′

in order to obtain said data x, where w is an integer and wv=1 mod n.

2. A cryptographic system according to claim 1 wherein said integer z is a complex number having real and imaginary components.

3. A cryptographic system according to claim 1 wherein said endomorphism [z] is represented as a rational map.

4. A cryptographic system according to claim 1 wherein said cryptographic data x comprises a message m, said public key operation operates to encrypt said message m to obtain an encrypted message m′

, and said private key operation operates to decrypt said encrypted message m′

to obtain said message m, said public key operation performed by a first entity and said private key operation performed by a second entity, said first and second entities being part of said cryptographic system.

5. A cryptographic system according to claim 1 wherein said data x′

comprises a message m for signature by a first entity of said cryptographic system, said private key operation operates on said message m to obtain a signature s, and said public key operation operates on said signature s by a second entity of said cryptographic system to verify said signature, said message m being originally generated by said second entity.

6. A cryptographic system according to claim 5 wherein said message m is generated from a hash function applied to an original message M.

7. A cryptographic system according to claim 1 wherein said cryptographic data x comprises a plurality of messages to receive a signature by a first entity of said cryptographic system, said private key operation operating on a combination of said plurality of messages to obtain said signature, and said public key operation being used by a second entity of said cryptographic system to verify said signature and thereby verify each said plurality of messages.

8. A method for performing cryptographic operations in a cryptographic system operating on an elliptic curve E of order n, said method comprising the steps of deriving an endomorphism [z] corresponding to a quadratic algebraic integer z that has the form z²+uz+v=0, where u and v are secret integers, and v is relatively prime to n;

applying a public key operation using said endomorphism [z] to cryptographic data x to obtain modified data x′

; and

applying a private key operation using [−

w][u]+[z] to said modified data x′

in order to obtain said data x, where w is an integer and wv=1 mod n.

9. A method according to claim 8 wherein said integer z is a complex number having real and imaginary components.

10. A method according to claim 8 wherein said endomorphism [z] is represented as a rational map.

11. A method according to claim 8 wherein said cryptographic data x comprises a message m, application of said public key operation encrypts said message m to obtain an encrypted message m′

, and application of said private key operation decrypts said message m from said encrypted message m′

.

12. A method according to claim 8 wherein said data x′

comprises a message m for signature;

said private key operation operates on said message m to obtain a signature s, and said public key operation operates on said signature s to verify same.

13. A method according to claim 12 wherein said message m is generated from a hash function applied to an original message M.

14. A method according to claim 8 wherein said cryptographic data x comprises a plurality of messages to receive a signature, said private key operation operates on a combination of said plurality of messages to obtain said signature, and said public key operation operating on said signature to verify same and thereby verify each said plurality of messages.

15. A method according to claim 8 wherein said data x comprises a message to be signed by a plurality of signers, said private key operation comprising a plurality of operations corresponding to each said signer, said private key operations being applied successively to said message to obtain a signature, said public key operation comprising a plurality of operations corresponding to each said signer, said public key operations being applied successively in opposite order to said private key operations to verify said signature.