New combinatorial bounds for authentication codes and key predistribution schemes (Q1273509)

The paper deals with lower bounds for authentication codes (A-codes) without secrecy. First, a new lower bound on the number of keys in an A-code is proved. Then a new scenario for authentication is introduced. In the scenario an opponent after observing \(p\) messages sends \(q\) messages to the receiver and succeeds if all \(q\) messages are accepted as authentic. A lower bound on the cheating probabilities as well as a lower bound on the number of keys in the A-code are proved for the new scenario. Finally, key predistribution schemes (KPS) are considered. First, a new upper bound on a number of users for so called \((2, t)\) KPS is established. Then it is shown that for a \((g, t)\) KPS there exists a corresponding A-code without secrecy. Combining the link between KPS and A-codes without secrecy together with the lower bound for A-codes derived in the first part of the paper a new lower bound on the amount of users' secret information is proved.