Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2305.01355 · Leibniz international proceedings in informatics

Spectral Approach to the Communication Complexity of Multi-Party Key Agreement

Geoffroy Caillat-Grenier, Andrei Romashchenko

Published May 2, 2023• 0 citations
arXivHTMLPDF

Abstract

We propose a linear algebraic method, rooted in the spectral properties of graphs, that can be used to prove lower bounds in communication complexity. Our proof technique effectively marries spectral bounds with information-theoretic inequalities. The key insight is the observation that, in specific settings, even when data sets $X$ and $Y$ are closely correlated and have high mutual information, the owner of $X$ cannot convey a reasonably short message that maintains substantial mutual information with $Y$. In essence, from the perspective of the owner of $Y$, any sufficiently brief message $m=m(X)$ would appear nearly indistinguishable from a random bit sequence. We employ this argument in several problems of communication complexity. Our main result concerns cryptographic protocols. We establish a lower bound for communication complexity of multi-party secret key agreement with unconditional, i.e., information-theoretic security. Specifically, for one-round protocols (simultaneous messages model) of secret key agreement with three participants we obtain an asymptotically tight lower bound. This bound implies optimality of the previously known omniscience communication protocol (this result applies to a non-interactive secret key agreement with three parties and input data sets with an arbitrary symmetric information profile). We consider communication problems in one-shot scenarios when the parties' inputs are not produced by any i.i.d. sources, and there are no ergodicity assumptions on the input data. In this setting, we found it natural to present our results using the framework of Kolmogorov complexity.

DOI
10.4230/lipics.stacs.2024.22

Related papers

Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory

Emirhan Gürpınar, Andrei Romashchenko

It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y , respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x , y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key, the size of which is much smaller than the mutual information between x and y . However, we discuss a natural class of x , y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses the spectral properties of appropriate graphs and the expander mixing lemma, as well as information-theoretic techniques, including constraint information inequalities and Muchnik’s conditional descriptions. A preliminary version of this article was published in the proceedings of MFCS 2020. In the present version, we give full proofs of all theorems and get rid of the assumption that the number of random bits used in the communication protocols is polynomial.

ACM Transactions on Computation Theory•May 17, 2024•2 citations

Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory

Emirhan Gürpınar, Andrei Romashchenko

It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x, y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key whose size is much smaller than the mutual information between x and y. On the other hand, we discuss examples of x, y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses spectral properties of appropriate graphs and the expander mixing lemma, as well as information theoretic techniques.

arXiv:2004.13411•Leibniz international proceedings in informatics•Jan 1, 2020•0 citations

Common Information in Well-Mixing Graphs and Applications to Information-Theoretic Cryptography

Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov

We study the connection between mixing properties for bipartite graphs and materialization of the mutual information in one-shot settings. We show that mixing properties of a graph imply impossibility to extract the mutual information shared by the ends of an edge randomly sampled in the graph. We apply these impossibility results to some questions motivated by information-theoretic cryptography. In particular, we show that communication complexity of a secret key agreement in one-shot setting is inherently uneven: for some inputs, almost all communication complexity inevitably falls on only one party.

arXiv:2405.05831•IEEE Information Theory Workshop (ITW)•Nov 24, 2024•2 citations

Secret Key Agreement from Correlated Data, with No Prior Information

Marius Zimand

A fundamental question that has been studied in cryptography and in information theory is whether two parties can communicate confidentially using exclusively an open channel. We consider the model in which the two parties hold inputs that are correlated in a certain sense. This model has been studied extensively in information theory, and communication protocols have been designed which exploit the correlation to extract from the inputs a shared secret key. However, all the existing protocols are not universal in the sense that they require that the two parties also know some attributes of the correlation. In other words, they require that each party knows something about the other party's input. We present a protocol that does not require any prior additional information. It uses space-bounded Kolmogorov complexity to measure correlation and it allows the two legal parties to obtain a common key that looks random to an eavesdropper that observes the communication and is restricted to use a bounded amount of space for the attack. Thus the protocol achieves complexity-theoretical security, but it does not use any unproven result from computational complexity. On the negative side, the protocol is not efficient in the sense that the computation of the two legal parties uses more space than the space allowed to the adversary.

arXiv:1910.03757•Leibniz international proceedings in informatics•Oct 9, 2019•0 citations

An Operational Characterization of Mutual Information in Algorithmic Information Theory

Andrei Romashchenko, Marius Zimand

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties—one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair—can establish via a probabilistic protocol with interaction on a public channel. For ℓ > 2, the longest shared secret that can be established from a tuple of strings ( x 1 , …, x ℓ ) by ℓ parties—each one having one component of the tuple and the complexity profile of the tuple—is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length for protocols with public randomness. We also show that if the communication complexity drops below the established threshold, then only very short secret keys can be obtained.

arXiv:1710.05984•Journal of the ACM•Sep 19, 2019•11 citations

Converses for Secret Key Agreement and Secure Computing

Himanshu Tyagi, Shun Watanabe

We consider information theoretic secret key agreement and secure function computation by multiple parties observing correlated data, with access to an interactive public communication channel. Our main result is an upper bound on the secret key length, which is derived using a reduction of binary hypothesis testing to multiparty secret key agreement. Building on this basic result, we derive new converses for multiparty secret key agreement. Furthermore, we derive converse results for the oblivious transfer problem and the bit commitment problem by relating them to secret key agreement. Finally, we derive a necessary condition for the feasibility of secure computation by trusted parties that seek to compute a function of their collective data, using an interactive public communication that by itself does not give away the value of the function. In many cases, we strengthen and improve upon previously known converse bounds. Our results are single-shot and use only the given joint distribution of the correlated observations. For the case when the correlated observations consist of independent and identically distributed (in time) sequences, we derive strong versions of previously known converses.

arXiv:1404.5715•Apr 23, 2014•5 citations
We propose a linear algebraic method, rooted in the spectral properties of graphs, that can be used to prove lower bounds in communication complexity. Our proof technique effectively marries spectral bounds with information-theoretic inequalities. The key insight is the observation that, in specific settings, even when data sets XXX and YYY are closely correlated and have high mutual information, the owner of XXX cannot convey a reasonably short message that maintains substantial mutual information with YYY. In essence, from the perspective of the owner of YYY, any sufficiently brief message m=m(X)m=m(X)m=m(X) would appear nearly indistinguishable from a random bit sequence. We employ this argument in several problems of communication complexity. Our main result concerns cryptographic protocols. We establish a lower bound for communication complexity of multi-party secret key agreement with unconditional, i.e., information-theoretic security. Specifically, for one-round protocols (simultaneous messages model) of secret key agreement with three participants we obtain an asymptotically tight lower bound. This bound implies optimality of the previously known omniscience communication protocol (this result applies to a non-interactive secret key agreement with three parties and input data sets with an arbitrary symmetric information profile). We consider communication problems in one-shot scenarios when the parties' inputs are not produced by any i.i.d. sources, and there are no ergodicity assumptions on the input data. In this setting, we found it natural to present our results using the framework of Kolmogorov complexity.
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y , respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x , y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key, the size of which is much smaller than the mutual information between x and y . However, we discuss a natural class of x , y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses the spectral properties of appropriate graphs and the expander mixing lemma, as well as information-theoretic techniques, including constraint information inequalities and Muchnik’s conditional descriptions. A preliminary version of this article was published in the proceedings of MFCS 2020. In the present version, we give full proofs of all theorems and get rid of the assumption that the number of random bits used in the communication protocols is polynomial.
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x, y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key whose size is much smaller than the mutual information between x and y. On the other hand, we discuss examples of x, y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses spectral properties of appropriate graphs and the expander mixing lemma, as well as information theoretic techniques.
We study the connection between mixing properties for bipartite graphs and materialization of the mutual information in one-shot settings. We show that mixing properties of a graph imply impossibility to extract the mutual information shared by the ends of an edge randomly sampled in the graph. We apply these impossibility results to some questions motivated by information-theoretic cryptography. In particular, we show that communication complexity of a secret key agreement in one-shot setting is inherently uneven: for some inputs, almost all communication complexity inevitably falls on only one party.
A fundamental question that has been studied in cryptography and in information theory is whether two parties can communicate confidentially using exclusively an open channel. We consider the model in which the two parties hold inputs that are correlated in a certain sense. This model has been studied extensively in information theory, and communication protocols have been designed which exploit the correlation to extract from the inputs a shared secret key. However, all the existing protocols are not universal in the sense that they require that the two parties also know some attributes of the correlation. In other words, they require that each party knows something about the other party's input. We present a protocol that does not require any prior additional information. It uses space-bounded Kolmogorov complexity to measure correlation and it allows the two legal parties to obtain a common key that looks random to an eavesdropper that observes the communication and is restricted to use a bounded amount of space for the attack. Thus the protocol achieves complexity-theoretical security, but it does not use any unproven result from computational complexity. On the negative side, the protocol is not efficient in the sense that the computation of the two legal parties uses more space than the space allowed to the adversary.
We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties—one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair—can establish via a probabilistic protocol with interaction on a public channel. For ℓ > 2, the longest shared secret that can be established from a tuple of strings ( x 1 , …, x ℓ ) by ℓ parties—each one having one component of the tuple and the complexity profile of the tuple—is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length for protocols with public randomness. We also show that if the communication complexity drops below the established threshold, then only very short secret keys can be obtained.
We consider information theoretic secret key agreement and secure function computation by multiple parties observing correlated data, with access to an interactive public communication channel. Our main result is an upper bound on the secret key length, which is derived using a reduction of binary hypothesis testing to multiparty secret key agreement. Building on this basic result, we derive new converses for multiparty secret key agreement. Furthermore, we derive converse results for the oblivious transfer problem and the bit commitment problem by relating them to secret key agreement. Finally, we derive a necessary condition for the feasibility of secure computation by trusted parties that seek to compute a function of their collective data, using an interactive public communication that by itself does not give away the value of the function. In many cases, we strengthen and improve upon previously known converse bounds. Our results are single-shot and use only the given joint distribution of the correlated observations. For the case when the correlated observations consist of independent and identically distributed (in time) sequences, we derive strong versions of previously known converses.