Fast Modular Reduction over Euclidean Rings and Its Application to Universal Hash Functions

Xiangyong ZENG  Lei HU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.1   pp.305-310
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.1.305
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
modular reduction,  Euclidean ring,  lattice,  universal hash function family,  message authentication code,  

Full Text: PDF>>
Buy this Article




Summary: 
In this letter, we propose a fast modular reduction method over Euclidean rings, which is a generalization of Barrett's reduction algorithm over the ring of integers. As an application, we construct new universal hash function families whose operations are modular arithmetic over a Euclidean ring, which can be any of three rings, the ring of integers, the ring of Gauss integers and the ring of Eisenstein integers. The implementation of these families is efficient by using our method.