---
author:
- 'Vinod M. Prabhakaran and Manoj M. Prabhakaran [^1]'
title: 'Assisted Common Information with an Application to Secure Two-Party Sampling'
---

Acknowledgements {#acknowledgements .unnumbered}
================

The example in is based on a suggestion by Jürg Wullschleger.  The first author would like to gratefully acknowledge discussions with Venkat Anantharam, Péter Gács, and Young-Han Kim.  We thank Hemanta Maji and Mike Rosulek for discussions at an early stage in this work.  We also thank Suhas Diggavi and the anonymous referees for carefully reviewing our drafts and making several insightful comments that have helped us greatly improve the paper. 

[1]{}

R. Ahlswede and J. Körner, “On common information and related characteristics of correlated information sources,” in [*Proc.  of the 7th Prague Conference on Information Theory*]{}, 1974. 

D. Beaver, “Correlated pseudorandomness and the complexity of private computations,” in [*Proc.  $28$th STOC*]{}, pp.  479–488, ACM, 1996. 

D. Beaver, “Precomputing oblivious transfer,” in Don Coppersmith, editor, [*CRYPTO*]{}, vol.  963 of [*Lecture Notes in Computer Science*]{}, pp.  97–109, Springer, 1995. 

T. M. Cover and J. A. Thomas, [*Elements of Information Theory*]{}, 2ed, Wiley, 2006. 

I. Csiszár and R. Ahlswede, “On oblivious transfer capacity,” in [*Proc.  International Symposium on Information Theory (ISIT)*]{}, pp.  2061–2064, 2007. 

I. Csiszár and J. Körner, , 1ed, Akadémiai Kiadó, Budapest, 1981. 

Y. Dodis and S. Micali, “Lower bounds for oblivious transfer reductions,” in Jacques Stern, editor, [*EUROCRYPT*]{}, vol.  1592 of [ *Lecture Notes in Computer Science*]{}, pp.  42–55, Springer, 1999. 

A. El Gamal and Y.-H. Kim, , Cambridge, 2012. 

P. Gács and J. Körner, “Common information is far less than mutual information,” , vol.  2, no.  2, pp.  119–162, 1973. 

M. Gastpar, B. Rimoldi, and M. Vetterli, “To code or not to code: Lossy source-channel communication revisited,” [*IEEE Transactions on Information Theory*]{}, vol.  49, no.  5, pp.  1147–1158, 2003. 

R. M. Gray and A. D. Wyner, “Source coding for a simple network,” [*Bell System Technical Journal*]{}, vol.  53, no.  9, pp.  1681–1721, 1974. 

H. Imai, K. Morozov, and A. C. A. Nascimento, “On the oblivious transfer capacity of the erasure channel,” in [*Proc.  International Symposium on Information Theory (ISIT)*]{}, pp.  1428–1431, 2006. 

H. Imai, K. Morozov, and A. C. A. Nascimento, “Efficient oblivious transfer protocols achieving a non-zero rate from any non-trivial noisy correlation,” in [*Proc.  International Conference on Information Theoretic Security (ICITS)*]{}, 2007. 

H. Imai, K. Morozov, A. C. A. Nascimento, and A. Winter, “Efficient protocols achieving the commitment capacity of noisy correlations,” in [*Proc.  International Symposium on Information Theory (ISIT)*]{}, pp.  1432–1436, 2006. 

H. Imai, J. Müller-Quade, A. C. A. Nascimento, and A. Winter, “Rates for bit commitment and coin tossing from noisy correlation,” in [*Proc.  International Symposium on Information Theory (ISIT)*]{}, pp.  45, 2004. 

Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Extracting Correlations.”  in [*Proc.  $50$th FOCS*]{}, pp.  261–270, IEEE, 2009. 

S. Kamath and V. Anantharam, “A new dual to the Gács-Körner common information defined via the Gray-Wyner system,” in [*Proc.  48th Allerton Conf.  on Communication, Control, and Computing*]{}, pp.  1340–1346, 2010. 

J. Kilian, “Founding cryptography on oblivious transfer,” in [*Proc.  $20$th STOC*]{}, pp.  20–31, ACM, 1988. 

J. Kilian, “More general completeness theorems for secure two-party computation,” in [*Proc.  $32$nd STOC*]{}, pp.  316–324, ACM, 2000. 

D. Marco and M. Effros, “On lossless coding with coded side information,” [*IEEE Transactions on Information Theory*]{}, vol.  55, no.  7, pp.  3284–3296, 2009. 

V. M. Prabhakaran and M. M. Prabhakaran, “Assisted common information,” in [*Proc.  International Symposium on Information Theory (ISIT)*]{}, pp.  2602-2606, 2010. 

V. M. Prabhakaran and M. M. Prabhakaran, “Assisted common information: Further results,” in [*Proc.  International Symposium on Information Theory (ISIT)*]{}, pp.  2861 - 2865, 2011. 

M. M. Prabhakaran and V. M. Prabhakaran, “On secure multiparty sampling for more than two parties,” in [Proc.  IEEE Information Theory Workshop (ITW)]{}, pp.  99 - 103, 2012. 

M. Rabin. “ How to exchange secrets by oblivious transfer,” Technical Report TR-81, Harvard Aiken Computation Laboratory, 1981. 

Stephen Wiesner. “ Conjugate coding,” Sigact News, vol.  15, pp.  78–88, 1983. 

S. Winkler and J. Wullschleger. “ On the Efficiency of Classical and Quantum Oblivious Transfer Reductions,” in Tal Rabin, editor, [*CRYPTO*]{}, vol.  6223 of [*Lecture Notes in Computer Science*]{}, pp.  707–723, Springer, 2010. 

A. Winter, A. C. A. Nascimento, and H. Imai. “ Commitment capacity of discrete memoryless channels,” in Kenneth G. Paterson, editor, [*IMA Int.  Conf.*]{},  vol.  2898 of [*Lecture Notes in Computer Science*]{}, pp.  35–51, Springer, 2003. 

H. S. Witsenhausen, “On sequences of pairs of dependent random variables,” , 28:100–113, 1975. 

S. Wolf and J. Wullschleger. “ Oblivious Transfer Is Symmetric,” , vol.  4004 of [*Lecture Notes in Computer Science*]{}, pp.  222–232, Springer, 2006. 

S. Wolf and J. Wullschleger. “ New monotones and lower bounds in unconditional two-party computation,” , vol.  54, no.  6, pp.  2792–2797, 2008. 

J. Wullschleger.  Oblivious-Transfer Amplification.  Ph.D. thesis, Swiss Federal Institute of Technology, Zürich, 2008.  <http://arxiv.org/abs/cs.CR/0608076>. 

A. D. Wyner, “The common information of two dependent random variables,” , vol.  21, no.  2, pp.  163–179, 1975. 

A. D. Wyner and J. Ziv, “Rate-distortion function for source coding with side information at the decoder,” , vol.  22, no.  1, pp.  1–11, 1976. 

H. Yamamoto, “Coding theorems for Shannon’s cipher system with correlated source outputs, and common information,” , vol.  40, no.  1, pp.  85–95, 1994. 

[^1]: This work was presented in part at IEEE International Symposia on Information Theory (ISIT) 2010 and 2011 [@PrabhakaranPr10; @PrabhakaranPr11].  Vinod M. Prabhakaran’s work was supported in part by a Ramanujan Fellowship from the Department of Science and Technology, Government of India.  Manoj M. Prabhakaran’s work was supported in part by NSF CAREER award 07-47027 and NSF grant 12-28856. 

    Vinod M. Prabhakaran is with the School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai 400 005 India (email: vinodmp@tifr.res.in)

    Manoj M. Prabhakaran is with the Department of Computer Science, University of Illinois, Urbana-Champaign, IL 61801 USA (email: mmp@illinois.edu)
