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^*

^*Tämän työn vastaava kirjoittaja

Matematiikan ja systeemianalyysin laitos

Tutkimustuotos: Lehtiartikkeli › Article › Scientific › vertaisarvioitu

54 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Artikkeli	102205
Sivumäärä	18
Julkaisu	Advances in Applied Mathematics
Vuosikerta	129
DOI - pysyväislinkit	https://doi.org/10.1016/j.aam.2021.102205
Tila	Julkaistu - elok. 2021
OKM-julkaisutyyppi	A1 Julkaistu artikkeli, soviteltu

Pääsy asiakirjaan

10.1016/j.aam.2021.102205Lisenssi: CC BY

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

OpenUrl-saatavuus

Koko teksti

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

Algebraic geometry of hidden variable models in statistics
Kubjas, K., Ardiyansyah, M., Boege, T., Kuznetsova, O., Lindy, E., Sodomaco, L., Henriksson, O. & Metsälampi, L.
01/09/2019 → 31/08/2023
Projekti: Academy of Finland: Other research funding

Siteeraa tätä

@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

VL - 129

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

M1 - 102205

ER -

Information hiding using matroid theory

Abstrakti

Pääsy asiakirjaan

OpenUrl-saatavuus

Muut tiedostot ja linkit

Sormenjälki

Projektit

Algebraic geometry of hidden variable models in statistics

Siteeraa tätä