November 8th: Ryann Cartor

All in the C* Family

Ryann Cartor – Clemson University

The cryptosystem C*, first proposed and studied by Matsumoto and Imai and introduced in EUROCRYPT ’88, is the predecessor of all of the so called “big field” schemes of multivariate cryptography.  This scheme has since been broken, which has led to the introduction of modifiers. The introduction of the numerous modifiers of multivariate schemes have produced several variants that stay faithful to the central structure of the original.  From the tumultuous history of C* derivatives we now see only a very few survivors in the cryptonomy. In this work, we revisit the roots of multivariate cryptography, investigating the viability of C* schemes, in general, under the entire multidimensional array of the principal modifiers.  We reveal that there is a nontrivial space of combinations of modifiers that produce viable schemes resistant to all known attacks.  This solution space of seemingly secure C* variants offers trade-offs in multiple dimensions of performance, revealing a family that can be optimized for disparate applications.