Information hiding using matroid theory

Ragnar Freij-Hollanti, Olga Kuznetsova*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
95 Downloads (Pure)


Inspired by problems in Private Information Retrieval, we consider the setting where two users need to establish a communication protocol to transmit a secret without revealing it to external observers. This is a question of how large a linear code can be, when it is required to agree with a prescribed code on a collection of coordinate sets. We show how the efficiency of such a protocol is determined by the derived matroid of the underlying linear communication code. Furthermore, we provide several sufficient combinatorial conditions for when no secret transmission is possible.

Original languageEnglish
Article number102205
Number of pages18
JournalAdvances in Applied Mathematics
Publication statusPublished - Aug 2021
MoE publication typeA1 Journal article-refereed


  • Abstract simplicial complex
  • Derived matroid
  • Linear code
  • Private information retrieval


Dive into the research topics of 'Information hiding using matroid theory'. Together they form a unique fingerprint.

Cite this