DocumentCode :
3070354
Title :
Assisted common information
Author :
Prabhakaran, Vinod ; Prabhakaran, Manoj
Author_Institution :
Univ. of Illinois, Urbana-Champaign, Urbana, IL, USA
fYear :
2010
fDate :
13-18 June 2010
Firstpage :
2602
Lastpage :
2606
Abstract :
Secure multi-party computation is a central problem in modern cryptography. An important sub-class of this are problems of the following form: Alice and Bob desire to produce sample(s) of a pair of jointly distributed random variables. Each party must learn nothing more about the other party´s output than what its own output reveals. To aid in this, they have available a set up - correlated random variables whose distribution is different from the desired distribution - as well as unlimited noiseless communication. In this paper we present an upperbound on how efficiently a given set up can be used to produce samples from a desired distribution. The key tool we develop is a generalization of the concept of common information of two dependent random variables [Gács-Körner, 1973]. Our generalization - a three-dimensional region - remedies some of the limitations of the original definition which captured only a limited form of dependence. It also includes as a special case Wyner´s common information [Wyner, 1975]. To derive the cryptographic bounds, we rely on a monotonicity property of this region: the region of the “views” of Alice and Bob engaged in any protocol can only monotonically expand and not shrink. Thus, by comparing the regions for the target random variables and the given random variables, we obtain our upperbound.
Keywords :
cryptography; cryptography; jointly distributed random variable; secure multiparty computation; unlimited noiseless communication; Cryptographic protocols; Cryptography; Distributed control; Entropy; Game theory; Information theory; Noise reduction; Q measurement; Random variables; Shape;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on
Conference_Location :
Austin, TX
Print_ISBN :
978-1-4244-7890-3
Electronic_ISBN :
978-1-4244-7891-0
Type :
conf
DOI :
10.1109/ISIT.2010.5513743
Filename :
5513743
Link To Document :
بازگشت