Spectral approach to the communication complexity of multi-party key agreement - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2024

Spectral approach to the communication complexity of multi-party key agreement

Abstract

In multi-party key agreement protocols it is assumed that the parties are given correlated input data and should agree on a common secret key so that the eavesdropper cannot obtain any information on this key by listening to the communications between the parties. We consider the one-shot setting, when there is no ergodicity assumption on the input data. It is known that the optimal size of the secret key can be characterized in terms of the mutual information between different combinations of the input data sets, and the optimal key can be produced with the help of the omniscience protocol. However, the optimal communication complexity of this problem remains unknown. We show that the communication complexity of the omniscience protocol is optimal, at least for some complexity profiles of the input data, in the setting with restricted interaction between parties (the simultaneous messages model). We also provide some upper and lower bounds for communication complexity for other communication problems. Our proof technique combines information-theoretic inequalities and the spectral method.
Fichier principal
Vignette du fichier
2305.01355.pdf (389.2 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-04087184 , version 1 (11-10-2023)

Identifiers

Cite

Geoffroy Caillat-Grenier, Andrei Romashchenko. Spectral approach to the communication complexity of multi-party key agreement. STACS 2024 - 41st International Symposium on Theoretical Aspects of Computer Science, Mar 2024, Clermont-Ferrand, France. pp.22:1-22:19, ⟨10.4230/LIPIcs.STACS.2024.22⟩. ⟨lirmm-04087184⟩
55 View
19 Download

Altmetric

Share

Gmail Facebook X LinkedIn More