• Diese Seite als PDF öffnen.

Explicit Construction of Deterministic Identification Codes

Keywords:
Identification via channels, identification codes,

Description

In this thesis, the student after studying deterministic identification will construct the explicit codes for certain channels.

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Construction of Identification Codes via Prime Numbers

Keywords:
Identification via channels, Prime Number Encryption

Short Description:
An approach for construction of identification codes for noiseless channel by means of the prime number encryption would be studied.

Description

In original scheme of identificaion via channels (Ahlswede and Dueck, 1989), a non-constructive method for coding for noiseless channel was studied. To address the explicit construction of identificaion codes, foremost Ahlswede and Verboven, 1991 provide a number theoretic approach based on the two successive prime number encryption. This method require the knowledge of first 2^n prime numbers for a block-length of n codeword. In this research internship, this method along with related prime number encryption tools and theorems would be investigated. Further, the extension of this scheme to a general DMC will be analyzed.

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

On the Equivalence of Identification and Authentication

Keywords:
Identification via channel, identification codes, authentication, authentication codes

Short Description:
A Certain equivalence of identification and authentication would be shown.

Description

It would be shown that under suitable formulations (preserving all salient features) the two problem of Identification (Ahlswede and Dueck, 1989) and Authentication (Simmons, G. J. 1984) are in essence very close to each other. This equivalency was conjectured first by M. S. Pinsker. In this research internship the student is expected to address this conjecture. Both problems must be studied separately and then the similar essence of them should be drawn out. In particular the identification codes and authentication codes along with theire relation will be investigated.

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Deterministic Identification Over the Binary Symmetric Channel

Keywords:
Identification, Identification Without Randomization, Complexity of Distributive Computing, One-Way/Two-Way Probabilistic Communications

Short Description:
Identification without randomization over the binary symmetric channel (BSC) would be studied and investigated. Method of coding, decoding sets, type I/II errors and a closed-form solution of non-randomized (deterministic) identification capacity will be considered and analysed.

Description

In theory of Identification introduced by Ahlswede and Dueck the perspective of  communications is changed from decoding to identification, i.e., the receiver is only interested to check whether or not his message was sent by transmitter. Ahslwede and Dueck proved that by means of local randomness (at encoder) they can achieve doubly exponential gain in code size which outperfrom substantially the classical scheme of Shannon transmission. (only exponential gain in code size). However, in many cases, there is no need to exploit the Randomization at encoder and thus the view of identification without randomization is introduced.

On the other hand to derive probabilistic complexity of models for one/two way communications for distributive computing (communication between two processors for determine copperatively value of an identification function) similar ideas were discussed. The student should understand those ideas and try to find the link between them and idea of Identification of Ahlswede and Dueck. Ideally the student attempt to derive forward or/and backward proof for non-randomized identification capacity of the Binary Symmetric Channel (BSC).

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

An Introduction to Zero-Error Identification Capacity

Description

1. The zero error capacity (C_0) for transmission (Shannon 1956) is the least upper bound of rates at which it is possible to transmit information across the noisy channel with zero probability of error.
2. Similarly a zero error capacity for identification (Ahlswede et al 1996) is the least upper bound of rates at which it is possible to identify information across the noisy channel with zero probability of type I error (type II is still nonzero).
3. In Identification scheme (Ahlwsede and Dueck 1989) the receiver is not interested in to estimate the sent message but rather it wants to answer reliably to a binary question with Yes/No answers. The question is: Is the actual sent message is my desired message or not?
4. Identification codes (with randomized encoder) the code size scales doubly exponential in block length, n (e^e^(nc)) which apparently outperform the classic Shannon codes with a code size of only single order exponential (e^(nc)).
5. As preliminaries, we study the Shannon zero error capacity as its own merit for transmission and a relation to Shannon zero error capacity of a graph. Further, we study and understand the identification capacity of a noisy channel and at the end we aims to perceive the zero error identification capacity of a noisy channel (i.e. type I error = 0 and type II error is not zero).
6. On the way of understanding C_0id, we need to address the zero-error capacities for transmission such as Erasure, List and Detection. Finally we draw the link between C_0id and C_0.

References:

1. R. Ahlswede, Ning Cai and Zhen ZHang, "Erasure, list, and detection zero-error capacities for low noise and a relation to identification," in  IEEE Transactions on Information Theory, vol. 42, no. 1, pp. 55-62, Jan. 1996, doi: 10.1109/18.481778.
   https://ieeexplore.ieee.org/document/481778
2. C. Shannon, "The zero error capacity of a noisy channel," in IRE Transactions on Information Theory, vol. 2, no. 3, pp. 8-19, September 1956, doi: 10.1109/TIT.1956.1056798.
   https://ieeexplore.ieee.org/document/1056798

Prerequisites

Supervisor:

Student