Paper 2014/399

An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme

Dustin Moody, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
multivariate public key cryptographydifferentialinvariantencryption
Contact author(s)
daniel smith @ nist gov
History
2014-06-02: received
Short URL
https://ia.cr/2014/399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/399,
      author = {Dustin Moody and Ray Perlner and Daniel Smith-Tone},
      title = {An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2014/399},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/399}},
      url = {https://eprint.iacr.org/2014/399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.