ISIT 2007 : security, wiretapping, and jamming

Fingerprinting Capacity Under the Marking Assumption (N. Prasanth Anthapadmanabhan, Alexander Barg, and Ilya Dumer) : This is a cool problem that was new to me and uses some AVC-like techniques so I was quite excited about it. Suppose we have an original version of some data. We would like to make many copies with fingerprints and distribute them such that if any t recipients collude (the “pirates”), they cannot make a fake new copy that will fool a validating agent. The marking assumption is that the pirates cannot change the fingerprint except in places where their copies differ. This is a tough combinatorial problem but is amenable to some random coding arguments. In particular, they get upper and lower bounds on the case of 2 or 3 pirates for binary alphabets.

On Multiterminal Secrecy Capacities (Imre Csiszár and Prakash Narayan) : I talked about some of this work from ITA — this was quite similar, but since it was my second time seeing some of the material, I got a bit more out of it. One basic problem from this paper is this : a public “server” terminal broadcasts a message to a bunch of receivers, who then engage in public discussion. How large a key can they generate, given that the public communication is subject to eavesdropping? The most interesting technical detail for me was the use of Markov trees for the case where some of the receivers are also wiretapped.

On Oblivious Transfer Capacity (Imre Csiszár and Rudolf Ahlswede) : This talk was the only one I saw given on transparencies — Csiszár apologized for giving a talk on “old technology” but noted that the “topic is quite new.” The Oblivious Transfer problem is this : Alice has two strings, X and Y, each of which is k bits long. Bob has a binary variable Z which tells him in which string he is interested (0 for X and 1 for Y). Bob wants to get his string, but doesn’t want to let Alice know which one he wanted, and Alice wants to tell him the correct string without revealing anything about the one he didn’t want. Alice can communicate over a DMC and there is also noiseless two-way communication. The capacity is defined as the limit of k/n, where k is the maximum achievable k. They get bounds on the OT capacity, which in some cases are tight, but under the assumption that Alice and Bob do not try to “cheat.”

An Achievable Region of Gaussian Wiretap Channel with Side Information (Yanling Chen and A.J. Han Vinck) : This paper looks at the wiretapping problem where an additive channel interference term is known at the encoder. In this setting, a generalized Costa “dirty paper” coding scheme can be shown to mask the source signal from a wiretapper (giving high equivocation) while communicating over the channel as if the interference were not present. They conjecture that this scheme is optimal, but as usual in more complicated coding scenarios, the converses are a little harder to come by.

Shannon’s Secrecy System With Informed Receivers and its Application to Systematic Coding for Wiretapped Channels (Neri Merhav) : This studies the case where an iid source vector to be encoded at the transmitter is observed in two ways by the decoder — firstly via an iid correlated sequence of variables, and secondly via an encoded message sent via the encoder over a DMC. The wiretapper gets a degraded version of both of these variables. One key message from the talk was that systematic coding is sometimes as good as the “optimal” scheme in an equivocation sense.


0 thoughts on “ISIT 2007 : security, wiretapping, and jamming

  1. The recent work of Csiszar and Ahlswede is based on the new area inaugurated by the cryptographer Anderson Nascimento. There’s a more recent work developed by him in which he obtains an efficient and optimal protocol for OT. He also prove his protocol is efficent in the non-asymptotic case (the so-called single serving case).
    He published in this conference:

    I have read Professor Ahlswede’s paper, it is a good one, but I think Professor Nascimento’s work should also be valorized.

  2. I know that Nascimento did a lot of pioneering work on the problem, but I could only really comment on the talk that I saw. I did go to the OT talk at last ISIT, which was Winter-Nascimento (or the other way around), but since it was my first time ever seeing the problem, I think I got lost a bit too quickly.

    Thank you for the link though!

  3. Hi all,

    Came upon this page thanks to Google 🙂

    Thanks for the comments.

    I believe it is not completely fair to say I created the subject of cryptographic capacities (Commitment and OT Capacity) of noisy channels/correlations. Many people were/are involved with it.

    I believe it is an exciting new field with many nice open questions to be attacked.

    Just to name a few: extensions to continuous channels, more general models where some parameters of the channel might be controlled by an adversary, relations to game theory, etc.

    If anyone is interested in the subject, please, send me an email ….

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.