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

IEEE Information Theory Workshop (ITW)

Linear perfect secret key agreement

Chung Chan

Published Oct 1, 2011• 26 citations
Publisher

Abstract

A linear scheme is proposed for multiterminal secret key agreement under a private finite linear source model with public discussion. With a wiretapper observing the public discussion and a subset of the source components, it attains the secrecy capacity perfectly and non-asymptotically with a finite block length. Upper bounds on the block length and public discussion rate are given.

DOI
10.1109/itw.2011.6089530

Related papers

One-Shot Perfect Secret Key Agreement for Finite Linear Sources

Chung Chan, Navin Kashyap, Praneeth Kumar Vippathalla +1 more

We consider a non-asymptotic (one-shot) version of the multiterminal secret key agreement problem on a finite linear source model. In this model, the observation of each terminal is a linear function of an underlying random vector composed of finitely many i.i.d. uniform random variables. By restricting the public discussion to be a linear function of the terminals' observations, we obtain a characterization of the communication complexity (minimum number of symbols of public discussion) of generating a secret key of maximum length. More precisely, we show that the minimum discussion can be achieved by a non-interactive protocol in which each terminal first does a linear processing of its own private observations, following which the terminals all execute a discussion-optimal communication-for-omniscience protocol. The secret key can be chosen to be a linear function of the vector of all observations.

arXiv:1901.05817•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•2 citations

Multiterminal Secret Key Agreement with Nearly No Discussion

Chung Chan, Manuj Mukherjee, Praneeth Kumar Vippathalla +1 more

We consider the secret key agreement problem under the multiterminal source model proposed by Csiszár and Narayan. A single-letter characterization of the secrecy capacity is desired but remains unknown except in the extreme case with unlimited public discussion and without wiretapper's side information. Taking the problem to the opposite extreme by requiring the public discussion rate to be zero asymptotically, we obtain the desired characterization under surprisingly general setting with wiretapper's side information, silent users, trusted and untrusted helpers. An immediate consequence of the result is that the capacity with nearly no discussion is the same as the capacity with no discussion, resolving a previous conjecture in the affirmative. The idea of the proof is to characterize the capacity in the special case with neither wiretapper's side information nor untrusted helpers using a multivariate extension of Gács-Körner common information, and then extend the result to the general setting by a change of scenario that turns untrusted helpers into trusted helpers. We further show how to evaluate the capacity explicitly for finite linear sources and discuss how the current result can be extended to improve and unify existing bounds on the capacity for strictly positive discussion rates.

arXiv:1904.11383•Apr 25, 2019•2 citations

Secret key agreement for hypergraphical sources with limited total discussion

Chung Chan

This work considers the problem of multiterminal secret key agreement by limited total public discussion under the hypergraphical source model. The secrecy capacity as a function of the total discussion rate is completely characterized by a polynomial-time computable linear program. Compared to the existing solution for a particular hypergraphical source model called the pairwise independent network (PIN) model, the current result is a non-trivial extension as it applies to a strictly larger class of sources and a more general scenario involving helpers and wiretapper's side information. In particular, while the existing solution by tree-packing can be strictly suboptimal for the PIN model with helpers and the hypergraphical source model in general, we can show that decremental secret key agreement and linear network coding is optimal, resolving a previous conjecture in the affirmative. The converse is established by a single-letter upper bound on the secrecy capacity for discrete memoryless multiple sources and individual discussion rate constraints. The minimax optimization involved in the bound can be relaxed to give the best existing upper bounds on secrecy capacities such as the lamination bounds for hypergraphical sources, helper-set bound for general sources, the bound at asymptotically zero discussion rate via the multivariate Gác--Körner common information, and the lower bound on communication complexity via a multivariate extension of the Wyner common information. These reductions unify existing bounding techniques and reveal surprising connections between seemingly different information-theoretic notions. Further challenges are posed in this work along with a simple example of finite linear source where the current converse techniques fail even though the proposed achieving scheme remains optimal.

arXiv:1910.01894•Oct 4, 2019•2 citations

Secret key agreement under discussion rate constraints

Chung Chan, Manuj Mukherjee, Navin Kashyap +1 more

For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the minimum public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to the general source model without helpers or wiretapper's side information, but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, our results yield a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate.

arXiv:1701.05008•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•16 citations

Delay of linear perfect secret key agreement

Chung Chan

Upper bounds are given on the block length required to attain the secrecy capacity by linear perfect secret key agreement. The bounds are universal to the source statistics and grow polynomially in the size of the network when the number of helpers is constant. The practical significance is that a shorter block length entails a smaller delay, lower computational complexity, and more efficient code construction.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2011•10 citations

Multiterminal Secret Key Agreement at Asymptotically Zero Discussion Rate

Chung Chan, Manuj Mukherjee, Navin Kashyap +1 more

In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.

arXiv:1802.04955•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•11 citations
A linear scheme is proposed for multiterminal secret key agreement under a private finite linear source model with public discussion. With a wiretapper observing the public discussion and a subset of the source components, it attains the secrecy capacity perfectly and non-asymptotically with a finite block length. Upper bounds on the block length and public discussion rate are given.
We consider a non-asymptotic (one-shot) version of the multiterminal secret key agreement problem on a finite linear source model. In this model, the observation of each terminal is a linear function of an underlying random vector composed of finitely many i.i.d. uniform random variables. By restricting the public discussion to be a linear function of the terminals' observations, we obtain a characterization of the communication complexity (minimum number of symbols of public discussion) of generating a secret key of maximum length. More precisely, we show that the minimum discussion can be achieved by a non-interactive protocol in which each terminal first does a linear processing of its own private observations, following which the terminals all execute a discussion-optimal communication-for-omniscience protocol. The secret key can be chosen to be a linear function of the vector of all observations.
We consider the secret key agreement problem under the multiterminal source model proposed by Csiszár and Narayan. A single-letter characterization of the secrecy capacity is desired but remains unknown except in the extreme case with unlimited public discussion and without wiretapper's side information. Taking the problem to the opposite extreme by requiring the public discussion rate to be zero asymptotically, we obtain the desired characterization under surprisingly general setting with wiretapper's side information, silent users, trusted and untrusted helpers. An immediate consequence of the result is that the capacity with nearly no discussion is the same as the capacity with no discussion, resolving a previous conjecture in the affirmative. The idea of the proof is to characterize the capacity in the special case with neither wiretapper's side information nor untrusted helpers using a multivariate extension of Gács-Körner common information, and then extend the result to the general setting by a change of scenario that turns untrusted helpers into trusted helpers. We further show how to evaluate the capacity explicitly for finite linear sources and discuss how the current result can be extended to improve and unify existing bounds on the capacity for strictly positive discussion rates.
This work considers the problem of multiterminal secret key agreement by limited total public discussion under the hypergraphical source model. The secrecy capacity as a function of the total discussion rate is completely characterized by a polynomial-time computable linear program. Compared to the existing solution for a particular hypergraphical source model called the pairwise independent network (PIN) model, the current result is a non-trivial extension as it applies to a strictly larger class of sources and a more general scenario involving helpers and wiretapper's side information. In particular, while the existing solution by tree-packing can be strictly suboptimal for the PIN model with helpers and the hypergraphical source model in general, we can show that decremental secret key agreement and linear network coding is optimal, resolving a previous conjecture in the affirmative. The converse is established by a single-letter upper bound on the secrecy capacity for discrete memoryless multiple sources and individual discussion rate constraints. The minimax optimization involved in the bound can be relaxed to give the best existing upper bounds on secrecy capacities such as the lamination bounds for hypergraphical sources, helper-set bound for general sources, the bound at asymptotically zero discussion rate via the multivariate Gác--Körner common information, and the lower bound on communication complexity via a multivariate extension of the Wyner common information. These reductions unify existing bounding techniques and reveal surprising connections between seemingly different information-theoretic notions. Further challenges are posed in this work along with a simple example of finite linear source where the current converse techniques fail even though the proposed achieving scheme remains optimal.
For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the minimum public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to the general source model without helpers or wiretapper's side information, but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, our results yield a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate.
In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.