Cryptology ePrint Archive: Report 2014/399

An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme

Dustin Moody and Ray Perlner and Daniel Smith-Tone

Abstract: Historically, multivariate public key cryptography has been less than successful at offering encryption schemes which are both secure and efficient. At PQCRYPTO '13 in Limoges, Tao, Diene, Tang, and Ding introduced a promising new multivariate encryption algorithm based on a fundamentally new idea: hiding the structure of a large matrix algebra over a finite field. We present an attack based on subspace differential invariants inherent to this methodology. The attack is is a structural key recovery attack which is asymptotically optimal among all known attacks (including algebraic attacks) on the original scheme and its generalizations.

Category / Keywords: public-key cryptography / multivariate public key cryptography, differential, invariant, encryption

Date: received 30 May 2014

Contact author: daniel smith at nist gov

Available format(s): PDF | BibTeX Citation

Version: 20140602:070642 (All versions of this report)

Short URL: ia.cr/2014/399

Discussion forum: Show discussion | Start new discussion