Security analysis of public-key cryptosystems based on matrix action problem against quantum attack
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 r...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2023-03-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2023064/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850096357151342592 |
|---|---|
| author | Huawei HUANG |
| author_facet | Huawei HUANG |
| author_sort | Huawei HUANG |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e6d87ed7d18b410b82af457d5ce58ada |
| institution | DOAJ |
| issn | 1000-436X |
| language | zho |
| publishDate | 2023-03-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-e6d87ed7d18b410b82af457d5ce58ada2025-08-20T02:41:14ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2023-03-014422022659388042Security analysis of public-key cryptosystems based on matrix action problem against quantum attackHuawei HUANGAs 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.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2023064/Shor’s algorithmhidden subgroup problemsemigroup action problempublic-key cryptographyagainst quantum attack |
| spellingShingle | Huawei HUANG Security analysis of public-key cryptosystems based on matrix action problem against quantum attack Tongxin xuebao Shor’s algorithm hidden subgroup problem semigroup action problem public-key cryptography against quantum attack |
| title | Security analysis of public-key cryptosystems based on matrix action problem against quantum attack |
| title_full | Security analysis of public-key cryptosystems based on matrix action problem against quantum attack |
| title_fullStr | Security analysis of public-key cryptosystems based on matrix action problem against quantum attack |
| title_full_unstemmed | Security analysis of public-key cryptosystems based on matrix action problem against quantum attack |
| title_short | Security analysis of public-key cryptosystems based on matrix action problem against quantum attack |
| title_sort | security analysis of public key cryptosystems based on matrix action problem against quantum attack |
| topic | Shor’s algorithm hidden subgroup problem semigroup action problem public-key cryptography against quantum attack |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2023064/ |
| work_keys_str_mv | AT huaweihuang securityanalysisofpublickeycryptosystemsbasedonmatrixactionproblemagainstquantumattack |