Published in

Advances in Cryptology – EUROCRYPT 2008, p. 19-30

DOI: 10.1007/978-3-540-78967-3_2

Links

Tools

Export citation

Search in Google Scholar

Key Recovery on Hidden Monomial Multivariate Schemes

Proceedings article published in 2008 by Pierre-Alain Fouque, Gilles Macario-Rat, Jacques Stern
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Question mark in circle
Preprint: policy unknown
Upload
Question mark in circle
Postprint: policy unknown
Upload
Question mark in circle
Published version: policy unknown
Upload

Abstract

The problem we study in this paper is the key recovery prob- lem on the C schemes and generalizations where the quadratic mono- mial of C (the product of two linear monomials) is replaced by a prod- uct of three or more linear monomials. This problem has been further generalized to any multivariate polynomial hidden by two invertible lin- ear maps and named the Isomorphism of Polynomials (IP) problem by Patarin et al. Some cryptosystems have been built on this appearing hard problem such as a traitor tracing scheme proposed by Billet and Gilbert. Here we show that if the hidden multivariate monomial is a quadratic monomial, as in SFLASH, or a cubic (or higher) monomial as in the traitor tracing scheme, then it is possible to recover an equivalent secret key in polynomial time O(nd) where n is the number of variables and d is the degree of the public polynomials.