An authentication scheme based on roots of sparse polynomials

J. Von Zur Gathen, A. Shokrollahi, I. Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

14 Downloads (Pure)


We describe an authentication scheme whose security is based on the hardness of finding roots of systems of sparse polynomial equations in many variables and of high degree. One of the new ideas is the use of many keys. In one authentication session, a small amount of information about only one of them, chosen randomly, is released; this may be useful in other situations as well. Although the practicality of this scheme has still to be investigated, we believe that the new ideas described here may be of independent interest.

Original languageEnglish
Title of host publicationProceedings 2003 IEEE Information Theory Workshop
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages4
ISBN (Electronic)0780377990, 9780780377998
Publication statusPublished - Apr 2003
Event2003 IEEE Information Theory Workshop, ITW - 2003 - Paris, France
Duration: 31 Mar 20034 Apr 2003


Other2003 IEEE Information Theory Workshop, ITW - 2003

Bibliographical note

Copyright 2003 IEEE. Reprinted from 2003 IEEE Information Theory Workshop : proceedings. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Macquarie University’s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to By choosing to view this document, you agree to all provisions of the copyright laws protecting it.


Dive into the research topics of 'An authentication scheme based on roots of sparse polynomials'. Together they form a unique fingerprint.

Cite this