Information hiding using matroid theory
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2021-08
Major/Subject
Mcode
Degree programme
Language
en
Pages
18
Series
Advances in Applied Mathematics, Volume 129
Abstract
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.Description
Funding Information: We thank Camilla Hollanti for advising during this project. We thank Amy Wiebe, Felipe Rincón, Mateusz Michalek and Federico Ardila for helpful discussions about matroids. Kuznetsova was partially supported by the Academy of Finland Grant 323416 and Aalto Free Mover Scholarship. Funding Information: We thank Camilla Hollanti for advising during this project. We thank Amy Wiebe, Felipe Rinc?n, Mateusz Michalek and Federico Ardila for helpful discussions about matroids. Kuznetsova was partially supported by the Academy of Finland Grant 323416 and Aalto Free Mover Scholarship. Publisher Copyright: © 2021 The Author(s)
Keywords
Abstract simplicial complex, Derived matroid, Linear code, Private information retrieval
Other note
Citation
Freij-Hollanti , R & Kuznetsova , O 2021 , ' Information hiding using matroid theory ' , Advances in Applied Mathematics , vol. 129 , 102205 . https://doi.org/10.1016/j.aam.2021.102205
