Random codes and graphs for secure communication

2009 2009

Other formats: Order a copy

Abstract (summary)

This dissertation considers two groups of problems related to secure communication. The first line of research is devoted to theoretical problems of copyright protection of digital content. Embedding identification data in the content is a well-developed technique of content protection known under the name of fingerprinting. Schemes that provide such protection are known as fingerprinting codes in the literature. We study limits of the number of users of a fingerprinting system as well as constructions of low-complexity fingerprinting codes that support a large number of users. The second problem that is addressed in the dissertation relates to connectivity analysis of ad hoc wireless networks. One of the basic requirements in such environments is to ensure that none of the nodes are completely isolated from the network. We address the problem of characterizing threshold parameters for node isolation that enable the system designer to choose the power needed for network operation based on the outage probability of links in the network.

The methods of this research draw from coding theory, information theory and random graphs. An idea that permeates most results in this dissertation is the application of randomization both in the analysis of fingerprinting and node isolation.

The main contributions of this dissertation belong in the area of fingerprinting and are described as follows. We derive new lower and upper bounds on the optimal trade-off between the number of users and the length of the fingerprints required to ensure reliability of the system, which we call fingerprinting capacity. Informationtheoretic techniques employed in our proofs of bounds on capacity originate in coding theorems for channels with multiple inputs. Constructions of fingerprinting codes draw on methods of coding theory related to list decoding and code concatenation.

We also analyze random graph models for ad hoc networks with link failures and secure sensor networks that employ randomized key distribution. We establish a precise zero-one law for node isolation in the model with link failures for nodes placed on the circle. We further generalize this result to obtain a one-law for secure sensor networks on some surfaces.

Indexing (details)

Electrical engineering;
Computer science
0544: Electrical engineering
0984: Computer science
Identifier / keyword
Applied sciences; Coding theory; Digital watermarking; Information theory; Random codes; Random graphs; Secure communication; Security
Random codes and graphs for secure communication
Anthapadmanabhan, Nagaraj Prasanth
Number of pages
Publication year
Degree date
School code
DAI-B 70/06, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Barg, Alexander
Committee member
Makowski, Armand; Narayan, Prakash; Srinivasan, Aravind; Wu, Min
University of Maryland, College Park
Electrical Engineering
University location
United States -- Maryland
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.