Converses for Secret Key Agreement and Secure Computing
arXiv:1404.5715
Abstract
We consider information theoretic secret key agreement and secure function computation by multiple parties observing correlated data, with access to an interactive public communication channel. Our main result is an upper bound on the secret key length, which is derived using a reduction of binary hypothesis testing to multiparty secret key agreement. Building on this basic result, we derive new converses for multiparty secret key agreement. Furthermore, we derive converse results for the oblivious transfer problem and the bit commitment problem by relating them to secret key agreement. Finally, we derive a necessary condition for the feasibility of secure computation by trusted parties that seek to compute a function of their collective data, using an interactive public communication that by itself does not give away the value of the function. In many cases, we strengthen and improve upon previously known converse bounds. Our results are single-shot and use only the given joint distribution of the correlated observations. For the case when the correlated observations consist of independent and identically distributed (in time) sequences, we derive strong versions of previously known converses.
References in corpus (12)
- Mixed State Entanglement and Quantum Error Correction
- Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
- The operational meaning of min- and max-entropy
- Min- and Max- Relative Entropies and a New Entanglement Monotone
- One-Shot Classical-Quantum Capacity and Hypothesis Testing
- Unconditional security from noisy quantum storage
- Robustness of quantum Markov chains
- Common Information and Secret Key Capacity
- Implementation of two-party protocols in the noisy-storage model
- Multipartite Classical and Quantum Secrecy Monotones
- Secret Key Agreement: General Capacity and Second-Order Asymptotics
- Assisted Common Information with Applications to Secure Two-Party Computation