An authentication scheme based on roots of sparse polynomials

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

doi:10.1109/ITW.2003.1216719

An authentication scheme based on roots of sparse polynomials

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

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

26 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Proceedings 2003 IEEE Information Theory Workshop
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	159-162
Number of pages	4
ISBN (Electronic)	0780377990, 9780780377998
DOIs	https://doi.org/10.1109/ITW.2003.1216719
Publication status	Published - Apr 2003
Event	2003 IEEE Information Theory Workshop, ITW - 2003 - Paris, France Duration: 31 Mar 2003 → 4 Apr 2003

Other

Other	2003 IEEE Information Theory Workshop, ITW - 2003
Country/Territory	France
City	Paris
Period	31/03/03 → 4/04/03

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 [email protected]. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

Access to Document

10.1109/ITW.2003.1216719

Publisher version (open access).pdfFinal published version, 334 KB

Cite this

@inproceedings{92a5edd58aa94d21900979cb7383f6fc,

title = "An authentication scheme based on roots of sparse polynomials",

abstract = "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.",

author = "\{Von Zur Gathen\}, J. and A. Shokrollahi and I. Shparlinski",

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{\^a}€{\texttrademark}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 [email protected]. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.; 2003 IEEE Information Theory Workshop, ITW - 2003 ; Conference date: 31-03-2003 Through 04-04-2003",

year = "2003",

month = apr,

doi = "10.1109/ITW.2003.1216719",

language = "English",

pages = "159--162",

booktitle = "Proceedings 2003 IEEE Information Theory Workshop",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

Von Zur Gathen, J, Shokrollahi, A & Shparlinski, I 2003, An authentication scheme based on roots of sparse polynomials. in Proceedings 2003 IEEE Information Theory Workshop., 1216719, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 159-162, 2003 IEEE Information Theory Workshop, ITW - 2003, Paris, France, 31/03/03. https://doi.org/10.1109/ITW.2003.1216719

An authentication scheme based on roots of sparse polynomials. / Von Zur Gathen, J.; Shokrollahi, A.; Shparlinski, I.
Proceedings 2003 IEEE Information Theory Workshop. Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE), 2003. p. 159-162 1216719.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - An authentication scheme based on roots of sparse polynomials

AU - Von Zur Gathen, J.

AU - Shokrollahi, A.

AU - Shparlinski, I.

N1 - 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 [email protected]. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

PY - 2003/4

Y1 - 2003/4

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84939200181

U2 - 10.1109/ITW.2003.1216719

DO - 10.1109/ITW.2003.1216719

M3 - Conference proceeding contribution

AN - SCOPUS:84939200181

SP - 159

EP - 162

BT - Proceedings 2003 IEEE Information Theory Workshop

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

T2 - 2003 IEEE Information Theory Workshop, ITW - 2003

Y2 - 31 March 2003 through 4 April 2003

ER -

An authentication scheme based on roots of sparse polynomials

Abstract

Other

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this