A public key cryptosystem based on sparse polynomials

D Grant*, K Krastev, D Lieman, Igor Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution


This paper introduces a new type of cryptosystem which is based on sparse polynomials over finite fields. We evaluate its theoretic characteristics and give some security analysis. Some preliminary timings are presented as well, which compare quite favourably with published optimized RSA timings. We believe that similar ideas can be used in some other settings as well.

Original languageEnglish
Title of host publicationCoding theory, cryptography and related areas
EditorsJ Buchmann, T Hoholdt, H Stichtenoth, H TapiaRecillas
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Number of pages8
ISBN (Print)3540662480
Publication statusPublished - 2000
EventInternational Conference on Coding Theory, Cryptography and Related Areas - GUANAJUATO, Mexico
Duration: 20 Apr 199824 Apr 1998


ConferenceInternational Conference on Coding Theory, Cryptography and Related Areas

Cite this