Cryptology ePrint Archive: Report 2008/245

Cryptanalysis of an Authentication Scheme Using Truncated Polynomials

Markus Grassl and Rainer Steinwandt

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.

Category / Keywords: public-key cryptography / cryptanalysis, authentication scheme, multivariate polynomials

Date: received 30 May 2008

Contact author: rsteinwa at fau edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20080603:011943 (All versions of this report)

Short URL: ia.cr/2008/245

Discussion forum: Show discussion | Start new discussion