Identification based on random coding

Ahlswede and Dueck show a possibility to identify with high probability one of M messages by transmitting 1/C log log M bits only, where C is the channel capacity. This identification can be based on error-correcting codes. We propose an identification procedure based on random codes which achieves channel capacity. Then we show that this procedure can be simplified using pseudorandom generators.