An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme

Published

October 3, 2014

Author(s)

Dustin Moody, Ray A. Perlner, Daniel C. 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 a structural key recovery attack which is asymptotically optimal among all known attacks (including algebraic attacks) on the original scheme and its generalizations.

Proceedings Title

Post-Quantum Cryptography (Lecture Notes in Computer Science)

Volume

8772

Conference Dates

October 1-3, 2014

Conference Location

Waterloo

Conference Title

6th International Conference on Post-Quantum Cryptography (PQCrypto 2014)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-319-11659-4_11

Keywords

differential, encryption, invariant, multivariate public key cryptography

Citation

Moody, D. , Perlner, R. and Smith-Tone, D. (2014), An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme, Post-Quantum Cryptography (Lecture Notes in Computer Science), Waterloo, -1, [online], https://doi.org/10.1007/978-3-319-11659-4_11 (Accessed September 30, 2025)