Information hiding using matroid theory

Thumbnail Image

Access rights

openAccess
publishedVersion

URL

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 (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)

Authors

Date

2021-08

Department

Department of Mathematics and Systems Analysis

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

DOI

10.1016/j.aam.2021.102205

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

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202108098297

Collections

[article-cris] Perustieteiden korkeakoulu / SCI