An authentication scheme based on roots of sparse polynomials

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.


Published in:
Proceedings of the IEEE Information Theory Workshop, 2003, 159-162
Year:
2003
Keywords:
Laboratories:




 Record created 2007-01-16, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)