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:1910.03757 · Leibniz international proceedings in informatics

Secret Key Agreement from Correlated Data, with No Prior Information

Marius Zimand

Published Oct 9, 2019• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.stacs.2020.21

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.

arXiv:2004.13411•ACM Transactions on Computation Theory•May 17, 2024•5 citations

On secret key agreement from the additive white Gaussian noise channel

Motohiko Isaka, Kawata Seiya

It is known that noise on communication channels can be a powerful resource for certain cryptographic purposes, basically by utilizing the randomness to ensure the secrecy. In this paper, we study information theoretically secure key agreement through the use of the additive white Gaussian noise channel and public discussion. We present a protocol for key agreement that defines the computation and communications between the two communicating parties to share a common secret information, about which negligible amount of information is revealed to other third parties. We discuss the signal design, secrecy and the achievable rate of the protocol.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2009•1 citation

Resource-Efficient Common Randomness and Secret-Key Schemes

Badih Ghazi, T. S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.

arXiv:1707.08086•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•15 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•14 citations

New bounds on the information-theoretic key agreement of multiple terminals

Amin Gohari, Venkat Anantharam

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•13 citations

Information Theoretic Secrecy

Abbas El Gamal, Young-Han Kim

Confidentiality of information is a key consideration in many networking applications, including e-commerce, online banking, and intelligence operations. How can information be communicated reliably to the legitimate users, while keeping it secret from eavesdroppers? How does such a secrecy constraint on communication affect the limits on information flow in the network? In this chapter, we study these questions under the information theoretic notion of secrecy, which requires each eavesdropper to obtain essentially no information about the messages sent from knowledge of its received sequence, the channel statistics, and the codebooks used. We investigate two approaches to achieve secure communication. The first is to exploit the statistics of the channel from the sender to the legitimate receivers and the eavesdroppers. We introduce the wiretap channel as a 2-receiver broadcast channel with a legitimate receiver and an eavesdropper, and establish its secrecy capacity, which is the highest achievable secret communication rate. The idea is to design the encoder so that the channel from the sender to the receiver becomes effectively stronger than the channel to the eavesdropper; hence the receiver can recover the message but the eavesdropper cannot. This wiretap coding scheme involves multicoding and randomized encoding. If the channel from the sender to the receiver is weaker than that to the eavesdropper, however, secret communication at a positive rate is not possible. This brings us to the second approach to achieve secret communication, which is to use a secret key shared between the sender and the receiver but unknown to the eavesdropper. We show that the rate of such secret key must be at least as high as the rate of the confidential message. This raises the question of how the sender and the receiver can agree on such a long secret key in the first place. After all, if they had a confidential channel with sufficiently high capacity to communicate the key, then why not use it to communicate the message itself! We show that if the sender and the receiver have access to correlated sources (e.g., through a satellite beaming common randomness to them), then they can still agree on a secret key even when the channel has zero secrecy capacity. We first consider the source model for key agreement, where the sender communicates with the receiver over a noiseless public broadcast channel to generate a secret key from their correlated sources.

Cambridge University Press eBooks•Dec 8, 2011•1 citation
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.
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 noise on communication channels can be a powerful resource for certain cryptographic purposes, basically by utilizing the randomness to ensure the secrecy. In this paper, we study information theoretically secure key agreement through the use of the additive white Gaussian noise channel and public discussion. We present a protocol for key agreement that defines the computation and communications between the two communicating parties to share a common secret information, about which negligible amount of information is revealed to other third parties. We discuss the signal design, secrecy and the achievable rate of the protocol.
We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.
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 study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.
Confidentiality of information is a key consideration in many networking applications, including e-commerce, online banking, and intelligence operations. How can information be communicated reliably to the legitimate users, while keeping it secret from eavesdroppers? How does such a secrecy constraint on communication affect the limits on information flow in the network? In this chapter, we study these questions under the information theoretic notion of secrecy, which requires each eavesdropper to obtain essentially no information about the messages sent from knowledge of its received sequence, the channel statistics, and the codebooks used. We investigate two approaches to achieve secure communication. The first is to exploit the statistics of the channel from the sender to the legitimate receivers and the eavesdroppers. We introduce the wiretap channel as a 2-receiver broadcast channel with a legitimate receiver and an eavesdropper, and establish its secrecy capacity, which is the highest achievable secret communication rate. The idea is to design the encoder so that the channel from the sender to the receiver becomes effectively stronger than the channel to the eavesdropper; hence the receiver can recover the message but the eavesdropper cannot. This wiretap coding scheme involves multicoding and randomized encoding. If the channel from the sender to the receiver is weaker than that to the eavesdropper, however, secret communication at a positive rate is not possible. This brings us to the second approach to achieve secret communication, which is to use a secret key shared between the sender and the receiver but unknown to the eavesdropper. We show that the rate of such secret key must be at least as high as the rate of the confidential message. This raises the question of how the sender and the receiver can agree on such a long secret key in the first place. After all, if they had a confidential channel with sufficiently high capacity to communicate the key, then why not use it to communicate the message itself! We show that if the sender and the receiver have access to correlated sources (e.g., through a satellite beaming common randomness to them), then they can still agree on a secret key even when the channel has zero secrecy capacity. We first consider the source model for key agreement, where the sender communicates with the receiver over a noiseless public broadcast channel to generate a secret key from their correlated sources.