Computational two-party correlation: a dichotomy for key-agreement protocols

DOI10.1137/19M1236837MaRDI QIDQ5138779zbMATH OpenFDO

Authors Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

Publication date 4 December 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

cryptographydifferential privacykey-agreement

Mathematics Subject Classification ID

Cryptography (94A60) Privacy of data (68P27) Communication complexity, information complexity (68Q11)

Abstract: Let $pi$ be an efficient two-party protocol that given security parameter $kappa$, both parties output single bits $X_{k}appa$ and $Y_{k}appa$, respectively. We are interested in how $(X_{k}appa,Y_{k}appa)$ "appears" to an efficient adversary that only views the transcript $T_{k}appa$. We make the following contributions: $$ We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol $pi$, there exists an efficient simulator such that the following holds: on input $T_{k}appa$, the simulator outputs a pair $(X{\text{'}}_{k}appa,Y{\text{'}}_{k}appa)$ such that $(X{\text{'}}_{k}appa,Y{\text{'}}_{k}appa,T_{k}appa)$ is (somewhat) computationally indistinguishable from $(X_{k}appa,Y_{k}appa,T_{k}appa)$. $$ We use these tools to prove the following dichotomy theorem: every such protocol $pi$ is: - either uncorrelated -- it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce $T_{k}appa$, but then choose their outputs independently from some product distribution (that is determined in poly-time from $T_{k}appa$), - or, the protocol implies a key-agreement protocol (for infinitely many $kappa$'s). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. $$ We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. $$ A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a longstanding open question regarding the complexity of fair two-party coin-flipping protocols.

Recommendations

• Extracting correlations
• Channels of small log-ratio leakage and characterization of two-party differentially private computation
• Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols
• On the complexity of fair coin flipping
• Secret-key agreement over unauthenticated public channels-part II: the simulatability condition

Cites work

• scientific article; zbMATH DE number 4185033 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• A uniform min-max theorem with applications in cryptography
• Accuracy-Privacy Tradeoffs for Two-Party Differentially Private Protocols
• Advances in Cryptology - EUROCRYPT 2004
• Black-box separations for differentially private protocols
• Can optimally-fair coin tossing be based on one-way functions?
• Channels of small log-ratio leakage and characterization of two-party differentially private computation
• Characterizing pseudoentropy and simplifying pseudorandom generator constructions
• Common randomness in information theory and cryptography. I. Secret sharing
• Distributed Private Data Analysis: Simultaneously Solving How and What
• Do distributed differentially-private protocols require oblivious transfer?
• Efficiency improvements in constructing pseudorandom generators from one-way functions
• How to fake auxiliary input
• Limits on the usefulness of random oracles
• Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
• New directions in cryptography
• Oblivious-Transfer Amplification
• On the Black-Box Complexity of Optimally-Fair Coin Tossing
• On the complexity of fair coin flipping
• On the complexity of simulating auxiliary input
• Optimal lower bound for differentially private multi-party aggregation
• Randomized response: a survey technique for eliminating evasive answer bias
• Secret key agreement by public discussion from common information
• Simulating auxiliary inputs, revisited
• Theory of Cryptography
• Theory of Cryptography
• Unconditionally secure key agreement and the intrinsic conditional information

Cited in

(9)

• On the complexity of fair coin flipping
• Computational hardness of optimal fair computation: beyond Minicrypt
• On the complexity of fair coin flipping
• A note on non-interactive zero-knowledge from CDH
• Tighter bounds on multiparty coin flipping via augmented weak martingales and differentially private sampling
• Channels of small log-ratio leakage and characterization of two-party differentially private computation
• On perfectly secure two-party computation for symmetric functionalities with correlated randomness
• Correction to: ``Topology-hiding communication from minimal assumptions
• Black-box use of one-way functions is useless for optimal fair coin-tossing

This page was built for publication: Computational two-party correlation: a dichotomy for key-agreement protocols

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