Information hiding using matroid theory

Ragnar Freij-Hollanti; Olga Kuznetsova

doi:10.1016/j.aam.2021.102205

Information hiding using matroid theory

Ragnar Freij-Hollanti, Olga Kuznetsova^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

1 Citation (Scopus)

130 Downloads (Pure)

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.

Original language	English
Article number	102205
Number of pages	18
Journal	Advances in Applied Mathematics
Volume	129
DOIs	https://doi.org/10.1016/j.aam.2021.102205
Publication status	Published - Aug 2021
MoE publication type	A1 Journal article-refereed

Keywords

Abstract simplicial complex
Derived matroid
Linear code
Private information retrieval

Access to Document

10.1016/j.aam.2021.102205Licence: CC BY

Information hiding using matroid theory.1-s2.0-S0196885821000439-mainFinal published version, 326 KBLicence: CC BY

Cite this

@article{ec2fb32a647149d2b8608fedfcc034dd,

title = "Information hiding using matroid theory",

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.",

keywords = "Abstract simplicial complex, Derived matroid, Linear code, Private information retrieval",

author = "Ragnar Freij-Hollanti and Olga Kuznetsova",

note = "Funding Information: We thank Camilla Hollanti for advising during this project. We thank Amy Wiebe, Felipe Rinc{\'o}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: {\textcopyright} 2021 The Author(s)",

year = "2021",

month = aug,

doi = "10.1016/j.aam.2021.102205",

language = "English",

volume = "129",

journal = "Advances in Applied Mathematics",

issn = "0196-8858",

publisher = "Academic Press",

}

TY - JOUR

T1 - Information hiding using matroid theory

AU - Freij-Hollanti, Ragnar

AU - Kuznetsova, Olga

N1 - 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)

PY - 2021/8

Y1 - 2021/8

N2 - 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.

AB - 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.

KW - Abstract simplicial complex

KW - Derived matroid

KW - Linear code

KW - Private information retrieval

UR - http://www.scopus.com/inward/record.url?scp=85110322078&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2021.102205

DO - 10.1016/j.aam.2021.102205

M3 - Article

AN - SCOPUS:85110322078

SN - 0196-8858

VL - 129

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

M1 - 102205

ER -

Information hiding using matroid theory

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

-: Algebraic geometry of hidden variable models in statistics

Cite this

Information hiding using matroid theory

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

-: Algebraic geometry of hidden variable models in statistics

Cite this