Graphs, Codes, and Tensors: Connections and Cryptographic Applications

Zhang, Chuanqi

Graphs, Codes, and Tensors: Connections and Cryptographic Applications

Zhang, Chuanqi

Permalink

Publication Type:: Thesis
Issue Date:: 2025

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download thesisAdobe PDF (1.51 MB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, Chuanqi
dc.date.accessioned	2026-07-22T01:43:54Z
dc.date.available	2026-07-22T01:43:54Z
dc.date.issued	2025
dc.identifier.uri	http://hdl.handle.net/10453/195743
dc.description	University of Technology Sydney. Faculty of Engineering and Information Technology.	en_US.UTF-8
dc.description.abstract	This thesis explores problems in the context of graphs, linear codes, and tensors, three fundamental objects in mathematics and computer science, which are most evidently linked by reductions on their isomorphism testing problems: graph isomorphism reduces to monomial code equivalence (Grochow, CCC'12), which further reduces to tensor isomorphism (Grochow-Qiao, SIAM J. Comput.'23). In this thesis, we extend the study beyond isomorphisms, uncovering richer connections between properties of graphs and tensors. For example, we establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence. Building on this perspective, we also compare different linear-algebraic notions of expansion that are both generalized from expander graphs. After exploring these structural insights in theory, we turn to applications in cryptography, where we design novel primitives, including blind signature schemes and key exchange protocols, based on a new interpretation of monomial code equivalence using symmetric group actions. Overall, this work connects mathematical structures with cryptographic designs, offering both theoretical understanding and concrete applications.	en_US.UTF-8
dc.format	Thesis (PhD)
dc.language.iso	en_US	en_US.UTF-8
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	© 2025 Chuanqi Zhang
dc.rights	au.edu.uts.lib/nph
dc.title	Graphs, Codes, and Tensors: Connections and Cryptographic Applications	en_US.UTF-8
dc.type	Thesis
utslib.copyright.status	open_access	*

Abstract:

This thesis explores problems in the context of graphs, linear codes, and tensors, three fundamental objects in mathematics and computer science, which are most evidently linked by reductions on their isomorphism testing problems: graph isomorphism reduces to monomial code equivalence (Grochow, CCC'12), which further reduces to tensor isomorphism (Grochow-Qiao, SIAM J. Comput.'23). In this thesis, we extend the study beyond isomorphisms, uncovering richer connections between properties of graphs and tensors. For example, we establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence. Building on this perspective, we also compare different linear-algebraic notions of expansion that are both generalized from expander graphs. After exploring these structural insights in theory, we turn to applications in cryptography, where we design novel primitives, including blind signature schemes and key exchange protocols, based on a new interpretation of monomial code equivalence using symmetric group actions. Overall, this work connects mathematical structures with cryptographic designs, offering both theoretical understanding and concrete applications.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/195743