探索拓扑编码中的图格与传统格的联系

doi:10.3778/j.issn.1673-9418.2010072

摘要/Abstract

摘要：

已知不存在解决某些格困难问题的多项式量子算法，无色图格和着色图格是受格理论启发而产生的多学科交叉的产物。拓扑编码中的一个无色图格或着色图格是建立在图的运算和一组顶点不交的连通图或连通着色图构成的图格基上。基于口令认证或数字文件加密，介绍数字串拓扑认证问题，用拓扑编码给出一种非对称加密系统。拓扑编码可以形成一个公钥对应多个私钥，多个公钥对应多个私钥的非对称加密系统；拓扑编码中的拓扑认证需要两个不同领域的数学知识，而且可以产生指数级别的算法。基于图的边连接运算、顶点重合运算等运算，研究了具有优美全着色的着色图格基存在性，建立了边连接图格和F-图格等无穷图格，并证明这些图格对优美全着色具有封闭性。定义了特殊着色图的拓扑向量，建立了图格与非负整数传统格之间的一个联系，为抗量子计算提供可行的技术；说明没有多项式算法解决数字串分解问题，又因为图同构问题是NP-困难，从而拓扑编码建立的图格具有抗超大计算机和量子计算机的计算功能。

关键词: 格, 图格, 全着色, 优美标号, 拓扑编码, 网络安全

Abstract:

It is known that there are no polynomial quantum algorithms to solve some lattice difficult problems. Uncolored graphic lattice and colored graphic lattice are the products of multidisciplinary intersection inspired by lattice theory. A uncolored graphic lattice or a colored graphic lattice in topological coding is based on some graph operations and a set of disjoint connected graphs or disjoint connected colored graphs. Based on password authentication or digital file encryption, this paper introduces the number-based string topological authentication problem, and gives an asymmetric encryption system by topological coding. Topological coding can form an asymmetric encryption system with one public key corresponding to two or more private keys and, more public keys corresponding to more private keys. Topology authentication in topology coding requires two different fields of mathematical knowledge and can produce exponential level algorithm. Based on the edge-joining operation and vertex-coinciding operation of graphs, the existence of colored graphic lattice admitting graceful total colorings is shown, and graphic lattice and F-graphic lattice are established with infinite elements closed to graceful total coloring. Topological vectors for special coloring graphs are defined, and a connection between graphic lattice and non-negative integer traditional lattice is built up to provide a feasible technique for quantum resistance calculation, since there is no polynomial algorithm for solving number-based strings up to now. Because graph isomorphism problem is NP-hard, topological coding lattice has the function of resisting supercomputer and quantum computer.

Key words: lattice, graphic lattice, total coloring, graceful labelling, topological coding, network security

张明军，杨思华，姚兵. 探索拓扑编码中的图格与传统格的联系[J]. 计算机科学与探索, 2021, 15(11): 2171-2183.

ZHANG Mingjun, YANG Sihua, YAO Bing. Exploring Relationship Between Traditional Lattices and Graph Lattices of Topological Coding[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2171-2183.

参考文献

[1] BERNSTEIN D J, BUCHMANN J, DAHMEN E. Post-quantum cryptography[M]. Berlin, Heidelberg: Springer, 2009.
[2] WANG X Y, LIU M J. Survey of lattice-based cryptography[J]. Journal of Cryptologic Reseatch, 2014, 1(1): 13-27.
王小云, 刘明洁. 格密码学研究[J]. 密码学报, 2014, 1(1): 13-27.
[3] WANG H Y, YAO B, SU J, et al. Number-based strings/passwords from imaginary graphs of topological coding for encryption[C]//Proceedings of the 2021 IEEE 4th Advanced Information Management, Communicates, Electronic and Automation Control Conference. Piscataway: IEEE, 2021: 497-501.
[4] YAO B, WANG H Y, SU J, et al. Graphic lattices for con-structing high-quality networks[C]//Proceedings of the 2020 IEEE 5th Information Technology and Mechatronics Engin-eering Conference, Chongqing, Jun 12-14, 2020. Piscataway: IEEE, 2020: 1726-1730.
[5] WANG H Y, XU J, YAO B. Exploring new cryptographical construction of complex network data[C]//Proceedings of the IEEE 1st International Conference on Data Science in Cyberspace, Changsha, Jun 13-16, 2016. Washington: IEEE Computer Society, 2016: 155-160.
[6] WANG H Y, XU J, YAO B. The key-models and their lock-models for designing new labellings of networks[C]//Proceedings of the 2016 IEEE Advanced Information Management, Com-municates, Electronic and Automation Control Conference, Xi??an, Oct 3-5, 2016. Piscataway: IEEE, 2016: 5565-5568.
[7] YAO B, YANG C, YAO M. Coding techniques from distinguishing colorings in topological coding[C]//Proceedings of the 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference, Chongqing, Dec 11-13, 2020. Piscataway: IEEE, 2020: 77-83.
[8] Encoding of Chinese characters: GB2312-80[S]. The Com-pilation of National Standards for Character Sets and Infor-mation Coding. China Standard Press, 1998.
[9] GALLIAN J A. A dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics, 2016, 18: #DS6.
[10] YAO B, SUN H, WANG H Y. Graph colorings based on n-dimension digital-based strings for information security[C]//Proceedings of the 2020 IEEE International Conference on Information Technology, Big Data and Artificial Intelligence, Chongqing, Nov 6-8, 2020. Piscataway: IEEE, 2020: 458-462.
[11] SHEPPARD D A. The factorial representation of balanced labeled graphs[J]. Discrete Mathematics, 1976, 15(4): 379-388.
[12] DEO N, NIKOLOSKI Z, SURAWEERA F. Generation of graceful trees[C]//Proceedings of the 33rd Southeastern Inter-national Conference on Combinatorics, Graph Theory and Computing, Boca, 2002: 4-8.
[13] YAO B. Graphic lattices and matrix lattices of topological coding[J]. arXiv:2005.03937, 2020.
[14] YAO B, WANG H Y. Graph homomorphisms based on particular total colorings of graphs and graphic lattices[J]. arXiv:2005. 02279v1, 2020.
[15] YAO B, ZHAO M M, ZHANG X H, et al. Topological coding and topological matrices toward network overall security[J]. arXiv:1909.01587v2, 2019.
[16] WANG H Y, YAO B, YAO M. Generalized edge-magic total labellings of models from researching networks[J]. Information Sciences, 2014, 279: 460-467.
[17] YAO B, MA F, WANG X M. Optimal design and randomly topological coloring of dynamic networks[C]//Proceedings of the IEEE 9th Joint International Information Technology and Artificial Intelligence Conference, Chongqing, Dec 11-13, 2020. Piscataway: IEEE, 2020: 226-231.
[18] YAO B, MU Y R, SUN H Z, et al. Algebraic groups for construction of topological graphic passwords in cryptography [C]//Proceedings of the 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference, Chongqing, Oct 12-14, 2018. Piscataway: IEEE, 2018: 2211-2216.
[19] WANG H Y, XU J, YAO B. Twin odd-graceful trees towards information security[J]. Procedia Computer Science, 2017, 107: 15-20.
[20] BONDY J A, MURTY U S. Graph theory[M]. Berlin, Hei-delberg: Springer, 2008.
[21] YAO B, WANG H Y, MA F, et al. On real-valued total colorings towards topological authentication in topological coding[C]//Proceedings of the 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, Chongqing, Jun 12-14, 2020. Piscataway: IEEE, 2020: 1751- 1756.
[22] YAO B, WANG H Y, SU J, et al. Especial total colorings towards multiple authentications in network encryption[C]//Proceedings of the 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, Chongqing, Jun 12-14, 2020. Piscataway: IEEE, 2020: 1617-1623.
[23] YAO B, MU Y R, SUN Y R, et al. Using Chinese characters to generate text-based passwords for information security[J]. arXiv:1907.05406v1, 2019.
[24] ZHANG M J, YANG S H, MU Y R, et al. Hanzi-TB-paws for helping Chinese people to memorize their passwords with longer bytes[C]//Proceedings of the 2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference, Chongqing, Oct 11-13, 2019. Piscataway: IEEE, 2019: 1418-1424.