On the One-Way Algebraic Homomorphism

Eikoh CHIDA  Takao NISHIZEKI  Motoji OHMORI  Hiroki SHIZUYA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.1   pp.54-60
Publication Date: 1996/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
one-way function,  homomorphism,  cryptography,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper we discuss the relation between a one-way group homomorphism and a one-way ring homomorphism. Let U,V be finite abelian groups with #U=n. We show that if there exists a one-way group homomorphism f:UV, then there exists a one-way ring homomorphism F:ZnUZnImf. We also give examples of such ring homomorphisms which are one-way under a standard cryptographic assumption. This implies that there is an affirmative solution to an extended version of the open question raised by Feigenbaum and Merrit: Is there an encryption function f such that both f(x+y) and f(x・y) can be efficiently computed from f(x) and f(y)? A multiple signature scheme is also given as an application of one-way ring homomorphisms.