New Insight into the Isomorphism of Polynomials problem IP1S and its Use in Cryptography

Gilles Macario-Rat; Jérôme Plût; Henri Gilbert

Paper 2013/799

New Insight into the Isomorphism of Polynomials problem IP1S and its Use in Cryptography

Gilles Macario-Rat, Jérôme Plût, and Henri Gilbert

Abstract

This paper investigates the mathematical structure of the ``Isomorphism of Polynomial with One Secret'' problem (IP1S). Our purpose is to understand why for practical parameter values of IP1S most random instances are easily solvable (as first observed by Bouillaguet et al.). We show that the structure of the problem is directly linked to the structure of quadratic forms in odd and even characteristic. We describe a completely new method allowing to efficiently solve most instances. Unlike previous solving techniques, this is not based upon Gröbner basis computations.

Note: This is a major revision of the version to be published by Springer-Verlag in the proceedings of ASIACRYPT 2013 (not yet online at the date of the last edit of this note). In particular, the proof of the binary case has been significantly expanded.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in ASIACRYPT 2013
Keywords: secret-key cryptography multivariate IP1S
Contact author(s): jerome plut @ ssi gouv fr
History: 2013-12-01: received
Short URL: https://ia.cr/2013/799
License: CC BY

BibTeX

@misc{cryptoeprint:2013/799,
      author = {Gilles Macario-Rat and Jérôme Plût and Henri Gilbert},
      title = {New Insight into the Isomorphism of Polynomials problem IP1S and its Use in Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2013/799},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/799}},
      url = {https://eprint.iacr.org/2013/799}
}