Decomposing attacks on asymmetric cryptography based on mapping compositions

Given the algebraic expression of the composition of two mappings how can o ne identify the two components? This is the problem of mapping decompositio n, of which the usual function-decomposition problem [8] is a special case. It was believed that this problem is intractable in general. Some public k ey cryptosystems (PKC) are based on the difficulty of this mathematical pro blem. Two types of such PKCs are FAPKC. proposed by Tao [16]. and the "2R-s chemes," proposed by Patarin and Goubin [11], [12]. FAPKC is based on compo sing finite automata (FA). while the "2R-schemes" use quadratic functions a s the components. In this paper the decomposition problem for FA and for qu adratic functions is investigated. Several methods for FA decomposing and o ne for quadratic functions are discovered. It is demonstrated that FA compo sition often exposes essential information about the components and that th e full expression of composition of quadratic functions should not be given in 2R-schemes.