The Intersection of Matroid Theory and Cryptography (Discrete Mathematics, Coding Theory, Information Theory, and Computation)

Reference No.	2026a022
Type/Category	Grant for Young Researchers and Students-Workshop (II)
Title of Research Project	The Intersection of Matroid Theory and Cryptography (Discrete Mathematics, Coding Theory, Information Theory, and Computation)
Principal Investigator	IMAMURA, Koji（Research and Education Institute for Semiconductors and Informatics, Kumamoto University・Project-Based Assistant Professor）
Research Period
Keyword(s) of Research Fields	matroids, error-correcting codes, graphs, hyperplane arrangements, cryptography, secret sharing, secure computation, information security
Abstract for Research Report	This workshop will explore the interface between matroid and polymatroid theory—abstract frameworks for linear and algebraic independence—and the core theories in cryptography and information security: coding theory, information theory, and computational complexity. Every linear code naturally gives rise to a representable matroid, and it is well known that the weight distributions (or the weight enumerator) is connected to matroid invariants such as the Tutte polynomial. At the same time, computing these invariants and deciding representability are generally hard problems. In secret sharing and secure computation (including MPC), access structures can sometimes be described in matroidal terms, and a substantial body of work relates representability to the existence of efficient secret sharing schemes. However, there is a growing need for a cross-disciplinary synthesis of these insights as well as for the development of new concrete examples. Moreover, entropy functions behave as polymatroids and arise in quantitative assessments of information leakage and in limit analyses of network-type protocols. Accordingly, the workshop aims to develop a common language that enables mutual translation between structural matroid theory and cryptographic security notions, and to share examples, computational methods, and open problems. More specifically, we aim to: (i) an organized picture of computable classes of polynomial invariants and of algorithmic challenges arising from the code–matroid correspondence; (ii) new examples and counterexamples concerning matroid-derived access structures and linear constructions; and (iii) perspectives on information-theoretic security evaluation using polymatroid inequalities. We will invite a broad range of researchers from both fields and neighboring areas (graphs, hyperplane arrangements, optimization, MPC/zero-knowledge proofs, network coding, etc.), and we expect as an outcome a curated list of research problems that can be carried forward into future short-term collaborations.
Organizing Committee Members (Workshop) Participants (Short-term Joint Usage)	NUIDA, Koji（Institute of Mathematics for Industry, Kyushu University・Professor） IKEMATSU, Yasuhiko（Institute of Mathematics for Industry, Kyushu University・Associate Professor） NAKASHIMA, Norihiro（Department of Mathematics, Nagoya Institute of Technology・Associate Professor） SATAKE, Shohei（Research and Education Institute for Semiconductors and Informatics, Kumamoto University・Associate Professor） NAGAMINE, Takanori（Department of Mathematics, Nihon University・Assistant Professor） SAITO, Takuya（Institute for Chemical Reaction Design and Discovery, Hokkaido University・Specially Appointed Assistant Professor）