Home // SECURWARE 2014, The Eighth International Conference on Emerging Security Information, Systems and Technologies // View article

Linearity Measures for Multivariate Public Key Cryptography

Authors:
Simona Samardjiska
Danilo Gligoroski

Keywords: Strong (s, t)-linearity; (s, t)-linearity; MinRank; good keys; separation keys.

Abstract:
We propose a new general framework for the security of Multivariate Quadratic (MQ) public key schemes with respect to attacks that exploit the existence of linear subspaces. We adopt linearity measures that have been used traditionally to estimate the security of symmetric cryptographic primitives, namely, the nonlinearity measure for vectorial functions introduced by Nyberg, and the (s, t)-linearity measure introduced recently by Boura and Canteaut. We redefine some properties of MQ cryptosystems in terms of these known symmetric cryptography notions, and show that our new framework is a compact generalization of several known attacks in MQ cryptography against single field schemes. We use the framework to explain various pitfalls regarding the successfulness of these attacks. Finally, we argue that linearity can be used as a solid measure for the susceptibility of MQ schemes to these attacks, and also as a necessary tool for prudent design practice in MQ cryptography.

Pages: 157 to 166

Copyright: Copyright (c) IARIA, 2014

Publication date: November 16, 2014

Published in: conference

ISSN: 2162-2116

ISBN: 978-1-61208-376-6

Location: Lisbon, Portugal

Dates: from November 16, 2014 to November 20, 2014