Paper 2013/799 Original: eprint.iacr.org/2013/799 ↗
New Insight into the Isomorphism of Polynomials problem IP1S and its Use in Cryptography
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2013-12-01: last updated
- 2013-12-01: published
- Short URL
- https://ia.cr/2013/799
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2013/799}
}