International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of an Authentication Scheme Using Truncated Polynomials

Authors:
Markus Grassl
Rainer Steinwandt
Download:
URL: http://eprint.iacr.org/2008/245
Search ePrint
Search Google
Abstract: An attack on a recently proposed authentication scheme of Shpilrain and Ushakov is presented. The public information allows the derivation of a system of polynomial equations for the secret key bits. Our attack uses simple elimination techniques to distill linear equations. For the proposed parameter choice, the attack often finds secret keys or alternative secret keys within minutes with moderate resources.
BibTeX
@misc{eprint-2008-17922,
  title={Cryptanalysis of an Authentication Scheme Using Truncated Polynomials},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / cryptanalysis, authentication scheme,  multivariate polynomials},
  url={http://eprint.iacr.org/2008/245},
  note={ rsteinwa@fau.edu 14029 received 30 May 2008},
  author={Markus Grassl and Rainer Steinwandt},
  year=2008
}