Information Theoretical Cryptogenography
Tóm tắt
We consider problems where n people are communicating and a random subset of them is trying to leak information, without making it clear who are leaking the information. We introduce a measure of suspicion and show that the amount of leaked information will always be bounded by the expected increase in suspicion, and that this bound is tight. Suppose a large number of people have some information they want to leak, but they want to ensure that after the communication, an observer will assign probability at most c to the events that each of them is trying to leak the information. How much information can they reliably leak, per person who is leaking? We show that the answer is
$$\left( \frac{-\log (1-c)}{c}-\log (e)\right) $$
bits.
Tài liệu tham khảo
R.J. Aumann. Interactive epistemology I: Knowledge. Int. J. Game Theory, 28(3), 263–300 (1999)
M. Backes, A. Kate, P. Manoharan, S. Meiser, E. Mohammadi, AnoA: A framework for analyzing anonymous communication protocols, in 2013 IEEE 26th Computer Security Foundations Symposium (CSF) (IEEE, 2013), pp. 163–178
R. Bagai, H. Lu, R. Li, B. Tang, An accurate system-wide anonymity metric for probabilistic attacks, in Proceedings of the 11th Privacy Enhancing Technologies Symposium (PETS 2011) (2011)
J. Brody, S. Jakobsen, D. Scheder, P. Winkler, Cryptogenography, in ITCS (2014)
D. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM, 24(2), 84–90 (1981).
D. Chaum, The dining cryptographers problem: Unconditional sender and recipient untraceability. J. Cryptol. 1, 65–75 (1988)
S. Clauß, S. Schiffner, Structuring anonymity metrics, in Proceedings of the Second ACM Workshop on Digital Identity Management, DIM ’06 (ACM, New York, NY, 2006), pp. 55–62
T.M. Cover, J.A. Thomas. Elements of Information Theory (Wiley-Interscience, New York, NY, 1991)
G. Danezis, C. Diaz, A survey of anonymous communication channels. Technical Report MSR-TR-2008-35, Microsoft Research (2008)
C. Diaz, S. Seys, J. Claessens, B. Preneel, Towards measuring anonymity. In R. Dingledine, P. Syverson, editors, Proceedings of Privacy Enhancing Technologies Workshop (PET 2002), LNCS 2482 (Springer, 2002)
R. Dingledine, N. Mathewson, P. Syverson, Tor: The second-generation onion router, in Proceedings of the 13th USENIX Security Symposium (2004)
B. Doerr, M. Künnemann, Improved protocols and hardness results for the two-player cryptogenography problem (2016). arXiv:1603.06113
C. Dwork, A. Roth, The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9(3-4), 211–407 (2014)
M. Edman, F. Sivrikaya, B. Yener, A combinatorial approach to measuring anonymity, in 2007 IEEE Intelligence and Security Informatics , pp. 356–363 (2007)
Freehaven. Anonymity bibliography. http://www.freehaven.net/anonbib/.
B. Gierlichs, C. Troncoso, C. Diaz, B. Preneel, I. Verbauwhede, Revisiting a combinatorial approach toward measuring anonymity. In V. Atluri, M. Winslett, editors, WPES ’08: Proceedings of the 7th ACM Workshop on Privacy in the Electronic Society (ACM, Alexandria, VA, 2008), pp. 111–116
D.M. Goldschlag, M.G. Reed, P.F. Syverson, Hiding routing information. In R. Anderson, editor, Proceedings of Information Hiding: First International Workshop, LNCS 1174 (Springer, 1996), pp. 137–150
N.J. Hopper, Toward a Theory of Steganography. PhD thesis, Carnegie Mellon University (2004)
E. Kushilevitz, N. Nisan, Communication Complexity (Cambridge University Press, New York, NY, 1997)
A. Serjantov, G. Danezis, Towards an information theoretic metric for anonymity. In R. Dingledine, P. Syverson, editors, Proceedings of Privacy Enhancing Technologies Workshop (PET 2002), LNCS 2482 (Springer, 2002)
C.E. Shannon, ACM SIGMOBILE Mobile Computing and Communications Review. A mathematical theory of communication, 5(1), 3–55 (2001)
G. Tóth, Z. Hornák, F. Vajda, Measuring anonymity revisited. In S. Liimatainen, T. Virtanen, editors, Proceedings of the Ninth Nordic Workshop on Secure IT Systems (2004), pp. 85–90
J. Van Den Hooff, D. Lazar, M. Zaharia, N. Zeldovich, Vuvuzela: Scalable private messaging resistant to traffic analysis, in Proceedings of the 25th Symposium on Operating Systems Principles (ACM, 2015), pp. 137–152
A. Chi-Chih Yao, Some complexity questions related to distributive computing (preliminary report), in Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC ’79 (ACM, New York, NY, 1979), pp. 209–213
Y. Zhu, R. Bettati, Anonymity vs. information leakage in anonymity systems, in ICDCS’05 (2005), pp. 514–524