Converses for Secret Key Agreement and Secure Computing
This work provides incremental improvements to converse bounds for cryptographic protocols like secret key agreement and secure computing, benefiting researchers in information theory and cryptography.
The paper tackles the problem of information-theoretic secret key agreement and secure function computation among multiple parties with correlated data and public communication, deriving new upper bounds on secret key length and strengthening existing converse results for various cryptographic protocols.
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.