The power of primes: security of authentication based on a universal hash-function family
The power of primes: security of authentication based on a universal hash-function family
复制标题
DOI：
10.1515/jmc.2010.005
复制
发表时间：
2010-10-01
影响因子：
1.2
通讯作者：
Poovendran, Radha
中科院分区：
文献类型：
--
作者：
Alomair, Basel;Clark, Andrew;Poovendran, Radha
基于通用散列函数族的消息认证码（MAC）由于其快速实现而变得越来越流行。本文研究了文献中反复出现的一类泛散列函数，并对基于这类泛散列函数的认证码的安全性进行了详细的代数分析。特别地，如文献中出现的，分析中的通用散列族使用有限域Zp中的操作。没有以前的工作已经研究了这种通用散列族的扩展时，执行计算模一个非素数n。在这项工作中，我们提供了第一个这样的分析。我们研究了在任意有限整数环Z（n）上进行计算时认证的安全性，并导出了n的素因子分解与成功伪造概率的界之间的显式关系。更具体地说，我们证明了基于这样一个通用散列函数族的认证码的成功伪造的概率是有界的模n的最小素因子的倒数。
Message authentication codes (MACs) based on universal hash-function families are becoming increasingly popular due to their fast implementation. In this paper, we investigate a family of universal hash functions that has been appeared repeatedly in the literature and provide a detailed algebraic analysis for the security of authentication codes based on this universal hash family. In particular, the universal hash family under analysis, as appeared in the literature, uses operation in the finite field Zp. No previous work has studied the extension of such universal hash family when computations are performed modulo a non-prime integer n. In this work, we provide the first such analysis. We investigate the security of authentication when computations are performed over arbitrary finite integer rings Z(n) and derive an explicit relation between the prime factorization of n and the bound on the probability of successful forgery. More specifically, we show that the probability of successful forgery against authentication codes based on such a universal hash-function family is bounded by the reciprocal of the smallest prime factor of the modulus n.