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

DOI10.1137/19M1236837zbMATH Open1498.94064arXiv2105.00765MaRDI QIDQ5138779FDOQ5138779

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)

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.

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

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

zbMATH Keywords

cryptographydifferential privacykey-agreement

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• 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
• On perfectly secure two-party computation for symmetric functionalities with correlated randomness
• Channels of small log-ratio leakage and characterization of two-party differentially private computation
• Correction to: ``Topology-hiding communication from minimal assumptions
• Black-box use of one-way functions is useless for optimal fair coin-tossing
• On the complexity of fair coin flipping

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)