A Bound For Multiparty Secret Key Agreement And Implications For A Problem Of Secure Computing

Abstract. We consider secret key agreement by multiple parties observ-ing correlated data and communicating interactively over an insecure communication channel. Our main contribution is a single-shot upper bound on the length of the secret keys that can be generated, with-out making any assumptions on the distribution of the underlying data. Heuristically, we bound the secret key length in terms of “how far ” is the joint distribution of the initial observations of the parties and the eaves-dropper from a distribution that renders the observations of the parties conditionally independent across some partition, when conditioned on the eavesdropper’s side information. The closeness of the two distribu-tions is measured in terms of the exponent of the probability of error of type II for a binary hypothesis testing problem, thus bringing out a structural connection between secret key agreement and binary hypoth-esis testing. When the underlying data consists of an independent and identically distributed sequence, an application of our bound recover