Communication-rounds tradeoffs for common randomness and secret key generation

DOI10.1137/1.9781611975482.112zbMATH Open1432.68154arXiv1808.08907OpenAlexW2952058148MaRDI QIDQ5236296FDOQ5236296

Authors: Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan 

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,dots$ and $Y_1,Y_2,dots$ with the pairs $(X_1,Y_1)$, $(X_2,Y_2)$, $dots$ being drawn independently from some known probability distribution $mu$. They wish to communicate so as to agree on $L$ bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions $mu=m{u}_{r,n,L}$, parametrized by integers $r$, $n$ and $L$, such that for every $r$ there exists a constant $b=b(r)$ for which CRG (respectively SKG) is feasible when $(X_i,Y_i)simm{u}_{r,n,L}$ with $r+1$ rounds of communication, each consisting of $O(logn)$ bits, but when restricted to $r/2-3$ rounds of interaction, the total communication must exceed $Omega(n/lo{g}^b(n))$ bits. Prior to our work no separations were known for $rgeq2$.

Full work available at URL: https://arxiv.org/abs/1808.08907

Recommendations

• Resource-efficient common randomness and secret-key schemes
• Common Randomness and Secret Key Capacities of Two-Way Channels
• Common randomness in information theory and cryptography. I. Secret sharing
• Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols
• Secret key agreement by public discussion from common information

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Cryptography (94A60) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11)

Cited In (3)

• Common randomness and secret key generation with a helper
• Common Randomness and Secret Key Capacities of Two-Way Channels
• Resource-efficient common randomness and secret-key schemes

This page was built for publication: Communication-rounds tradeoffs for common randomness and secret key generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236296)