Abstract: The cartesian authentication codes based on k-spanning tree are constructed and their parameters are derived. The probabilities of success for the impersonation attack, the substitution attack and r-spoofing attack are also computed respectively based on the assumption of the encoding rules which are chosen according to a uniform probability distribution. These results extend results given by Wang Yongchuan and Yang Yixian.

Key words: cartesian authentication code, k-spanning tree, r-spoofing attack, lower bound of information theory

摘要： 利用完全图[Kn]中的k-生成树性质构造了一个新的cartesian认证码，计算了码参数，当编码规则按照均匀的概率分布被选取时，计算了该码的成功冒充攻击概率、成功替换攻击概率和[r]阶欺骗攻击成功的概率，改进了已有的相关结果。

关键词: cartesian认证码, k-生成树, [r]阶欺骗攻击, 信息论下界