Paper 2014/703

Linearity Measures for MQ Cryptography

Simona Samardjiska and Danilo Gligoroski

Abstract

We propose a new general framework for the security of multivariate quadratic (\mathcal{MQ}) 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 at Eurocrypt '92, and the $(s, t)$--linearity measure introduced recently by Boura and Canteaut at FSE'13. We redefine some properties of \mathcal{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 \mathcal{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 \mathcal{MQ} schemes to these attacks, and also as a necessary tool for prudent design practice in \mathcal{MQ} cryptography.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. SECURWARE 2014
Keywords
Strong $(st)$--linearity$(st)$--linearityMinRankgood keysseparation keys
Contact author(s)
simonas @ item ntnu no
History
2014-09-05: received
Short URL
https://ia.cr/2014/703
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/703,
      author = {Simona Samardjiska and Danilo Gligoroski},
      title = {Linearity Measures for MQ Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2014/703},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/703}},
      url = {https://eprint.iacr.org/2014/703}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.