Security analysis of public-key cryptosystems based on matrix action problem against quantum attack - Huawei HUANG (Tongxin xuebao)
As a generalization of the discrete logarithm problem, semigroup action problem has important applications in the design of public-key cryptography.Public-key cryptosystems based on action problem of integer matrix semigroups on the direct product of commutative groups were analyzed.The matrix was regarded as the exponent of direct product elements, and this class of matrix action had the exponential rules similar to group.It was proved that if the matrix action was injective or the number of generators of the hidden subgroup was less than or equal to the square of the order of the matrix, the matrix action problem could be reduced in polynomial time to the hidden subgroup problem of the direct sum of the additive group of the matrices.And it was proved that commutative matrix action problem could also be reduced to hidden subgroup problem of the direct sum of the additive group of the matrices in polynomial time.The cryptosystems based on this class of matrix action problem cannot against quantum attacks.This conclusion has theoretical significance in the design of public-key cryptography against quantum attacks.