Paper 2017/1175

Short Solutions to Nonlinear Systems of Equations

Alan Szepieniec and Bart Preneel

Abstract

This paper presents a new hard problem for use in cryptography, called Short Solutions to Nonlinear Equations (SSNE). This problem generalizes the Multivariate Quadratic (MQ) problem by requiring the solution be short; as well as the Short Integer Solutions (SIS) problem by requiring the underlying system of equations be nonlinear. The joint requirement causes common solving strategies such as lattice reduction or Gröbner basis algorithms to fail, and as a result SSNE admits shorter representations of equally hard problems. We show that SSNE can be used as the basis for a provably secure hash function. Despite failing to find public key cryptosystems relying on SSNE, we remain hopeful about that possibility.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Number Theory Methods in Cryptology - NuTMiC 2017
Keywords
signature schemehard problempost-quantumMQSISSSNEhash function
Contact author(s)
alan szepieniec @ esat kuleuven be
History
2017-12-06: received
Short URL
https://ia.cr/2017/1175
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1175,
      author = {Alan Szepieniec and Bart Preneel},
      title = {Short Solutions to Nonlinear Systems of Equations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1175},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1175}},
      url = {https://eprint.iacr.org/2017/1175}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.