Use of isogenies for design of cryptosystems
Techniques are disclosed to provide public-key encryption systems. More particularly, isogenies of Abelian varieties (e.g., elliptic curves in one-dimensional cases) are utilized to provide public-key encryption systems. For example, the isogenies permit the use of multiple curves instead of a single curve to provide more secure encryption. The techniques may be applied to digital signatures and/or identity based encryption (IBE) solutions. Furthermore, the isogenies may be used in other applications such as blind signatures, hierarchical systems, and the like. Additionally, solutions are disclosed for generating the isogenies.
1. A method comprising:
generating an isogeny that maps a plurality of points from a first elliptic curve onto a second elliptic curve, wherein the isogeny is generated using a technique selected from a group comprising complex multiplication generation, modular generation, linearly independent generation, and combinations thereof;
publishing a public key corresponding to the isogeny;
encrypting a message using a encryption key corresponding to the isogeny; and
decrypting the encrypted message using a decryption key corresponding to the isogeny, wherein the decrypting is performed by bilinear pairing and wherein the bilinear pairing is a pairing selected from a group comprising Weil pairing, Tate pairing, and square pairing; and
using a trace map to shorten points on an Abelian variety.
2. A method as recited by claim 1 , wherein at least one of the encryption key or the decryption key is a private key, the private key being a dual isogeny of the isogeny.
3. A method as recited by claim 1 , wherein the generating maps a plurality of points from a first elliptic curve onto a plurality of elliptic curves.
4. A method as recited by claim 1 , wherein the method is applied using Abelian varieties.
5. A method as recited by claim 1 , wherein the method signs the message.
6. A method as recited by claim 1 , wherein the method provides identity based encryption.
7. A method as recited by claim 1 , further comprising composing a plurality of modular isogenies to provide the isogeny without revealing any intermediate curves.
8. A method as recited by claim 1 , further comprising using a trace map down to a base field to shorten points on an elliptic curve mapped by the isogeny.
9. A method comprising:
publishing a public key corresponding to an isogeny that maps a plurality of points from a first elliptic curve onto a second elliptic curve, wherein the isogeny is generated using a technique selected from a group comprising complex multiplication generation, modular generation, linearly independent generation, and combinations thereof; and
decrypting an encrypted message using a decryption key corresponding to the isogeny, wherein the decryption is performed by bilinear pairing and wherein the bilinear pairing is a pairing selected from a group comprising Weil pairing, Tate pairing, and square pairing.
10. A method as recited by claim 9 , wherein the decryption key is a dual isogeny of the isogeny.
11. A method as recited by claim 9 , wherein the isogeny maps a plurality of points from a first elliptic curve onto a plurality of elliptic curves.
12. A method as recited by claim 9 , wherein the method is applied using Abelian varieties.
13. A method as recited by claim 9 , wherein the method signs the message.
14. A method as recited by claim 9 , wherein the method provides identity based encryption.
15. A method as recited by claim 9 , further comprising using a trace map down to a base field to shorten points on an elliptic curve mapped by the isogeny.
16. A system comprising:
a first processor;
a first system memory coupled to the first processor, the first system memory storing a public key corresponding to an isogeny that maps a plurality of points from a first elliptic curve onto a second elliptic curve;
a second processor;
a second system memory coupled to the second processor, the second system memory storing an encrypted message and a decryption key corresponding to the isogeny to decrypt the encrypted message, wherein the decryption is performed by bilinear pairing and wherein the bilinear pairing is a pairing selected from a group comprising Weil pairing, Tate pairing, and square pairing,
wherein the encrypted message is encrypted using an encryption key.
17. A system as recited by claim 16 , wherein at least one of the encryption key or the decryption key is a private key, the private key being a dual isogeny of the isogeny.
18. A system as recited by claim 16 , wherein the isogeny maps a plurality of points from a first elliptic curve onto a plurality of elliptic curves.
19. One or more computer-readable media having instructions stored thereon that, when executed, direct a machine to perform acts comprising:
publishing a public key corresponding to an isogeny that maps a plurality of points from a first elliptic curve onto a second elliptic curve, wherein the isogeny is generated using a technique selected from a group comprising complex multiplication generation, modular generation, linearly independent generation, and combinations thereof; and
decrypting an encrypted message using a decryption key corresponding to the isogeny, wherein the decrypting is performed by bilinear pairing and wherein the bilinear pairing is a pairing selected from a group comprising Weil pairing, Tate pairing, and square pairing.
20. One or more computer-readable media as recited by claim 19 , wherein the decryption key is a private key, the private key being a dual isogeny of the isogeny.
21. One or more computer-readable media as recited by claim 19 , wherein the isogeny maps a plurality of points from a first elliptic curve onto a plurality of elliptic curves.
22. One or more computer-readable media as recited by claim 19 , wherein the acts are applied using Abelian varieties.
23. One or more computer-readable media as recited by claim 19 , wherein the acts further comprise using a trace map down to a base field to shorten points on an elliptic curve mapped by the isogeny.
24. One or more computer-readable media as recited by claim 19 , wherein the acts further comprise composing a plurality of modular isogenies to provide the isogeny without revealing any intermediate curves.
25. One or more computer-readable media as recited by claim 19 , wherein the acts further comprise using a trace map to shorten points on an Abelian variety.
26. One or more computer-readable media as recited by claim 19 , wherein the acts sign the message.
27. One or more computer-readable media as recited by claim 19 , wherein the acts provide identity based encryption.