TY - JOUR

T1 - One-way functions over finite near-rings

AU - Chida, Eikoh

AU - Shizuya, Hiroki

AU - Nishizeki, Takao

PY - 1995/1

Y1 - 1995/1

N2 - A near-ring is an extended notion of a usual ring. Therefore a ring is a near-ring, but the converse does not necessarily hold. We investigate in this paper one-way functions associated with finite near-rings, and show that if there exists a one-way group homomorphism, there exists a one-way non-ring near-ring homomorphism (Theorem 1); if there exists a one-way ring homomorphism, there exists a one-way non-ring near-ring homomorphism (Theorem 2). Further, we introduce a discrete logarithm problem over a finite near-ring, and show that the integer factoring is probabilistic polynomial-time Turing equivalent to a modified version of this problem (Theorem 3). Theorem 1 implies that under some standard cryptographic assumption, there is an affirmative but trivial solution to the extended version of the open question: Is there an encryption function f such that both f(x + y) and f(xy) are efficiently computed from given f(x) and f(y)?

AB - A near-ring is an extended notion of a usual ring. Therefore a ring is a near-ring, but the converse does not necessarily hold. We investigate in this paper one-way functions associated with finite near-rings, and show that if there exists a one-way group homomorphism, there exists a one-way non-ring near-ring homomorphism (Theorem 1); if there exists a one-way ring homomorphism, there exists a one-way non-ring near-ring homomorphism (Theorem 2). Further, we introduce a discrete logarithm problem over a finite near-ring, and show that the integer factoring is probabilistic polynomial-time Turing equivalent to a modified version of this problem (Theorem 3). Theorem 1 implies that under some standard cryptographic assumption, there is an affirmative but trivial solution to the extended version of the open question: Is there an encryption function f such that both f(x + y) and f(xy) are efficiently computed from given f(x) and f(y)?

UR - http://www.scopus.com/inward/record.url?scp=0029219644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029219644&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0029219644

SN - 0916-8508

VL - E78-A

SP - 4

EP - 10

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 1

ER -