NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme
Published
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)
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 October 20, 2025)